Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the State Complexity of Star of Union and Star of Intersection

Jiraskova G., Okhotin A.

Fundamenta Informaticae

2011

Vol. 109, nr 2

161-178

The state complexity of the star of union of anm-state DFA language and an n-state DFA language is proved to be 2m+n-1 - 2m-1 - 2n-1 +1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as [...} for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu ("State complexity of combined operations", Theoret. Comput. Sci., 383 (2007) 140–152).