Parikh-reducing Church-Rosser representations for some classes of regular languages
Parikh-reducing Church-Rosser representations for some classes of regular languages
复制标题
某些类别的常规语言的 Parikh-reducing Church-Rosser 表示
DOI：
10.1016/j.tcs.2017.08.009
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Walter
中科院分区：
文献类型：
--
作者：
T. Walter
本文研究了Parikh-约化Church-Rosser系统的概念。它表明，对于两类正规语言存在这样的系统描述的语言使用的重写系统的许多等价类。这两个类是：1）。所有正则语言的类，使得语法幺半群只包含阿贝尔群，2）。在两个字母表上的所有语言群的分类。系统的建设产生幺半群表示，使所有的子群是阿贝尔。此外，这些表示的复杂性进行了研究。
In this paper the concept of Parikh-reducing Church–Rosser systems is studied. It is shown that for two classes of regular languages there exist such systems which describe the languages using finitely many equivalence classes of the rewriting system. The two classes are: 1.) the class of all regular languages such that the syntactic monoid contains only abelian groups and 2.) the class of all group languages over a two-letter alphabet. The construction of the systems yield a monoid representation such that all subgroups are abelian. Additionally, the complexity of those representations is studied.
登录
查看更多内容
DOI：
10.1016/c2009-0-21176-7
发表时间：
1983
期刊：
--
影响因子：
--
作者：
M. Davies;R. Segal;E. Weyuker
通讯作者：
M. Davies;R. Segal;E. Weyuker
DOI：
10.1016/j.tcs.2015.07.008
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
V. Diekert;M. Kufleitner
通讯作者：
M. Kufleitner
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
J. Almeida;O. Klíma
通讯作者：
O. Klíma
一些与 Church-Rosser 一致的常规语言
DOI：
10.1007/3-540-46011-x_29
发表时间：
2001
期刊：
Inf. Comput.
影响因子：
--
作者：
Gundula Niemann;Johannes Waldmann
通讯作者：
Johannes Waldmann
无星语言是 Church-Rosser 一致的
DOI：
10.1016/j.tcs.2012.01.028
发表时间：
2011
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
V. Diekert;Manfred Kufleitner;P. Weil
通讯作者：
P. Weil