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

Viliam Geffert, Alexander Okhotin

Research output

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings
PublisherSpringer Nature
Pages291-302
Number of pages12
EditionPART 1
ISBN (Print)9783662445211
DOIs
Publication statusPublished - 1 Jan 2014
Event39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 - Budapest
Duration: 25 Aug 201429 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8634 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
CountryHungary
CityBudapest
Period25/08/1429/08/14

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Transforming two-way alternating finite automata to one-way nondeterministic automata'. Together they form a unique fingerprint.

Cite this