A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the State Complexity of Star of Union and Star of Intersection
Tekijät: Jiraskova G, Okhotin A
Kustantaja: IOS PRESS
Julkaisuvuosi: 2011
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Numero sarjassa: 2
Vuosikerta: 109
Numero: 2
Aloitussivu: 161
Lopetussivu: 178
Sivujen määrä: 18
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2011-502
Tiivistelmä
The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2(m+n-1) - 2(m-1) - 2(n-1) + 1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2(mn) 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).
The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2(m+n-1) - 2(m-1) - 2(n-1) + 1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2(mn) 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).
Turun yliopiston Tutkimustietojärjestelmän portaali