Journal article

Publication year: 2024

Journal: Theoretical Computer Science

Volume number: 996

ISSN: 0304-3975

eISSN: 1879-2294

Open access status: Hybrid

DOI Link: https://doi.org/10.1016/j.tcs.2024.114503

Publisher: Elsevier

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) realtime 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.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2024) On the power of pushing or stationary moves for input-driven pushdown automata, Theoretical Computer Science, 996, Article 114503. https://doi.org/10.1016/j.tcs.2024.114503

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2024). On the power of pushing or stationary moves for input-driven pushdown automata. Theoretical Computer Science. 996, Article 114503. https://doi.org/10.1016/j.tcs.2024.114503