Transforming two-way alternating finite automata to one-way nondeterministic automata

Viliam Geffert, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

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

Аннотация

It is proved that a two-way alternating finite automaton (2AFA) with n states can be transformed to an equivalent one-way nondeterministic finite automaton (1NFA) with f(n)=2Θ(n logn) states, and that this number of states is necessary in the worst case already for the transformation of a two-way automaton with universal nondeterminism (2Π1FA) to a 1NFA. At the same time, an n-state 2AFA is transformed to a 1NFA with (2 n -1)2+1 states recognizing the complement of the original language, and this number of states is again necessary in the worst case. The difference between these two trade-offs is used to show that complementing a 2AFA requires at least Ω(n logn) states.

Язык оригиналаанглийский
Название основной публикацииMathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings
ИздательSpringer Nature
Страницы291-302
Число страниц12
ИзданиеPART 1
ISBN (печатное издание)9783662445211
DOI
СостояниеОпубликовано - 1 янв 2014
Событие39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 - Budapest, Венгрия
Продолжительность: 25 авг 201429 авг 2014

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
НомерPART 1
Том8634 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
СтранаВенгрия
ГородBudapest
Период25/08/1429/08/14

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Transforming two-way alternating finite automata to one-way nondeterministic automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать