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.
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
- scientific article; zbMATH DE number 5671765 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 44695 (Why is no real title available?)
- scientific article; zbMATH DE number 3509706 (Why is no real title available?)
- scientific article; zbMATH DE number 2038746 (Why is no real title available?)
- scientific article; zbMATH DE number 2040920 (Why is no real title available?)
- scientific article; zbMATH DE number 1796157 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- A Note on Pushdown Store Automata and Regular Systems
- CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
- Counter machines and verification problems.
- Deterministic context free languages
- Deterministic stack automata and the quotient operator
- Deterministic stack transducers
- Iterated stack automata and complexity classes
- Look-ahead on pushdowns
- New Decidability Results Concerning Two-Way Counter Machines
- On the density of context-free and counter languages
- On the density of languages accepted by Turing machines and other machine models
- One-way stack automata
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Reversal-bounded multipushdown machines
- Some Results on Tape-Bounded Turing Machines
- Some decision problems concerning semilinearity and commutation.
- Stack automata and compiling
- The complexity of decision problems for finite-turn multicounter machines
- The effect of end-markers on counter machines and commutativity
- Turing machines with sublogarithmic space
- Visibly pushdown automata and transducers with counters
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
- scientific article; zbMATH DE number 7301303 (Why is no real title available?)
- State grammars with stores
- On families of full trios containing counter machine languages
- On counting functions and slenderness of languages
- Descriptional complexity of pushdown store languages
- Descriptional complexity of pushdown store 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)
