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

Original languageEnglish
Pages (from-to)161-178
Number of pages18
JournalFundamenta Informaticae
Volume109
Issue number2
DOIs
Publication statusPublished - 16 Sep 2011

Scopus subject areas

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

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