We give an optimized construction of a tree automaton recognizing the k-parallel, k ≥ 1, tree concatenation of two regular tree languages. For tree automata with m and n states, respectively, the construction yields an upper bound (m+1/2)(n+1)⋅2nk−1 for the state complexity of k-parallel tree concatenation. We give a matching lower bound in the case k = 2. We conjecture that the upper bound is tight for all values of k. We also consider the special case where one of the tree languages is the set of all ranked trees and in this case establish a different tight state complexity bound for all values of k.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer n ≥1, there is a D&omega n;(Σ1) -complete tree language Ln accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree languages W(l,k), for Mostowski-Rabin indices (, k). We prove that the D&omega n;(Σ1) -complete tree languages Ln are Wadge reducible to the game tree languageW(l,k) for k-l≥2. In particular these languagesW(l,k) are not in any class D&omega n;(Σ1) for α<ωω
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We study caterpillar tree automata [3] that are restricted to enter any subtree at most one time (or k times). We show that, somewhat surprisingly, the deterministic one-visit automata can already, for instance, evaluate trees where the nodes represent some non-associative operations. We show that there exist regular tree languages that cannot be accepted by a one-visit automaton, thus proving a weakened form of a conjecture of Brüggemann-Klein and Wood [3]. We establish that the k-visit property is decidable.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.