Towards exact state complexity bounds for input-driven pushdown automata

DOI10.1007/978-3-319-98654-8_36OpenAlexW2887759255MaRDI QIDQ1622993FDOQ1622993

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (8)

• Input-Driven Pushdown Automata with Limited Nondeterminism
• Descriptional complexity of unambiguous input-driven pushdown automata
• 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
• 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)