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

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

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

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

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

Цитировать