Talk:Alternating finite automaton

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Stub-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
Note icon
This article has been automatically rated by a bot or other tool as Stub-Class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.


hi, i think this topic needs to be more complete. i am currently expanding this article. i'll appreciate any comment/suggestion/correction. so far i got started with the first part of formal definition. will expand more. thank you. Janechii 08:40, 18 January 2007 (UTC)

Hi Janechii, I read your article and i liked it but i want more information on alternating automata. Please edit some more information about the topic or just email me as soon as possible, my address is


There is a definition of "alternating finite automaton" in Pippenger, Nicholas (1997). Theories of Computability. Cambridge University Press. pp. 93–94. ISBN 0-521-55380-6. Zbl 0879.03013.  The definition is in terms of winning strategies in a game and it is not clear whether it is equivalent to the definition given here. There is also a definition in Jiri Wiedermann; Peter van Emde Boas; Mogens Nielsen, eds. (1999). Automata, Languages and Programming: 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999 Proceedings. Lecture Notes in Computer Science. 1644. Springer-Verlag. ISBN 3-540-66224-3.  This seems similar but again it is not quite clear that they are the same. Deltahedron (talk) 06:39, 13 October 2012 (UTC)