Paper Info
Title
The effect of end-markers on counter machines and commutativity.
Abstract
Restrictions of reversal-bounded multicounter machines are studied; in particular, those that cannot subtract from any counter until it has reached the end of the input. It is proven that this does not alter the languages accepted when the machines are nondeterministic. When the machines are deterministic, the languages (denoted by eDCM) are shown to coincide with those accepted by deterministic Parikh automata, but are strictly contained in the class of languages accepted by machines without this condition. It then follows that all commutative semilinear languages are in this restricted class. A number of decidability and complexity properties are shown, such as the ability to test, given a deterministic pushdown automaton (even if augmented by a fixed number of reversal-bounded counters), whether it is commutative. Lastly, this deterministic family, eDCM, is shown to be the smallest family of languages closed under commutative closure, right quotient with regular languages and inverse deterministic finite transductions.
Year
DOI
Venue
2016
10.1016/j.tcs.2016.02.034
Theoretical Computer Science
Keywords
Field
DocType
Counter machines,Commutativity,Reversal-bounds,Determinism,Finite automata
Deterministic context-free grammar,Discrete mathematics,Combinatorics,Two-way deterministic finite automaton,Deterministic automaton,Nested word,Deterministic finite automaton,Deterministic pushdown automaton,Deterministic context-free language,Pushdown automaton,Mathematics
Journal
Volume
Issue
ISSN
627
C
0304-3975
Citations 
PageRank 
References 
4
0.47
6
Authors
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72