Yield-languages recognized by alternating tree recognizers
Salomaa, Kai
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 319-339 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1988-01-01
@article{ITA_1988__22_3_319_0,
     author = {Salomaa, Kai},
     title = {Yield-languages recognized by alternating tree recognizers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {22},
     year = {1988},
     pages = {319-339},
     mrnumber = {963595},
     zbl = {0656.68087},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1988__22_3_319_0}
}

Salomaa, Kai. Yield-languages recognized by alternating tree recognizers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) pp. 319-339. http://gdmltest.u-ga.fr/item/ITA_1988__22_3_319_0/

1. A. Aho, Indexed Grammars. An Extension of Context-free Grammars, J. Assoc. Comput. Mach., Vol. 15, 1968, pp. 647-671. | MR 258547 | Zbl 0175.27801

2. A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation, J. Assoc. Comput. Mach., Vol. 28, 1981, pp. 114-133. | MR 603186 | Zbl 0473.68043

3. F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984. | MR 735615 | Zbl 0537.68056

4. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Language, and Computation, Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

5. R. E. Ladner, R. J. Lipton and L. J. Stockmeyer, Alternating Pushdown and Stack Automata, SIAM J. Comput., Vol. 13, 1984, pp. 135-155. | MR 731032 | Zbl 0538.68039

6. D. E. Muller, A. Saoudi and P. E. Schupp, Alternating Automata, the Weak Monadic Theory of the Tree, and its Complexity, Proc. of 13th ICALP, Lect. Notes Comput. Sci., Vol. 226, 1986, pp. 275-283. | MR 864690 | Zbl 0617.03020

7. M. Penttonen, One-sided and Two-sided Context in Formal Grammars, Inf. Control, Vol. 25, 1974, pp. 371-392. | MR 356593 | Zbl 0282.68035

8. W. C. Rounds, Mappings and Grammars on Trees, Math. Systems Theory, Vol. 4, 1970, pp. 257-287. | MR 269440 | Zbl 0203.30103

9. A. Salomaa, Formal Languages, Academic Press, NewYork, 1973. | MR 438755 | Zbl 0262.68025

10. K. Salomaa, Alternating Botton-up Tree Recognizers, Proc. of llth CAAP, Lect. Notes Comput. Sci., Vol. 214, 1986, pp. 158-171. | MR 848792 | Zbl 0599.68059

11. G. Slutzki, Alternating Tree Automa, Proc. of 8th CAAP, Lect. Notes Comput. Sci., Vol. 159, 1983, pp. 392-404. | MR 744224 | Zbl 0523.68043