Paper Info
Title
On Store Languages of Language Acceptors.
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 store 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 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 of Turing machines for having non-regular store languages are obtained.
Year
DOI
Venue
2018
10.1016/j.tcs.2018.05.036
Theoretical Computer Science
Keywords
DocType
Volume
Store languages,Turing machines,Storage structures,Right quotient,Automata
Journal
745
ISSN
Citations 
PageRank 
0304-3975
2
0.39
References 
Authors
13
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72