Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
- PDF / 369,596 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 239 Views
Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata Benedek Nagy · Friedrich Otto
Received: 10 April 2012 / Accepted: 18 December 2012 / Published online: 30 January 2013 © Springer-Verlag Berlin Heidelberg 2013
Abstract Recently the one-counter trace languages and the context-free trace languages have been characterized through restricted types of cooperating distributed systems (CDsystems) of stateless deterministic restarting automata with window size one (so-called stldet-R(1)-automata) that work in mode ‘=1’ 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.
1 Introduction For analyzing sentences of a natural language with free word-order, the technique of analysis by reduction is used in linguistics (see, e.g., [17]). This technique consists in a stepwise
B. Nagy was supported by the TÁMOP 4.2.1/B-09/1/KONV-2010-0007 and by the TÁMOP 4.2.2/C-11/1/KONV-2012-0001 projects that are implemented through the New Hungary Development Plan and have been supported by the European Union, co-financed by the European Social Fund. The results of this paper have been announced at the 13-th International Conference on Automata and Formal Languages, AFL 2011, in Debrecen, Hungary, August 2011. An extended abstract appeared in the proceedings of that conference [26]. B. Nagy (B) Department of Computer Science, Faculty of Informatics, University of Debrecen, Egyetem tér 1., Debrecen 4032, Hungary e-mail: [email protected] F. Otto Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany e-mail: [email protected]
123
230
B. Nagy, F. Otto
simplification of a given sentence until a simple core sentence is obtained. It is required that the simplifications preserve the syntactic correctness or incorrectness of the sentence. For modelling this technique the so-called restarting automaton was introduced by Janˇcar et al. in [14]. A restarting automaton M consists of a finite-state control and a flexible tape with end markers on which a read/write window of a fixed size k ≥ 1 operates. The automaton M works in cycles: starting in its initial state with the read/write window on the left end of the tape, it scans the tape from left to right until it detects a factor of size at most k that can be simplified, which means that this factor can be rewritten by a shorter word. As the tape is flexible, it adjusts to this shortening, that is, no empty tape cells are created. After performing the simplification, M restarts, that is, its read/write window is placed over the left en
Data Loading...
