The "Last" Decision Problem for Rational Trace Languages
The "Last" Decision Problem for Rational Trace Languages
复制标题
有理跟踪语言的“最后”决策问题
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
J. Sakarovitch
中科院分区：
文献类型：
--
作者：
J. Sakarovitch
本文证明了自由部分交换幺半群（即迹幺半群）的有理集是否可识别当且仅当交换关系是传递的（即迹幺半群同构于自由交换幺半群的自由积）。大部分的文件包括通过广义有限自动机的自由产品的可识别集的特征。
It is established here that it is decidable whether a rational set of a free partially commutative monoid (i.e. trace monoid) is recognizable or not if and only if the commutation relation is transitive (i.e. if the trace monoid is isomorphic to a free product of free commutative monoids). The bulk of the paper consists in a characterization of recognizable sets of free products via generalized finite automata.