On store languages of language acceptors
From MaRDI portal
Publication:1786598
DOI10.1016/J.TCS.2018.05.036zbMATH Open1400.68107arXiv1702.07388OpenAlexW2999574320WikidataQ129656991 ScholiaQ129656991MaRDI QIDQ1786598FDOQ1786598
Authors: Oscar H. Ibarra, Ian McQuillan 
Publication date: 24 September 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: It is well known that the "store language" of every pushdown automaton -- the set of store configurations (state and stack contents) that can appear as an intermediate step in accepting computations -- is a regular language. Here many models of language acceptors with various data structures are examined, along with a study of their store languages. For each model, an attempt is made to find the simplest model that accepts their store languages. Some connections between store languages of one-way and two-way machines generally are demonstrated, as with connections between nondeterministic and deterministic machines. A nice application of these store language results is also presented, showing a general technique for proving families accepted by many deterministic models are closed under right quotient with regular languages, resolving some open questions (and significantly simplifying proofs for others that are known) in the literature. Lower bounds on the space complexity for recognizing store languages for the languages to be non-regular are obtained.
Full work available at URL: https://arxiv.org/abs/1702.07388
Recommendations
- On store languages and applications
- Deterministic acceptors for indexed languages
- State grammars with stores
- State grammars with stores
- Some Decision Questions Concerning the Time Complexity of Language Acceptors
- SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
- Languages and P0L schemes
- Descriptional complexity of pushdown store languages
- Descriptional complexity of pushdown store languages
- scientific article; zbMATH DE number 7301303
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reversal-bounded multipushdown machines
- Some decision problems concerning semilinearity and commutation.
- The effect of end-markers on counter machines and commutativity
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
- Deterministic context free languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Iterated stack automata and complexity classes
- Turing machines with sublogarithmic space
- The complexity of decision problems for finite-turn multicounter machines
- Title not available (Why is that?)
- Counter machines and verification problems.
- New Decidability Results Concerning Two-Way Counter Machines
- Stack automata and compiling
- A Note on Pushdown Store Automata and Regular Systems
- One-way stack automata
- Some Results on Tape-Bounded Turing Machines
- Look-ahead on pushdowns
- Visibly pushdown automata and transducers with counters
- Deterministic stack automata and the quotient operator
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deterministic stack transducers
- On the density of context-free and counter languages
- On the density of languages accepted by Turing machines and other machine models
Cited In (13)
- Space complexity of stack automata models
- New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
- A direct construction of finite state automata for pushdown store languages
- Input-Position-Restricted Models of Language Acceptors
- Title not available (Why is that?)
- State grammars with stores
- On families of full trios containing counter machine languages
- Descriptional complexity of pushdown store languages
- Descriptional complexity of pushdown store languages
- On counting functions and slenderness of languages
- Space Complexity of Stack Automata Models
- On store languages and applications
- The bag automaton: a model of nondeterministic storage
This page was built for publication: On store languages of language acceptors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786598)
