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: combined operations

Sortuj według:

Ogranicz wyniki do:

State Complexity of Combined Operations with Union, Intersection, Star and Reversal

Gao Y., Yu S

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

79-92

In this paper, we study the state complexities of four combined operations: [formula]. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.

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).