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

Galina Jirásková; Alexander Okhotin

doi:10.3233/FI-2011-502

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

Galina Jirásková, Alexander Okhotin

Research output

12 Citations (Scopus)

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

Original language	English
Pages (from-to)	161-178
Number of pages	18
Journal	Fundamenta Informaticae
Volume	109
Issue number	2
DOIs	https://doi.org/10.3233/FI-2011-502
Publication status	Published - 16 Sep 2011

Scopus subject areas

Computational Theory and Mathematics
Information Systems
Algebra and Number Theory
Theoretical Computer Science

Access to Document

10.3233/FI-2011-502

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

Fingerprint Dive into the research topics of 'On the state complexity of star of union and star of intersection'. Together they form a unique fingerprint.

Cite this

@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",

}

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 -