First-order properties of trees, star-free expressions, and aperiodicity
Heuter, Uschi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 125-145 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1991-01-01
@article{ITA_1991__25_2_125_0,
     author = {Heuter, Uschi},
     title = {First-order properties of trees, star-free expressions, and aperiodicity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {125-145},
     mrnumber = {1110980},
     zbl = {0741.68065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1991__25_2_125_0}
}

Heuter, Uschi. First-order properties of trees, star-free expressions, and aperiodicity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) pp. 125-145. http://gdmltest.u-ga.fr/item/ITA_1991__25_2_125_0/

1. J. R. Büchi, Weak second-order arithmetic and finite automata, Z. math. Logik Grundlagen Math, 6, 1960, pp. 66-92. | MR 125010 | Zbl 0103.24705

2. J. Doner, Tree acceptors and some of their applications, J. of Comp. and System Sci., 4, 1970, pp. 406-451. | MR 287977 | Zbl 0212.02901

3. C. C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer, Math. Soc., 98, 1961, pp. 21-52. | MR 139530 | Zbl 0111.01102

4. F. Gecseg and M. Steinby, "Tree Automata", Akademiai Kiado, Budapest, 1984. | MR 735615 | Zbl 0537.68056

5. U. Heuter, First-order properties of fmite trees, star-free expressions and aperiodicity, Proc. 5th STACS, R. Cori and M. Wirsing, Eds., L.N.C.S., 294, 1988, pp. 136-149. | MR 935795 | Zbl 0644.68103

6. U. Heuter, Zur Klassifizierung regulärer Baumsprachen, Dissertation an der RWTH, Aachen, 1989.

7. U. Heuter and D. Niwinski, A note on starfree tree languages (to appear), 1989.

8. R. Mcnaughton and S. Papert, "Counter-free Automata", M.I.T.-Press, Cambridge, Mass., 1971. | MR 371538 | Zbl 0232.94024

9. A. R. Meyer, A note on star-free events, J. Assoc. Comput. Mach., 16, 1969, pp. 220-225. | MR 238624 | Zbl 0224.94060

10. J. G. Rosenstein, "Linear Orderings", Academic Press, New York, 1982. | MR 662564 | Zbl 0488.04002

11. M. P. Schützenberger, On monoids having only nontrivial subgroups, Inform. Contr., 8, 1965, pp. 190-194. | MR 176883 | Zbl 0131.02001

12. W. Thomas, Classifying regular events in symbolic logic, J. of Comput. and System Sci, 25, 1982, pp. 360-376. | MR 684265 | Zbl 0503.68055

13. W. Thomas, Logical aspects in the study of tree languages, Ninth colloquium on trees in algebra and programming, B. Courcelle Ed., Cambridge Univ. Press, 1984, pp. 31-51. | MR 787450 | Zbl 0557.68051

14. J. W. Thatcher and J. B. Wright, Generalized finite automata with an application to a decision problem of second-order logic, Math. Syst Theory, 2, 1968, pp. 57-82. | MR 224476 | Zbl 0157.02201