A1 Refereed original research article in a scientific journal
On the State Complexity of Star of Union and Star of Intersection
Authors: Jiraskova G, Okhotin A
Publisher: IOS PRESS
Publication year: 2011
Journal: Fundamenta Informaticae
Journal name in source: FUNDAMENTA INFORMATICAE
Journal acronym: FUND INFORM
Number in series: 2
Volume: 109
Issue: 2
First page : 161
Last page: 178
Number of pages: 18
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2011-502(external)
Abstract
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).
UTU Research Portal