Grammatical characterizations of NPDAs and VPDAs with counters

DOI10.1016/J.TCS.2018.06.035zbMATH Open1400.68106OpenAlexW2811459629MaRDI QIDQ1784750FDOQ1784750

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

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

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)

Cites Work

• Title not available (Why is that?)
• Visibly pushdown languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• On Context-Free Languages
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence of four extensions of context-free grammars
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• Title not available (Why is that?)
• The complexity of decision problems for finite-turn multicounter machines
• Title not available (Why is that?)
• Left-derivation bounded languages
• Title not available (Why is that?)
• Linear indexed languages
• Derivation-bounded languages
• Visibly pushdown automata and transducers with counters
• Title not available (Why is that?)

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)