Grammatical characterizations of NPDAs and VPDAs with counters

DOI10.1016/J.TCS.2018.06.035MaRDI QIDQ1784750zbMATH OpenOpenAlexFDO

Authors 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 problemautomata with reversal-bounded countersgrammatical modelsChomsky-Schützenberger theorem

Mathematics Subject Classification ID

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

Recommendations

• Visibly pushdown automata and transducers with counters
• Some decision problems concerning NPDAs, palindromes, and Dyck languages
• Pushdown automata with reversal-bounded counters
• One-reversal counter machines and multihead automata: revisited
• The Power of Alternating One-Reversal Counters and Stacks

Cites work

• scientific article; zbMATH DE number 1670769 (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 1759611 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Derivation-bounded languages
• Indexed Grammars—An Extension of Context-Free Grammars
• Left-derivation bounded languages
• Linear indexed languages
• Nested Stack Automata
• On Context-Free Languages
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The complexity of decision problems for finite-turn multicounter machines
• The equivalence of four extensions of context-free grammars
• Visibly pushdown automata and transducers with counters
• Visibly pushdown languages

Cited in

(3)

• Some decision problems concerning NPDAs, palindromes, and Dyck languages
• State grammars with stores
• Visibly pushdown automata and transducers with counters

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

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