Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2016

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

State Complexity of Basic Operations on Non-Returning Regular Languages

Eom H.-S., Han Y.-S., Jirásková G.

Fundamenta Informaticae

2016

Vol. 144, nr 2

161--182

We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reverse, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also study the unary case.