|
Title:
|
The word problem distinguishes counter languages
|
|
Author:
|
Cleary, Sean; Elder, Murray; Ostheimer, Gretchen
|
|
Other authors:
|
Centre de Recerca Matemàtica |
|
Resum:
|
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 Zn is accepted by a nondeterministic m-counter automaton if and only if m &= n. |
|
Publication date:
|
2006-06 |
|
Subject (UDC):
|
68 - Indústries, oficis i comerç d'articles acabats. Tecnologia cibernètica i automàtica |
|
Subject(s):
|
Llenguatges formals
Autòmats finits
Lingüística computacional |
|
Rights:
|
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/) |
|
Document type:
|
Preprint |
|
Share:
|
|
