State complexity of the quotient operation on input-driven pushdown automata

DOI10.1142/S0129054119400367MaRDI QIDQ5205050zbMATH OpenOpenAlexFDO

Authors 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

quotientclosure propertiesstate complexityvisibly pushdown automatainput-driven automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The quotient operation on input-driven pushdown automata
• Further closure properties of input-driven pushdown automata
• Further closure properties of input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• The full quotient and its closure property for regular languages

Cites work

• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• A further note on top-down deterministic languages
• Adding nesting structure to words
• Descriptional complexity of unambiguous input-driven pushdown automata
• Deterministic context free languages
• Edit distance neighbourhoods of input-driven pushdown automata
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Input-driven languages are linear conjunctive
• Intersection and union of regular languages and state complexity
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Quotients of Context-Free Languages
• State complexity of operations on input-driven pushdown automata
• The family of one-counter languages is closed under quotient
• The quotient operation on input-driven pushdown automata
• Visibly pushdown languages

Cited in

(3)

• Further closure properties of input-driven pushdown automata
• The full quotient and its closure property for regular languages
• The quotient operation on input-driven pushdown automata

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

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