On CD-systems of stateless deterministic R-automata with window size one

详细信息	查看全文 | 推荐本文 |

• 作者：Benedek Nagy^a ; ¹ ; ^{nbenedek@inf.unideb.hu} ; Friedrich Otto^b ; ^{otto@theory.informatik.uni-kassel.de}
• 关键词：Restarting automaton ; CD-system ; Rational trace language ; Closure property
• 刊名：Journal of Computer and System Sciences
• 出版年：2012
• 期刊代码：186_00220000
• 类别：et
• 出版时间：May, 2012
• 卷：78
• 期：3
• 页码：780-806
• 文件大小：502 K

摘要

Here we study cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic -automata. We study the expressive power of these systems by relating the class of languages that they accept by mode =1 computations to other well-studied language classes, showing in particular that this class only contains semi-linear languages. Our model can be viewed as a nondeterministic finite-state acceptor with translucent letters, that is, it processes its input in a different way than the usual left-to-right order. In this way all commutative semi-linear languages, and in fact all rational trace languages, can be accepted. In addition, we investigate the closure and non-closure properties of the class of languages accepted by our model and some of its algorithmic properties.