First-order properties of trees, star-free expressions, and aperiodicity

Uschi Heuter

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1991)

  • Volume: 25, Issue: 2, page 125-145
  • ISSN: 0988-3754

How to cite

top

Heuter, Uschi. "First-order properties of trees, star-free expressions, and aperiodicity." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.2 (1991): 125-145. <http://eudml.org/doc/92385>.

@article{Heuter1991,
author = {Heuter, Uschi},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {tree automata; tree languages; first-order definability},
language = {eng},
number = {2},
pages = {125-145},
publisher = {EDP-Sciences},
title = {First-order properties of trees, star-free expressions, and aperiodicity},
url = {http://eudml.org/doc/92385},
volume = {25},
year = {1991},
}

TY - JOUR
AU - Heuter, Uschi
TI - First-order properties of trees, star-free expressions, and aperiodicity
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 2
SP - 125
EP - 145
LA - eng
KW - tree automata; tree languages; first-order definability
UR - http://eudml.org/doc/92385
ER -

References

top
  1. 1. J. R. BÜCHI, Weak second-order arithmetic and finite automata, Z. math. Logik Grundlagen Math, 6, 1960, pp. 66-92. Zbl0103.24705MR125010
  2. 2. J. DONER, Tree acceptors and some of their applications, J. of Comp. and System Sci., 4, 1970, pp. 406-451. Zbl0212.02901MR287977
  3. 3. C. C. ELGOT, Decision problems of finite automata design and related arithmetics, Trans. Amer, Math. Soc., 98, 1961, pp. 21-52. Zbl0111.01102MR139530
  4. 4. F. GECSEG and M. STEINBY, "Tree Automata", Akademiai Kiado, Budapest, 1984. Zbl0537.68056MR735615
  5. 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. Zbl0644.68103MR935795
  6. 6. U. HEUTER, Zur Klassifizierung regulärer Baumsprachen, Dissertation an der RWTH, Aachen, 1989. 
  7. 7. U. HEUTER and D. NIWINSKI, A note on starfree tree languages (to appear), 1989. 
  8. 8. R. MCNAUGHTON and S. PAPERT, "Counter-free Automata", M.I.T.-Press, Cambridge, Mass., 1971. Zbl0232.94024MR371538
  9. 9. A. R. MEYER, A note on star-free events, J. Assoc. Comput. Mach., 16, 1969, pp. 220-225. Zbl0224.94060MR238624
  10. 10. J. G. ROSENSTEIN, "Linear Orderings", Academic Press, New York, 1982. Zbl0488.04002MR662564
  11. 11. M. P. SCHÜTZENBERGER, On monoids having only nontrivial subgroups, Inform. Contr., 8, 1965, pp. 190-194. Zbl0131.02001MR176883
  12. 12. W. THOMAS, Classifying regular events in symbolic logic, J. of Comput. and System Sci, 25, 1982, pp. 360-376. Zbl0503.68055MR684265
  13. 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. Zbl0557.68051MR787450
  14. 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. Zbl0157.02201MR224476

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.