PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote 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
Content available remote Transition Complexity of Incomplete DFAs
Gao Y., Salomaa K., Yu S
Fundamenta Informaticae
|
2011
|
Vol. 110, nr 1-4
143-158
EN
We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
3
Content available remote 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
4
Content available remote Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
Han Y-S., Salomaa K., Wood D.
Fundamenta Informaticae
|
2009
|
Vol. 90, nr 1-2
93-106
EN
We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.
5
Content available remote The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal
Gao Y., Salomaa K., Yu S
Fundamenta Informaticae
|
2008
|
Vol. 83, nr 1-2
75-89
EN
The state complexity of two combined operations, star of catenation and star of reversal, on regular languages is considered in this paper. Tight bounds are obtained for both combined operations. The results clearly show that the state complexity of a combined operation can be very different from the composition of the state complexities of its participating individual operations. A new approach for research in automata and formal language theory is also explained.
6
Content available remote Intercode Regular Languages
Han Y-S., Salomaa K., Wood D.
Fundamenta Informaticae
|
2007
|
Vol. 76, nr 1-2
113-128
EN
Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.
7
Content available remote Interpreted Trajectories
Domaratzki M., Rozenberg G., Salomaa K.
Fundamenta Informaticae
|
2006
|
Vol. 73, nr 1-2
81-97
EN
We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.
8
Content available remote Contextual Grammars with Uniform Sets of Trajectories
Okhotin A., Salomaa K.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
341-351
EN
A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.
9
Content available remote 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.
10
Content available remote 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.
first rewind previous Strona / 1 next fast forward last
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ć.