On the power of pushing or stationary moves for input-driven pushdown automata
Loading...
Date
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
Quotable link
Abstract
Input-driven pushdown automata (IDPDAs) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that every push operation pushes exactly one additional symbol on the pushdown store and, in addition, stationary moves are not allowed so that the devices work in real time. Here, we relax this strong definition and consider IDPDAs that may push more than one symbol in one step (push-IDPDA) or may perform stationary moves (stat-IDPDA). We study the computational power of the extended variants both in the deterministic and nondeterministic case, we investigate several decidability questions for the new automata classes, and we obtain interesting representations by inverse homomorphisms. Namely, every (1) deterministic, (2) real-time deterministic, and (3) nondeterministic context-free language can be characterized as the inverse homomorphic image of a language accepted by a (1) stat-IDPDA, (2) push-IDPDA, and (3) nondeterministic push-IDPDA.Link to publications or other datasets
Description
Notes
Original publication in
Theoretical computer science 996 (2024), 114503