Standard

On the state complexity of star of union and star of intersection. / Jirásková, Galina; Okhotin, Alexander.

In: Fundamenta Informaticae, Vol. 109, No. 2, 16.09.2011, p. 161-178.

Research output: Contribution to journal › Article › peer-review

Harvard

Jirásková, G & Okhotin, A 2011, 'On the state complexity of star of union and star of intersection', Fundamenta Informaticae, vol. 109, no. 2, pp. 161-178. https://doi.org/10.3233/FI-2011-502

APA

Jirásková, G., & Okhotin, A. (2011). On the state complexity of star of union and star of intersection. Fundamenta Informaticae, 109(2), 161-178. https://doi.org/10.3233/FI-2011-502

Vancouver

Jirásková G, Okhotin A. On the state complexity of star of union and star of intersection. Fundamenta Informaticae. 2011 Sep 16;109(2):161-178. https://doi.org/10.3233/FI-2011-502

Author

Jirásková, Galina ; Okhotin, Alexander. / On the state complexity of star of union and star of intersection. In: Fundamenta Informaticae. 2011 ; Vol. 109, No. 2. pp. 161-178.

BibTeX

@article{79b0d5dfba9b48d6be35121fbabc1038,
title = "On the state complexity of star of union and star of intersection",
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 2m+n-1-2m-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 2mn 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).",
keywords = "combined operations, Descriptional complexity, finite automata, state complexity",
author = "Galina Jir{\'a}skov{\'a} and Alexander Okhotin",
year = "2011",
month = sep,
day = "16",
doi = "10.3233/FI-2011-502",
language = "English",
volume = "109",
pages = "161--178",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "2",

}

RIS

TY - JOUR

T1 - On the state complexity of star of union and star of intersection

AU - Jirásková, Galina

AU - Okhotin, Alexander

PY - 2011/9/16

Y1 - 2011/9/16

N2 - The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2m+n-1-2m-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 2mn 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).

AB - The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2m+n-1-2m-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 2mn 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).

KW - combined operations

KW - Descriptional complexity

KW - finite automata

KW - state complexity

UR - http://www.scopus.com/inward/record.url?scp=80052673146&partnerID=8YFLogxK

U2 - 10.3233/FI-2011-502

DO - 10.3233/FI-2011-502

M3 - Article

AN - SCOPUS:80052673146

VL - 109

SP - 161

EP - 178

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 2

ER -

ID: 41140645