An application of the Ehrenfeucht-Fraisse game in formal language theory

Wolfgang Thomas

Mémoires de la Société Mathématique de France (1984)

  • Volume: 16, page 11-21
  • ISSN: 0249-633X

How to cite

top

Thomas, Wolfgang. "An application of the Ehrenfeucht-Fraisse game in formal language theory." Mémoires de la Société Mathématique de France 16 (1984): 11-21. <http://eudml.org/doc/94847>.

@article{Thomas1984,
author = {Thomas, Wolfgang},
journal = {Mémoires de la Société Mathématique de France},
keywords = {star-free languages; dot-depth hierarchy; prefix types of first order formulas},
language = {eng},
pages = {11-21},
publisher = {Société mathématique de France},
title = {An application of the Ehrenfeucht-Fraisse game in formal language theory},
url = {http://eudml.org/doc/94847},
volume = {16},
year = {1984},
}

TY - JOUR
AU - Thomas, Wolfgang
TI - An application of the Ehrenfeucht-Fraisse game in formal language theory
JO - Mémoires de la Société Mathématique de France
PY - 1984
PB - Société mathématique de France
VL - 16
SP - 11
EP - 21
LA - eng
KW - star-free languages; dot-depth hierarchy; prefix types of first order formulas
UR - http://eudml.org/doc/94847
ER -

References

top
  1. J.A. Brzozowksi, R. Knast (1978) : The dot-depth hierarchy of star-free languages is infinite, J.Comput.System Sci. 16, 37-55. Zbl0368.68074MR57 #11183
  2. R.S. Cohen, J.A. Brzozowski (1971) : Dot-depth of star-free events, J.Comput.System Sci. 5, 1-16. Zbl0217.29602MR46 #8783
  3. S. Eilenberg (1976) : "Automata, Languages, and Machines", Vol.B, Academic Press, New York. Zbl0359.94067MR58 #26604b
  4. R. Fraissé (1972) : "Cours de Logique Mathématique", Tome 2, Gauthier-Villars, Paris. Zbl0247.02003
  5. R. McNaughton, S. Papert (1971) : "Counter-free Automata", MIT Press, Cambridge, Mass. Zbl0232.94024MR51 #7756
  6. J.E. Pin (1984a) : Hierarchies de concaténation, RAIRO-Informatique Théorique (to appear). Zbl0559.68062
  7. J.E. Pin (1984b) : "Variétés de langages formels", Masson, Paris (in press). Zbl0636.68093MR86a:68058
  8. J.G. Rosenstein (1982) : "Linear Orderings", Academic Press, New York. Zbl0488.04002
  9. H. Straubing (1981) : A generalization of the Schützenberger product of finite monoids, Theor.Comput. Sci. 13, 107-110. Zbl0456.20048MR82a:20079
  10. W. Thomas (1982) : Classifying regular events in symbolic logic, J.Comput.System Sci. 25, 360-376. Zbl0503.68055MR85a:03053

Citations in EuDML Documents

top
  1. F. Blanchet-Sadri, On dot-depth two
  2. Victor L. Selivanov, Hierarchies and reducibilities on regular languages related to modulo counting
  3. Victor L. Selivanov, Hierarchies and reducibilities on regular languages related to modulo counting
  4. F. Blanchet-Sadri, On semidirect and two-sided semidirect products of finite 𝒥 trivial monoids
  5. Jean-Eric Pin, Pascal Weil, A conjecture on the concatenation product
  6. Jean-Eric Pin, Pascal Weil, A conjecture on the concatenation product

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.