No Access

STAR-FREE GEODESIC LANGUAGES FOR GROUPS

SUSAN HERMILLER

Department of Mathematics, University of Nebraska, Lincoln NE 68588-0130, USA

Search for more papers by this author

DEREK F. HOLT

Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK

Search for more papers by this author

, and

SARAH REES

School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK

Search for more papers by this author

https://doi.org/10.1142/S0218196707003603Cited by:2 (Source: Crossref)

Abstract

In this article we show that every group with a finite presentation satisfying one or both of the small cancellation conditions C′(1/6) and C′(1/4) - T(4) has the property that the set of all geodesics (over the same generating set) is a star-free regular language. Star-free regularity of the geodesic set is shown to be dependent on the generating set chosen, even for free groups. We also show that the class of groups whose geodesic sets are star-free with respect to some generating set is closed under taking graph (and hence free and direct) products, and includes all virtually abelian groups.

Keywords:

AMSC: 20F65 (primary), 20F06 (secondary), 20F10 (secondary), 20F67 (secondary), 68Q45 (secondary)

References

R. Charney and J. Meier, Math. Z. 248, 495 (2004). Crossref, Web of Science, Google Scholar
D. B. A. Epstein et al. , Word Processing in Groups ( Jones and Bartlett , Boston , 1992 ) . Crossref, Google Scholar
E. R. Green, Graph products of groups, PhD thesis, The University of Leeds (1990) . Google Scholar
S. Hermiller and J. Meier, J. Algebra 171, 230 (1995). Crossref, Web of Science, Google Scholar
J. E. Hopcroft , R. Motwani and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation , 2nd edn. ( Addison Wesley , Reading, MA , 2001 ) . Google Scholar
R. B. Howlett, Miscellaneous facts about Coxeter groups, Notes of Lectures Given at the ANU Group Actions Workshop (October, 1993), available fromhttp://www.maths.usyd.edu.au:8000/res/Algebra/How/anucox.html . Google Scholar
J. Loeffler, J. Meier and J. Worthington, Int. J. Algebra Comput. 12, 747 (2002). Link, Web of Science, Google Scholar
S. Margolis, private communication . Google Scholar
R. McNaughton and S. Papert , Counter-free Automata ( MIT Press , Cambridge, MA, London , 1971 ) . Google Scholar
W. Neumann and M. Shapiro, Invent. Math. 120, 259 (1995). Crossref, Web of Science, Google Scholar
J. E. Pin , Varieties of Formal Languages ( Plenum Publishing Corp. , New York , 1986 ) . Crossref, Google Scholar
L. Sabalka, Contemp. Math. 360, 133 (2004). Crossref, Google Scholar
H. Straubing , Finite Automata, Formal Logic, and Circuit Complexity ( Birkhäuser , Boston , 1994 ) . Crossref, Google Scholar
R. Strebel , Sur les groupes hyperboliques d'après Mikhael Gromov , Progress in Mathematics 83 , eds. E. Ghys and P. de la Harpe ( Birkhäuser Boston, Inc. , Boston, MA , 1990 ) . Google Scholar