Deciding path size of nondeterministic (and input-driven) pushdown automata

DOI10.1016/J.TCS.2022.10.023MaRDI QIDQ2098178zbMATH OpenOpenAlexFDO

Authors Yo-Sub Han, Sang-Ki Ko, Kai Salomaa

Publication date 17 November 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.10.023

zbMATH Keywords

ambiguitydecidabilityinput-driven pushdown automatonmeasures of nondeterminismpath size

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Input-Driven Pushdown Automata with Limited Nondeterminism
• Limited nondeterminism of input-driven pushdown automata: decidability and complexity
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• On the degree of ambiguity of finite automata

Cites work

• 2-Visibly Pushdown Automata
• A Second Course in Formal Languages and Automata Theory
• Adding nesting structure to words
• Ambiguity, nondeterminism and state complexity of finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Descriptional complexity of machines with limited resources
• Edit-distance between visibly pushdown languages
• scientific article; zbMATH DE number 3839323 (Why is no real title available?)
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 4090831 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Measures of nondeterminism for pushdown automata
• Measuring nondeterminism in pushdown automata
• Nondeterministic state complexity of nested word automata
• On the degree of ambiguity of finite automata
• On the finite-valuedness problem for sequential machines
• Problems on finite automata and the exponential time hypothesis
• Pumping and pushdown machines
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• State complexity of finite tree width NFAs
• State complexity of operations on input-driven pushdown automata
• Structural properties of NFAs and growth rates of nondeterminism measures
• The tractability frontier for NFA minimization
• Visibly pushdown automata with multiplicities: finiteness and K-boundedness
• Visibly pushdown languages

Cited in

(4)

• Existential and universal width of alternating finite automata
• Exact descriptional complexity of determinization of input-driven pushdown automata
• Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
• Existential and universal width of alternating finite automata

This page was built for publication: Deciding path size of nondeterministic (and input-driven) pushdown automata

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