Wyniki wyszukiwania - BazTech

1

State Complexity of k-Parallel Tree Concatenation

Han Y.-S., Ko S.-K., Salomaa K.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

185--199

EN

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

Transformations Between Different Models of Unranked Bottom-Up Tree Automata

Piao X., Salomaa K.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 4

405-424

EN

We consider the representational state complexity of unranked tree automata. The bottomup computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT’05, LNCS 3623, pp. 68–79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata

3

The Monadic Second-order Logic Evaluation Problem on Finite Colored Trees: a Database-theoretic Approach

Foustoucos E., Kalantzi L.

Fundamenta Informaticae

|

2009

|

Vol. 92, nr 3

193-231

EN

We model the monadic second-order logic (MSO) evaluation problem on finite colored trees in a purely database theoretic framework, based on the well-known MSO-automata connection: we reduce the problem to an acyclic conjunctive query evaluation problem on the one hand and to a monadic datalog evaluation problem on the other hand. This approach offers the possibility to solve the MSO problem using optimized evaluation methods for relational algebra expressions and for datalog programs (such as Yannakakis algorithm [27] and the rewriting method using resolutionbased filtering referred to as "magic sets" method in [3]): we use these methods for evaluating our queries and giving estimates of their complexity. This is the first time, to our knowledge, that a solution to the MSO evaluation problem related to relational algebra is given; furthermore, thanks to this reduction, we prove that the automata-based algorithm given in [8] constitutes a particular "instance" of Yannakakis algorithm. Besides the optimized database methods that we propose for solving the MSO evaluation problem, our results prove that MSO-definable queries over colored trees are datalog-definable; this result subsumes the corresponding result in [12] which states that unary MSO queries are monadic datalog-definable and it also subsumes the well-known result that any MSO-definable class of trees is monadic datalog-definable.

4

Products of Tree Automata with an Application to Temporal Logic

Ésik Z., Iván S.

Fundamenta Informaticae

|

2008

|

Vol. 82, nr 1-2

61-78

EN

We introduce the notion of the Moore product of tree automata as a special case of the cascade product. We give an algebraic characterization of the expressive power of certain CTL-like temporal logics based on the notion of varieties of finite tree automata closed under the Moore product.

5

One-Visit Caterpillar Tree Automata

Okhotin A., Salomaa K., Domaratzki M.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 4

361-375

EN

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.

6

Distinguishability, simulation and universality of Moore

Jurvanen E., Lipponen M.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

79-91

EN

We extend the notions of distinguishability of states, simulation and universality of string automata to tree automata of Moore type. In particular, we prove that for each finite class of tree automata satisfying certain conditions, there is a unique minimal universal tree automaton. The transfer from strings to rees brings new aspects but also adds difficulties in generalizing classical Moore results.

7

On the size of stack and synchronization alphabets of tree automata

Rahonis G., Salomaa K.

Fundamenta Informaticae

|

1998

|

Vol. 36, nr 1

57-69

EN

We consider classes of forests defined by synchronized and pushdown tree automata having a fixed size of , respectively, synchronization or pushdown alphabet. We show that such families have nice properties, for instance, they from either a sheaf or a strict alphabetic cone of forests. Furthermore, for the (deterministic and nondeterministic) synchronized tree automata and the real-time pushdown tree automata we obtain a strict infinite forest hierarchy with respect to the alphabet size.