Green’s Relations in Deterministic Finite Automata
Green’s Relations in Deterministic Finite Automata
复制标题
确定性有限自动机中的格林关系
DOI：
10.1007/s00224-018-9847-4
复制
发表时间：
2018
影响因子：
0.5
通讯作者：
M. Kufleitner
中科院分区：
文献类型：
--
作者：
L. Fleischer;M. Kufleitner
绿色关系是半群结构理论中的一个基本工具。它们可以通过（右/左/双侧）Cayley图中的可达性来定义。绿色关系的等价类则对应于强连通分量。研究了有限集上变换生成的半群中绿色关系的复杂性。我们表明，在最坏的情况下，等价类的数量是在相同的数量级的元素的数量。另一个重要的参数是强连通分支链的最大长度。我们的主要贡献是这个参数的指数下界。有一个简单的构造任意一组生成器。然而，对于一个恒定大小的字母表的证明是相当复杂的。我们还研究了一元和二进制字母表的特殊情况。这些结果推广到确定性有限自动机及其句法半群。
Green’s relations are a fundamental tool in the structure theory of semigroups. They can be defined by reachability in the (right/left/two-sided) Cayley graph. The equivalence classes of Green’s relations then correspond to the strongly connected components. We study the complexity of Green’s relations in semigroups generated by transformations on a finite set. We show that, in the worst case, the number of equivalence classes is in the same order of magnitude as the number of elements. Another important parameter is the maximal length of a chain of strongly connected components. Our main contribution is an exponential lower bound for this parameter. There is a simple construction for an arbitrary set of generators. However, the proof for a constant size alphabet is rather involved. We also investigate the special cases of unary and binary alphabets. All these results are extended to deterministic finite automata and their syntactic semigroups.
DOI：
10.1007/978-3-319-58747-9_12
发表时间：
2017-03
期刊：
--
影响因子：
--
作者：
Lukas Fleischer;Manfred Kufleitner
通讯作者：
Lukas Fleischer;Manfred Kufleitner