Towards exact state complexity bounds for input-driven pushdown automata

DOI10.1007/978-3-319-98654-8_36MaRDI QIDQ1622993zbMATH OpenOpenAlexFDO

Authors Galina Jirásková, Alexander Okhotin

Publication date 22 November 2018

Full work available at URL https://doi.org/10.1007/978-3-319-98654-8_36

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of operations on input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Descriptional complexity of unambiguous input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

Cited in

(8)

• Input-Driven Pushdown Automata with Limited Nondeterminism
• State complexity of operations on input-driven pushdown automata
• Descriptional complexity of input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Descriptional complexity of unambiguous input-driven pushdown automata
• Lower bound for the number of states of purposeful deterministic automata
• Exact descriptional complexity of determinization of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata

This page was built for publication: Towards exact state complexity bounds for input-driven pushdown automata

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