Deciding path size of nondeterministic (and input-driven) pushdown automata
From MaRDI portal
Publication:2098178
DOI10.1016/j.tcs.2022.10.023OpenAlexW4307896660MaRDI QIDQ2098178
Kai Salomaa, Sang-Ki Ko, Yo-Sub Han
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
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The tractability frontier for NFA minimization
- On the finite-valuedness problem for sequential machines
- On the degree of ambiguity of finite automata
- Measures of nondeterminism for pushdown automata
- Pushdown automata with bounded nondeterminism and bounded ambiguity
- Problems on finite automata and the exponential time hypothesis
- Communication complexity method for measuring nondeterminism in finite automata
- Structural properties of NFAs and growth rates of nondeterminism measures
- Nondeterministic state complexity of nested word automata
- State complexity of operations on input-driven pushdown automata
- Measuring nondeterminism in pushdown automata
- Input-Driven Pushdown Automata with Limited Nondeterminism
- Edit-Distance Between Visibly Pushdown Languages
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness
- Adding nesting structure to words
- A Second Course in Formal Languages and Automata Theory
- Visibly pushdown languages
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Pumping and pushdown machines
- State Complexity of Finite Tree Width NFAs
- Ambiguity, Nondeterminism and State Complexity of Finite Automata
- 2-Visibly Pushdown Automata
This page was built for publication: Deciding path size of nondeterministic (and input-driven) pushdown automata
