Green's Relations and Their Use in Automata Theory
Green's Relations and Their Use in Automata Theory
复制标题
DOI：
10.1007/978-3-642-21254-3_1
复制
发表时间：
2011-05
期刊：
影响因子：
--
通讯作者：
Thomas Colcombet
中科院分区：
文献类型：
--
作者：
Thomas Colcombet
本综述的目的是介绍幺半群的理想理论，即所谓的绿色关系，并说明这种工具在解决自动机相关问题时的实用性。我们使用绿色关系证明了与自动机理论相关的四个经典结果：Schützenberger刻画无星语言的结果，Simon的因子分解森林定理，谢梅诺夫的可判定一元理论的无限词的刻画和McNaughton的无限词上的自动机的确定性的结果。
The objective of this survey is to present the ideal theory of monoids, the so-called Green’s relations, and to illustrate the usefulness of this tool for solving automata related questions.We use Green’s relations for proving four classical results related to automata theory: The result of Schützenberger characterizing star-free languages, the theorem of factorization forests of Simon, the characterization of infinite words of decidable monadic theory due to Semenov, and the r esult of determinization of automata over infinite words of McNaughton.