Grammatical characterizations of NPDAs and VPDAs with counters

DOI10.1016/j.tcs.2018.06.035zbMath1400.68106OpenAlexW2811459629MaRDI QIDQ1784750

Oscar H. Ibarra

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

zbMATH Keywords

characterizationsclosure propertiesemptiness problemChomsky-Schützenberger theoremautomata with reversal-bounded countersgrammatical models

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

State grammars with stores

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

This page was built for publication: Grammatical characterizations of NPDAs and VPDAs with counters