Paper Info
Title
On Store Languages and Applications
Abstract
The store language of a machine of some arbitrary type is the set of all store configurations (state plus store contents but not input) that can appear in an accepting computation. New algorithms and characterizations of store languages are obtained, such as the result that any nondeterministic pushdown automaton augmented with reversal-bounded counters, where the pushdown can “flip” its contents a bounded number of times, can be accepted by a machine with only reversal-bounded counters. Connections are made between store languages and several model checking and reachability problems, such as accepting the set of all predecessor and successor configurations of a machine from a given (regular) set of configurations. For a variety of different machine models often containing multiple parallel data stores, these sets can be accepted with a machine model that is simpler than the original model itself. Store languages are key to showing these properties.
Year
DOI
Venue
2019
10.1016/j.ic.2019.03.003
Information and Computation
Keywords
Field
DocType
Automata,Store languages,Counter machines,Deletion operations,Reversal-bounds,Determinism,Finite automata
Discrete mathematics,Model checking,Nondeterministic algorithm,Successor cardinal,Reachability,Theoretical computer science,Machine models,Pushdown automaton,Mathematics,Computation,Bounded function
Journal
Volume
ISSN
Citations 
267
0890-5401
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72