Introduction

This document is a web version of some talks I have given on on connections between group theory and formal languages. The talks were presented originally at the Graduate Center of the City University of New York in October 1999 and in revised form at the Workshop on Groups and Languages at Neuchatel in June 2000.

No knowledge of formal languages is assumed. Several books devoted completely or in large part to that subject and written from various points of view are listed below. There are substantial applications of language theory to semigroups and monoids, but they are not treated here; consult [1], [4], [6] and [10]. Much of the material presented here is taken from [7], which is accessible through my web page.

If your browser cannot display the pdf files which follow, you can use Acrobat Reader or Ghostscript, both of which are free.

Bob Gilman
rgilman@stevens-tech.edu

References

  1. R. Book and F. Otto, String Rewriting Systems, Springer Verlag, 1993.
  2. J. Conway, Regular Algebra and Finite Machines, Chapman and Hall, 1971.
  3. J. Dassow and G. Paun, Regulated Rewriting in Formal Language Theory, Springer Verlag, 1989.
  4. S. Eilenberg, Automata, Languages and Machines, vols. A and B, Academic Press, New York, 1974.
  5. R. Floyd and R. Biegel, The Language of Machines, Computer Science Press, New York, 1994.
  6. J. Fountain, Semigroups, Formal Languages and Groups, Kluwer Academic Publishers, 1995.
  7. R. Gilman, Formal languages and infinite groups, in Geometric and Computational Perspectives on Infinite Groups, (Minneapolis, MN and New Brunswick, NJ, 1994), 27-51, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996.
  8. M. Harrison, Introduction to Formal Language Theory, Addison Wesley, 1978.
  9. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
  10. G. Lallement, Semigroups and Combinatorial Applications, John Wiley, 1979.
  11. M. Lothaire, Combinatorics on Words, Addison Wesley, 1983.
  12. G. E. Revesz, Introduction to Formal Languages, McGraw-Hill, 1983.
  13. G. Rozenberg and A. Salomaa eds., Handbook of Formal Languages, vols. 1-3, Springer Verlag, 1997.