2024-03-28T15:06:26Zhttps://www.tdx.cat/oai/requestoai:www.tdx.cat:10803/3940772020-10-30T13:38:09Zcom_10803_183col_10803_669774
nam a 5i 4500
Tree automata with constraints and tree homomorphisms
[Barcelona] :
Universitat Politècnica de Catalunya,
2016
Accés lliure
http://hdl.handle.net/10803/394077
cr |||||||||||
AAMMDDs2016 sp ||||fsm||||0|| 0 eng|c
Creus López, Carles,
autor
1 recurs en línia (137 pàgines)
Tesi
Doctorat
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
2016
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Tesis i dissertacions electròniques
Godoy Balil, Guillem,
supervisor acadèmic
TDX
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.
p
ES-BaCBU
cat
rda
ES-BaCBU
text
txt
rdacontent
informàtic
c
rdamedia
recurs en línia
cr
rdacarrier