Sweeping input-driven pushdown automata

DOI10.1142/S0129054125410072MaRDI QIDQ6857626zbMATH OpenFDO

Authors Martin Kutrib

Publication date 17 February 2026

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

determinizationinput-driven pushdown automatacomputational capacitydecidability problemshalting computationssweeping input processing

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3230262 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A simulation result for the auxiliary pushdown automata
• Adding nesting structure to words
• Boosting reversible pushdown and queue machines by preprocessing
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Digging input-driven pushdown automata
• Growing context-sensitive languages and Church-Rosser languages
• Input-Driven Double-Head Pushdown Automata
• Input-Driven Queue Automata with Internal Transductions
• Input-driven multi-counter automata
• Input-driven stack automata
• Membership for growing context-sensitive grammars is polynomial
• Minimizing Variants of Visibly Pushdown Automata
• On reducing the number of stack symbols in a PDA
• On reducing the number of states in a PDA
• On the Tape Complexity of Deterministic Context-Free Languages
• On the complexity of formal grammars
• On the power of pushing or stationary moves for input-driven pushdown automata
• Operator precedence and the visibly pushdown property
• Ordered multi-stack visibly pushdown automata
• Scope-bounded pushdown languages
• Stack automata and compiling
• Sweeping input-driven pushdown automata
• Synchronization of Pushdown Automata
• The tree width of auxiliary storage
• Tight lower bounds on the size of sweeping automata
• Time and tape complexity of pushdown automaton languages
• Time-bounded grammars and their languages
• Tinput-driven pushdown, counter, and stack automata
• Two-way pushdown automata
• Two-way visibly pushdown automata and transducers
• Visibly pushdown languages
• When input-driven pushdown automata meet reversiblity

This page was built for publication: Sweeping input-driven pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6857626)