• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the State Complexity of Star of Union and Star of Intersection

Galina Jiraskova, Alexander Okhotin, On the State Complexity of Star of Union and Star of Intersection. TUCS Technical Reports 825, Turku Centre for Computer Science, 2007.

Abstract:

The state complexity of the star of union
of an <i>m</i>-state DFA language and an <i>n</i>-state DFA language
is proved to be 2^{<i>m</i>+<i>n</i>&#8722;1} &#8722; 2^{<i>m</i>&#8722;1} &#8722; 2^{<i>n</i>&#8722;1} + 1
for every alphabet of at least two letters.
The state complexity of the star of intersection
is established as 3/4 2^<i>mn</i>
for every alphabet of six or more letters.
This improves the recent results of A. Salomaa, K. Salomaa and S. Yu.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tJiOk07a,
  title = {On the State Complexity of Star of Union and Star of Intersection},
  author = {Jiraskova, Galina and Okhotin, Alexander},
  number = {825},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {descriptional complexity, finite automata, state complexity, combined operations},
  ISBN = {978-952-12-1914-6},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication