Emptiness and finiteness for tree automata with global reflexive disequality constraints

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/22680

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Creus López, Carles
dc.contributor.author	Gascón Caro, Adrià
dc.contributor.author	Godoy Balil, Guillem
dc.date	2013-12-01
dc.identifier.citation	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.
dc.identifier.citation	0168-7433
dc.identifier.citation	10.1007/s10817-012-9270-5
dc.identifier.uri	http://hdl.handle.net/2117/22680
dc.language.iso	eng
dc.relation	http://link.springer.com/article/10.1007%2Fs10817-012-9270-5
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Sistemes d'informació
dc.subject	Decision problems
dc.subject	Disequality constraints
dc.subject	Global constraints
dc.subject	Tree automata
dc.title	Emptiness and finiteness for tree automata with global reflexive disequality constraints
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	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 finiteness problem remains unknown. In this paper, we consider the particular case of tree automata with global constraints when the constraint is a conjunction of disequalities between states, and the disequality predicate is forced to be reflexive. This restriction is significant in the context of XML definitions with monadic key constraints. We prove that emptiness and finiteness are decidable in triple exponential time for this kind of automata. © 2012 Springer Science+Business Media Dordrecht.
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author