Affordable Access

Publisher Website

Alternating finite automata on ω-words

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
32
Issue
3
Identifiers
DOI: 10.1016/0304-3975(84)90049-5

Abstract

Abstract Alternating finite automata on ω-words are introduced as an extension of nondeterministic finite automata which process infinite sequences of symbols. The classes of ω-languages defined by alternating finite automata are investigated and characterized under four types of acceptance conditions. It is shown that for one type of acceptance condition alternation increases the power in comparison with nondeterminism and for other three acceptance conditions nondeterministic finite automata on ω-words have the same power as alternating ones.

There are no comments yet on this publication. Be the first to share your thoughts.