On store languages of language acceptors

DOI10.1016/j.tcs.2018.05.036zbMath1400.68107arXiv1702.07388OpenAlexW2999574320MaRDI QIDQ1786598

Oscar H. Ibarra, Ian McQuillan

Publication date: 24 September 2018

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

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

zbMATH Keywords

Turing machinesautomataright quotientstorage structuresstore languages

Mathematics Subject Classification ID

Related Items (7)

Space Complexity of Stack Automata Models ⋮ On store languages and applications ⋮ New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines ⋮ On counting functions and slenderness of languages ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On families of full trios containing counter machine languages ⋮ Space Complexity of Stack Automata Models

Cites Work

• 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
• Look-ahead on pushdowns
• The complexity of decision problems for finite-turn multicounter machines
• Iterated stack automata and complexity classes
• Reversal-bounded multipushdown machines
• Turing machines with sublogarithmic space
• Counter machines and verification problems.
• Some decision problems concerning semilinearity and commutation.
• Deletion operations on deterministic families of automata
• Insertion operations on deterministic reversal-bounded counter machines
• Deterministic stack automata and the quotient operator
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• New Decidability Results Concerning Two-Way Counter Machines
• Visibly Pushdown Automata and Transducers with Counters
• Deterministic Stack Transducers
• On the Density of Context-Free and Counter Languages
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• [https://portal.mardi4nfdi.de/wiki/Publication:5376337 On the Density of Languages Accepted by Turing Machines and Other Machine Models]
• Deterministic context free languages
• Stack automata and compiling
• One-way stack automata
• A Note on Pushdown Store Automata and Regular Systems
• Some Results on Tape-Bounded Turing Machines

This page was built for publication: On store languages of language acceptors