State complexity of operations on input-driven pushdown automata

DOI10.1007/978-3-642-22993-0_44MaRDI QIDQ3088065zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin, Kai Salomaa

Publication date 17 August 2011

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

Full work available at URL https://doi.org/10.1007/978-3-642-22993-0_44

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of operations on input-driven pushdown automata
• Towards exact state complexity bounds for input-driven pushdown automata
• Further closure properties of input-driven pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

Cited in

(13)

• Towards exact state complexity bounds for input-driven pushdown automata
• When input-driven pushdown automata meet reversiblity
• State complexity of the concatenation of regular tree languages
• Further closure properties of input-driven pushdown automata
• State complexity of the quotient operation on input-driven pushdown automata
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Descriptional complexity of unambiguous input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Operational state complexity of nested word automata
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Descriptional complexity of input-driven pushdown automata
• The quotient operation on input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

This page was built for publication: State complexity of operations on input-driven pushdown automata

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