Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Emptiness and finiteness for tree automata with global reflexive disequality constraints

Autor
Creus, C.; Gascon, A.; Godoy, G.
Tipus d'activitat
Article en revista
Revista
Journal of automated reasoning
Data de publicació
2013-12-01
Volum
51
Número
4
Pàgina inicial
371
Pàgina final
400
DOI
https://doi.org/10.1007/s10817-012-9270-5 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/22680 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs10817-012-9270-5 Obrir en finestra nova
Resum
In recent years, several extensions of tree automata have been considered. Most of them are related with the capability of testing equality or disequality of certain subterms of the term evaluated by the automaton. In particular, tree automata with global constraints are able to test equality and disequality of subterms depending on the state to which they are evaluated. The emptiness problem is known decidable for this kind of automata, but with a non-elementary time complexity, and the finiten...
Citació
Creus, C.; Gascon, A.; Godoy, G. Emptiness and finiteness for tree automata with global reflexive disequality constraints. "Journal of automated reasoning", 01 Desembre 2013, vol. 51, núm. 4, p. 371-400.
Paraules clau
Decision problems, Disequality constraints, Global constraints, Tree automata
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants