The word problem distinguishes counter languages

Consultar RECERCAT

dc.contributor.author	Cleary, Sean
dc.contributor.author	Elder, Murray
dc.contributor.author	Ostheimer, Gretchen
dc.contributor.author	Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica
dc.date	2006
dc.identifier	https://ddd.uab.cat/record/44067
dc.identifier	urn:oai:ddd.uab.cat:44067
dc.format	application/pdf
dc.language	eng
dc.publisher	Centre de Recerca Matemàtica
dc.relation	Centre de Recerca Matemàtica. Prepublicacions ;
dc.rights	open access
dc.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
dc.rights	https://creativecommons.org/licenses/by-nc-nd/2.5/
dc.subject	Llenguatges formals
dc.subject	Autòmats finits
dc.subject	Lingüística computacional
dc.title	The word problem distinguishes counter languages
dc.type	Article
dc.type	Prepublicació
dc.description.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 Zn is accepted by a nondeterministic m-counter automaton if and only if m >= n.

Cleary, Sean; Elder, Murray; Ostheimer, Gretchen

Cleary, Sean; Taback, Jennifer; Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica

Cleary, Sean; Taback, Jennifer; Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica

Burillo Puig, Josep; Cleary, Sean; Wiest, Bertold; Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica

Burillo Puig, Josep; Cleary, Sean; Stein, Melanie; Taback, Jennifer; Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica

Coordinación

Patrocinio