Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: deterministic finite automaton

Sortuj według:

Ogranicz wyniki do:

Transition Complexity of Incomplete DFAs

Gao Y., Salomaa K., Yu S

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

143-158

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.

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

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.