Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata

作者：Nagy Benedek^*; Otto Friedrich

来源：Acta Informatica, 2013, 50(4): 229-255.

DOI：10.1007/s00236-012-0175-x

Recently the one-counter trace languages and the context-free trace languages have been characterized through restricted types of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size one (so-called stl-det-R(1)-automata) that work in mode %26apos;=1%26apos; and that use an external counter or pushdown store to determine the successor components within computations. Here we study the deterministic variants of these CD-systems, comparing the resulting language classes to the classes of languages defined by CD-systems of stl-det-R(1)-automata without such an external device and to some classical language families, among them in particular the classes of rational, one-counter, and context-free trace languages. In addition, we present a large number of (non-)closure properties for our language classes.

• 出版日期2013-6