State grammars with stores

DOI10.1016/J.TCS.2019.06.024MaRDI QIDQ5919706zbMATH OpenOpenAlexWikidataFDO

Authors Oscar H. Ibarra, Ian McQuillan

Publication date 7 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.06.024

zbMATH Keywords

automata modelsemptiness problemgrammarsmatrix grammarsNPNP-completenessPreversal-bounded counters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• State grammars with stores
• scientific article; zbMATH DE number 4068327
• On state-alternating context-free grammars
• On store languages and applications
• Grammatical characterizations of NPDAs and VPDAs with counters

Cites work

• A hierarchy between context-free and context-sensitive languages
• Finite-Turn Pushdown Automata
• Grammatical characterizations of NPDAs and VPDAs with counters
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Matrix grammars with a leftmost restriction
• On state-alternating context-free grammars
• On the effect of the finite index restriction on several families of grammars
• Petri net algorithms in the theory of matrix grammars
• Remarks on blind and partially blind one-way multicounter machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Slender matrix languages
• Some remarks on state grammars and matrix grammars
• The complexity of decision problems for finite-turn multicounter machines
• The effect of end-markers on counter machines and commutativity

Cited in

(3)

• On store languages of language acceptors
• scientific article; zbMATH DE number 4068327 (Why is no real title available?)
• State grammars with stores

This page was built for publication: State grammars with stores

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