Tree automata with height constraints between brothers

Consultar RECERCAT

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/24225

Títol:	Tree automata with height constraints between brothers
Autor/a:	Creus López, Carles; Godoy Balil, Guillem
Altres autors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Abstract:	We define the tree automata with height constraints between brothers (TACBB H ). Constraints of equalities and inequalities between heights of siblings that restrict the applicability of the rules are allowed in TACBB H. These constraints allow to express natural tree languages like complete or balanced (like AVL) trees. We prove decidability of emptiness and finiteness for TACBB H, and also for a more general class that additionally allows to combine equality and disequality constraints between brothers. © 2014 Springer International Publishing Switzerland.
Abstract:	Peer Reviewed
Matèries:	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Information processing -Constraints -Emptiness -Finiteness -Tree-Automata -Informació--Sistemes d'emmagatzematge i recuperació
Drets:
Tipus de document:	Article - Versió publicada Objecte de conferència
Publicat per:	Springer
Compartir:

Arias Vicente, Marta; Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem

Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem; Ramos, Lander

Barguño, Luis; Creus López, Carles; Godoy Balil, Guillem; Jacquemard, Florent; Vacher, Camile

Creus López, Carles; Godoy Balil, Guillem; Massanes Basi, Francesc d'Assis; Tiwari, Ashish Kumar

Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem

Coordinació

Patrocini