The word problem distinguishes counter languages

2006/06/17 by Sean Cleary, Cleary, Sean, Murray Elder +3
Mathematics · #20F10 #68Q45 #FOS: Mathematics #Group Theory (math.GR) #math.GR #msc:20F10 #msc:68Q45

paper · pdf · doi:10.48550/arxiv.math/0606415

8 pages

arxiv created 2006/06/17 · arxiv updated 2009/12/01

Abstract

Counter automata are more powerful versions of finite-state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of \Zⁿ is accepted by a nondeterministic m-counter automaton if and only if m ≥ n.

Related

• One-Counter Automata with Counter Observability
• On the Linguistic Capacity of Real-Time Counter Automata
• Unboundedness problems for machines with reversal-bounded counters
• Store Languages of Turing Machines and Counter Machines
• Techniques for Showing the Decidability of the Boundedness Problem of Language Acceptors