World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

STAR-FREE GEODESIC LANGUAGES FOR GROUPS

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

    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.

    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 ScienceGoogle Scholar
    • D. B. A.   Epstein et al. , Word Processing in Groups ( Jones and Bartlett , Boston , 1992 ) . CrossrefGoogle 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 ScienceGoogle 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 ScienceGoogle 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 ScienceGoogle Scholar
    • J. E.   Pin , Varieties of Formal Languages ( Plenum Publishing Corp. , New York , 1986 ) . CrossrefGoogle Scholar
    • L. Sabalka, Contemp. Math. 360, 133 (2004). CrossrefGoogle Scholar
    • H.   Straubing , Finite Automata, Formal Logic, and Circuit Complexity ( Birkhäuser , Boston , 1994 ) . CrossrefGoogle 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
    Remember to check out the Most Cited Articles!

    Check out Algebra & Computation books in the Mathematics 2021 catalogue.