Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Excessively duplicating patterns represent non-regular languages

Autor
Creus, C.; Godoy, G.; Ramos, L.
Tipus d'activitat
Article en revista
Revista
Information processing letters
Data de publicació
2014-03-01
Volum
114
Número
3
Pàgina inicial
85
Pàgina final
93
DOI
https://doi.org/10.1016/j.ipl.2013.11.010 Obrir en finestra nova
Projecte finançador
Métodos formales y algoritmos para el diseño de sistemas
Repositori
http://hdl.handle.net/2117/23504 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S002001901300286X Obrir en finestra nova
Resum
A constrained term pattern s:¿ represents the language of all instances of the term s satisfying the constraint ¿. For each variable in s, this constraint specifies the language of its allowed substitutions. Regularity of languages represented by sets of patterns has been studied for a long time. This problem is known to be co-NP-complete when the constraints allow each variable to be replaced by any term over a fixed signature, and EXPTIME-complete when the constraints restrict each variable ...
Citació
Creus, C.; Godoy, G.; Ramos, L. Excessively duplicating patterns represent non-regular languages. "Information processing letters", 01 Març 2014, vol. 114, núm. 3, p. 85-93.
Paraules clau
Pattern, Regular tree language, Theory of computation, Tree automaton, Tree homomorphism
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants