Utilizad este identificador para citar o enlazar este documento: http://hdl.handle.net/2072/5334

The word problem distinguishes counter languages
Cleary, Sean; Elder, Murray; Ostheimer, Gretchen
Centre de Recerca Matemàtica
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.
06-2006
68 - Indústries, oficis i comerç d'articles acabats. Tecnologia cibernètica i automàtica
Llenguatges formals
Autòmats finits
Lingüística computacional
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/)
Edición preliminar
Centre de Recerca Matemàtica
Prepublicacions del Centre de Recerca Matemàtica;695
         

Documentos con el texto completo de este documento

Ficheros Tamaño Formato
Pr695.pdf 161.6 KB PDF

Mostrar el registro completo del ítem

Documentos relacionados