On store languages and applications

DOI10.1016/j.ic.2019.03.003zbMath1422.68151arXiv2010.00523OpenAlexW2922460544MaRDI QIDQ2417850

Ian McQuillan, Oscar H. Ibarra

Publication date: 29 May 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.00523

zbMATH Keywords

determinismautomatafinite automatacounter machinesreversal-boundsstore languagesdeletion operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of end-markers on counter machines and commutativity
• The complexity of decision problems for finite-turn multicounter machines
• Reversal-bounded multipushdown machines
• Semilinearity of families of languages
• On store languages of language acceptors
• Some decision problems concerning semilinearity and commutation.
• Eliminating the storage tape in reachability constructions.
• Set Automata
• On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L
• BOUNDED PARIKH AUTOMATA
• Global Model Checking of Ordered Multi-Pushdown Systems
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• On the Reachability Analysis of Acyclic Networks of Pushdown Systems
• From Multi to Single Stack Automata
• Reversal-Bounded Counter Machines Revisited
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• k + 1 Heads Are Better than k
• Deterministic Stack Transducers
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS
• [https://portal.mardi4nfdi.de/wiki/Publication:5376337 On the Density of Languages Accepted by Turing Machines and Other Machine Models]
• One-way stack automata
• A Note on Pushdown Store Automata and Regular Systems
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• CONCUR 2005 – Concurrency Theory
• Decidable models of integer-manipulating programs with recursive parallelism
• Reachability analysis of pushdown automata: Application to model-checking

This page was built for publication: On store languages and applications