Tree automata with constraints and tree homomorphisms

Abstract

Automata are a widely used formalism in computer science as a concise representation for sets. They are interesting from a theoretical and practical point of view. This work is focused on automata that are executed on tree-like structures, and thus, define sets of trees. Moreover, we tackle automata that are enhanced with the possibility to check (dis)equality constraints, i.e., where the automata are able to test whether specific subtrees of the input tree are equal or different. Two distinct mechanisms are considered for defining which subtrees have to be compared in the evaluation of the constraints. First, in local constraints, a transition of the automaton compares subtrees pending at positions relative to the position of the input tree where the transition takes place. Second, in global constraints, the subtrees tested are selected depending on the state to which they are evaluated by the automaton during a computation. In the setting of local constraints, we introduce tree automata with height constraints between brothers. These constraints are predicates on sibling subtrees that, instead of evaluating whether the subtrees are equal or different, compare their respective heights. Such constraints allow to express natural tree sets like complete or balanced (like AVL) trees. We prove decidability of emptiness and finiteness for these automata, and also for their combination with the tree automata with (dis)equality constraints between brothers of Bogaert and Tison (1992). We also define a new class of tree automata with constraints that allows arbitrary local disequality constraints and a particular kind of local equality constraints. We prove decidability of emptiness and finiteness for this class in exponential time. As a consequence, we obtain several EXPTIME-completeness results for problems on images of regular tree sets under tree homomorphisms, like set inclusion, finiteness of set difference, and regularity (also called HOM problem). In the setting of global constraints, we study the class of tree automata with global reflexive disequality constraints. Such kind of constraints is incomparable with the original notion of global disequality constraints of Filiot et al. (2007): the latter restricts disequality tests to only compare subtrees evaluated to distinct states, whereas in our model it is possible to test that all subtrees evaluated to the same given state are pairwise different. Our tests correspond to monadic key constraints, and thus, can be used to characterize unique identifiers, a typical integrity constraint of XML schemas. We study the emptiness and finiteness problems for these automata, and obtain decision algorithms that take triple exponential time.

Los autómatas son un formalismo ampliamente usado en ciencias de la computación como una representación concisa para conjuntos, siendo interesantes tanto a nivel teórico como práctico. Este trabajo se centra en autómatas que se ejecutan en estructuras arbóreas, y por tanto, definen conjuntos de árboles. En particular, tratamos autómatas que han sido extendidos con la posibilidad de comprobar restricciones de (des)igualdad, es decir, autómatas que son capaces de comprobar si ciertos subárboles del árbol de entrada son iguales o diferentes. Se consideran dos mecanismos distintos para definir qué subárboles deben ser comparados en la evaluación de las restricciones. Primero, en las restricciones locales, una transición del autómata compara subárboles que penden en posiciones relativas a la posición del árbol de entrada en que se aplica la transición. Segundo, en restricciones globales, los subárboles comparados se seleccionan dependiendo del estado al que son evaluados por el autómata durante el cómputo. En el marco de restricciones locales, introducimos los autómatas de árboles con restricciones de altura entre hermanos. Estas restricciones son predicados entre subárboles hermanos que, en lugar de evaluar si los subárboles son iguales o diferentes, comparan sus respectivas alturas. Este tipo de restricciones permiten expresar conjuntos naturales de árboles, tales como árboles completos o equilibrados (como AVL). Demostramos la decidibilidad de la vacuidad y finitud para este tipo de autómata, y también para su combinación con los autómata con restricciones de (des)igualdad entre hermanos de Bogaert y Tison (1992). También definimos una nueva clase de autómatas con restricciones que permite restricciones locales de desigualdad arbitrarias y un tipo particular de restricciones locales de igualdad. Demostramos la decidibilidad de la vacuidad y finitud para esta clase, con un algoritmo de tiempo exponencial. Como consecuencia, obtenemos varios resultados de EXPTIME-completitud para problemas en imágenes de conjuntos regulares de árboles a través de homomorfismos de árboles, tales como inclusión de conjuntos, finitud de diferencia de conjuntos, y regularidad (también conocido como el problema HOM). En el marco de restricciones globales, estudiamos la clase de autómatas de árboles con restricciones globales de desigualdad reflexiva. Este tipo de restricciones es incomparable con la noción original de restricciones globales de desigualdad de Filiot et al. (2007): éstas últimas restringen las comprobaciones de desigualdad a subárboles que se evalúen a estados distintos, mientras que en nuestro modelo es posible comprobar que todos los subárboles que se evalúen a un mismo estado dado son dos a dos distintos. Nuestras restricciones corresponden a restricciones de clave, y por tanto, pueden ser usadas para caracterizar identificadores únicos, una restricción de integridad típica de los XML Schemas. Estudiamos los problemas de vacuidad y finitud para estos autómatas, y obtenemos algoritmos de decisión con coste temporal triplemente exponencial.