Journal article

Publication year: 2017

Pages: 59-88

Journal: Fundamenta Informaticae

Volume number: 155

Issue number: 1-2

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2017-1576

Publisher: SAGE Publications

Abstract: 
In input-driven automata the input alphabet is divided into distinct classes and different actions on the storage medium are solely governed by the input symbols. For example, in inputdriven pushdown automata (IDPDA) there are three distinct classes of input symbols determining the action of pushing, popping, or doing nothing on the pushdown store. Here, input-driven automata are extended in such a way that the input is preprocessed by a deterministic sequential transducer. IDPDAs extended in this way are called tinput-driven pushdown automata (TDPDA) and it turns out that TDPDAs are more powerful than IDPDAs but still not as powerful as real-time deterministic pushdown automata. Nevertheless, even this stronger model has still good closure and decidability properties. In detail, it is shown that TDPDAs are closed under the Boolean operations union, intersection, and complementation. Furthermore, decidability procedures for the inclusion problem as well as for the questions of whether a given automaton is a TDPDA or an IDPDA are developed. Additionally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established. Two other classes investigated are on the one hand TDPDAs restricted to tinput-driven counter automata and on the other hand TDPDAs generalized to tinput-driven stack automata. In both cases, it is possible to preserve the good closure and decidability properties of TDPDAs, namely, the closure under the Boolean operations as well as the decidability of the inclusion problem.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2017) Tinput-Driven Pushdown, Counter, and Stack Automata, Fundamenta Informaticae, 155(1-2), pp. 59-88. https://doi.org/10.3233/FI-2017-1576

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2017). Tinput-Driven Pushdown, Counter, and Stack Automata. Fundamenta Informaticae. 155(1-2), 59-88. https://doi.org/10.3233/FI-2017-1576