The word problem distinguishes counter languages
Cleary, Sean
Elder, Murray
Ostheimer, Gretchen
Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica

Publicación: Centre de Recerca Matemàtica 2006
Descripción: 7 p.
Resumen: 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.
Derechos: 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 Creative Commons
Lengua: Anglès
Colección: Centre de Recerca Matemàtica. Prepublicacions
Colección: Prepublicacions del Centre de Recerca Matemàtica ; 695
Documento: article ; submittedVersion
Materia: Llenguatges formals ; Autòmats finits ; Lingüística computacional

Adreça alternativa: https://hdl.handle.net/2072/5334


7 p, 157.8 KB

El registro aparece en las colecciones:
Documentos de investigación > Prepublicacions

 Registro creado el 2009-07-13, última modificación el 2020-11-21



   Favorit i Compartir