State Complexity of the Quotient Operation on Input-Driven Pushdown Automata

DOI10.1142/S0129054119400367zbMath1427.68152OpenAlexW2973381442MaRDI QIDQ5205050

Alexander Okhotin, Kai Salomaa

Publication date: 10 December 2019

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

Full work available at URL: https://doi.org/10.1142/s0129054119400367

zbMATH Keywords

closure propertiesstate complexityquotientvisibly pushdown automatainput-driven automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional complexity of unambiguous input-driven pushdown automata
• The family of one-counter languages is closed under quotient
• Intersection and union of regular languages and state complexity
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• State complexity of operations on input-driven pushdown automata
• The quotient operation on input-driven pushdown automata
• Input-driven languages are linear conjunctive
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Adding nesting structure to words
• Visibly pushdown languages
• Deterministic context free languages
• Quotients of Context-Free Languages
• A further note on top-down deterministic languages
• Edit distance neighbourhoods of input-driven pushdown automata

This page was built for publication: State Complexity of the Quotient Operation on Input-Driven Pushdown Automata