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

Результат исследований: Научные публикации в периодических изданиях › статья

12 Цитирования (Scopus)

Аннотация

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

Язык оригинала	английский
Страницы (с-по)	161-178
Число страниц	18
Журнал	Fundamenta Informaticae
Том	109
Номер выпуска	2
DOI	https://doi.org/10.3233/FI-2011-502
Состояние	Опубликовано - 16 сен 2011

Предметные области Scopus

Математика и теория расчета
Информационные системы
Алгебра и теория чисел
Теоретические компьютерные науки

Доступ к документу

10.3233/FI-2011-502

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

Fingerprint Подробные сведения о темах исследования «On the state complexity of star of union and star of intersection». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

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