Yield-languages recognized by alternating tree recognizers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1988)
- Volume: 22, Issue: 3, page 319-339
- ISSN: 0988-3754
Access Full Article
topHow to cite
topSalomaa, Kai. "Yield-languages recognized by alternating tree recognizers." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 22.3 (1988): 319-339. <http://eudml.org/doc/92311>.
@article{Salomaa1988,
author = {Salomaa, Kai},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {tree automata; alternating computations; formal languages; context- sensitive language; yield-language; tree language},
language = {eng},
number = {3},
pages = {319-339},
publisher = {EDP-Sciences},
title = {Yield-languages recognized by alternating tree recognizers},
url = {http://eudml.org/doc/92311},
volume = {22},
year = {1988},
}
TY - JOUR
AU - Salomaa, Kai
TI - Yield-languages recognized by alternating tree recognizers
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1988
PB - EDP-Sciences
VL - 22
IS - 3
SP - 319
EP - 339
LA - eng
KW - tree automata; alternating computations; formal languages; context- sensitive language; yield-language; tree language
UR - http://eudml.org/doc/92311
ER -
References
top- 1. A. AHO, Indexed Grammars. An Extension of Context-free Grammars, J. Assoc. Comput. Mach., Vol. 15, 1968, pp. 647-671. Zbl0175.27801MR258547
- 2. A. K. CHANDRA, D. C. KOZEN and L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., Vol. 28, 1981, pp. 114-133. Zbl0473.68043MR603186
- 3. F. GÉCSEG and M. STEINBY, Tree Automata, Akadémiai Kiadó, Budapest, 1984. Zbl0537.68056MR735615
- 4. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Language, and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
- 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. Zbl0538.68039MR731032
- 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. Zbl0617.03020MR864690
- 7. M. PENTTONEN, One-sided and Two-sided Context in Formal Grammars, Inf. Control, Vol. 25, 1974, pp. 371-392. Zbl0282.68035MR356593
- 8. W. C. ROUNDS, Mappings and Grammars on Trees, Math. Systems Theory, Vol. 4, 1970, pp. 257-287. Zbl0203.30103MR269440
- 9. A. SALOMAA, Formal Languages, Academic Press, NewYork, 1973. Zbl0262.68025MR438755
- 10. K. SALOMAA, Alternating Botton-up Tree Recognizers, Proc. of llth CAAP, Lect. Notes Comput. Sci., Vol. 214, 1986, pp. 158-171. Zbl0599.68059MR848792
- 11. G. SLUTZKI, Alternating Tree Automa, Proc. of 8th CAAP, Lect. Notes Comput. Sci., Vol. 159, 1983, pp. 392-404. Zbl0523.68043MR744224
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.