Determinizing k-path input-driven PDAs

DOI10.1007/978-3-032-32016-2_13MaRDI QIDQ7412096zbMATH OpenFDO

Authors Mohammad Zakzok, Kai Salomaa

Publication date 2027

Full work available at URL https://doi.org/10.1007/978-3-032-32016-2_13

zbMATH Keywords

determinizationinput-driven pushdown automatalimited nondeterminismlower boundssize complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Adding nesting structure to words
• Ambiguity, nondeterminism and state complexity of finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Exact descriptional complexity of determinization of input-driven pushdown automata
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
• Input-Driven Pushdown Automata with Limited Nondeterminism
• State complexity of finite tree width NFAs
• Visibly pushdown languages

This page was built for publication: Determinizing \(k\)-path input-driven PDAs

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