Grammatical characterizations of NPDAs and VPDAs with counters
From MaRDI portal
Publication:1784750
DOI10.1016/j.tcs.2018.06.035zbMath1400.68106OpenAlexW2811459629MaRDI 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
characterizationsclosure propertiesemptiness problemChomsky-Schützenberger theoremautomata with reversal-bounded countersgrammatical models
Related Items (1)
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Grammatical characterizations of NPDAs and VPDAs with counters