The word problem distinguishes counter languages

Simple item page
dc.creatorCleary, Sean
dc.creatorElder, Murray
dc.creatorOstheimer, Gretchen
dc.date2006-06-17
dc.date.accessioned2026-07-07T07:17:23Z
dc.date.available2026-07-07T07:17:23Z
dc.descriptionCounter 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^n$ is accepted by a nondeterministic $m$-counter automaton if and only if $m \geq n$.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/math/0606415
dc.identifierhttp://arxiv.org/abs/math/0606415
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/113921
dc.subjectGroup Theory
dc.subject20F10, 68Q45
dc.titleThe word problem distinguishes counter languages
dc.typetext

Files

Collections

arXiv