Grammatical characterizations of NPDAs and VPDAs with counters
From MaRDI portal
Publication:1784750
DOI10.1016/j.tcs.2018.06.035zbMath1400.68106MaRDI QIDQ1784750
Publication date: 27 September 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.035
characterizations; closure properties; emptiness problem; Chomsky-Schützenberger theorem; automata with reversal-bounded counters; grammatical models
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Linear indexed languages
- The complexity of decision problems for finite-turn multicounter machines
- Left-derivation bounded languages
- On finite-index indexed grammars and their restrictions
- Derivation-bounded languages
- Visibly pushdown languages
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The equivalence of four extensions of context-free grammars
- Visibly Pushdown Automata and Transducers with Counters
- On Context-Free Languages
- Indexed Grammars—An Extension of Context-Free Grammars
- Nested Stack Automata