Constructions for alternating finite automataFootnote^∗

^∗This work was supported by the natural sciences and engineering research council of canada, Grants OGP0000243 and OGP0041630.

References

• Chandra A. K. Kozen D. C. Stockmeyer L. J. IBM T. J. Watson Research Center Yorktown Heights, NY 1978 Alternation. Res. Rept. R7489
   Google Scholar
• Chandra , A.K. , Kozen , D.C. and Stockmeyer , L.J. 1981 . Alternation. JACM , 28 : 114 – 133 .
   Web of Science ®Google Scholar
• Change , J.H. , Ibarra , O.H. and Ravikumar , B. 1987 . Some observations concerning alternating turing machines using small space . Inform. Process. Lett , 25 : 1 – 9 .
   Web of Science ®Google Scholar
• Hopcroft , J.E. and Ullman , J.D. 1979 . Introduction to Automata Theory, Languages, and Computation , Reading : Addison-Wesley .
   Google Scholar
• Hromkovič , H. 1985 . Alternating multicounter machines with constant number of reversals . Information Processing Letters , 21 : 7 – 9 .
   Web of Science ®Google Scholar
• Hromkovič , J. 1985 . On the power of alternation in Automata Theory . J. of Comp, and Syst. Sci , 31 : 28 – 39 .
   Web of Science ®Google Scholar
• Inoue , K. , Takanami , I. and Tanaguchi , H. . Two-dimensional alternating turing machines . Proc. 14th Ann. ACM Symp . pp. 37 – 46 . New York : ACM . On Theory of Computing
   Google Scholar
• Inoue , K. , Takanami , I. and Tanaguchi , H. 1982 . A note on alternating on-line turing machines . Inform. Process. Lett , 15 : 164 – 168 .
   Web of Science ®Google Scholar
• King , K.N. 1980 . Restricted Forms of Alternation , Berkeley : University of California . Ph.D. Dissertation
   Google Scholar
• Lindsay , P.A. 1986 . Alternation and co-type turing acceptors . Theoret. Comput. Sci , 43 : 107 – 115 .
   Web of Science ®Google Scholar
• Ladner , R.E. , Lipton , R.J and Stockmeyer , L.J . 1978 . Alternating pushdown automata . Proc. 19th IEEE Symp . 1978 . pp. 92 – 106 . on Foundations of Computer Science, IEEE
   Google Scholar
• Paul , W.J. , Prauss , E.J. and Reischuck , R. 1980 . On Alternation . Acta Inform , 14 : 243 – 255 .
   Web of Science ®Google Scholar
• Ruzzo , W.L. 1980 . Tree-size bounded alternation . J. Comput. System Sci , 21 : 218 – 235 .
   Web of Science ®Google Scholar
• Sudborough , I.H. 1980 . Efficient algorithms for path system problems and applications to alternating and time-space complexity classes . Proc 21st IEEE Ann. Symp . 1980 . pp. 62 – 72 . On Foundations of Computer Science, IEEE
   Google Scholar
• Wagner , K. and Wechsung , G. 1986 . Computational Complexity , Berlin : VEB Deutscher Verlag der Wissenschaften .
   Google Scholar
• Wood , D. 1987 . Theory of Computation , New York : Harper & Row . 2nd printing, Wiley, 1988
   Google Scholar