Paper Info
Title
Tinput-Driven Pushdown Automata
Abstract
In input-driven pushdown automata (IDPDA) the input alphabet is divided into three distinct classes and the actions on the pushdown store (push, pop, nothing) are solely governed by the input symbols. Here, this model is extended in such a way that the input of an IDPDA is preprocessed by a deterministic sequential transducer. These automata 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. Finally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established.
Year
DOI
Venue
2015
10.1007/978-3-319-23111-2_7
Lecture Notes in Computer Science
Keywords
Field
DocType
Input driven pushdown automata,Sequential transducers,Real-time deterministic context-free languages,Closure properties,Decidability questions
Deterministic context-free grammar,Discrete mathematics,Embedded pushdown automaton,Context-free language,Two-way deterministic finite automaton,Combinatorics,Nested word,Deterministic pushdown automaton,Deterministic context-free language,Pushdown automaton,Mathematics
Conference
Volume
ISSN
Citations 
9288
0302-9743
3
PageRank 
References 
Authors
0.41
7
3
Name
Order
Citations
PageRank
Martin Kutrib177889.77
Andreas Malcher220439.40
Matthias Wendlandt33214.13