LONDONMATHEMATICALSOCIETYSTUDENTTEXTS ManagingEditor:ProfessorD.Benson, DepartmentofMathematics,UniversityofAberdeen,UK 49 AnintroductiontoK-theoryforC*-algebras,M.RØRDAM,F.LARSEN&N.J.LAUSTSEN 50 Abriefguidetoalgebraicnumbertheory,H.P.F.SWINNERTON-DYER 51 Stepsincommutativealgebra:Secondedition,R.Y.SHARP 52 FiniteMarkovchainsandalgorithmicapplications,OLLEHA¨GGSTRO¨M 53 Theprimenumbertheorem,G.J.O.JAMESON 54 Topicsingraphautomorphismsandreconstruction,JOSEFLAURI&RAFFAELE SCAPELLATO 55 Elementarynumbertheory,grouptheoryandRamanujangraphs,GIULIANADAVIDOFF, PETERSARNAK&ALAINVALETTE 56 Logic,inductionandsets,THOMASFORSTER 57 IntroductiontoBanachalgebras,operatorsandharmonicanalysis,GARTHDALESetal 58 Computationalalgebraicgeometry,HALSCHENCK 59 Frobeniusalgebrasand2-Dtopologicalquantumfieldtheories,JOACHIMKOCK 60 Linearoperatorsandlinearsystems,JONATHANR.PARTINGTON 61 AnintroductiontononcommutativeNoetherianrings:Secondedition,K.R.GOODEARL& R.B.WARFIELD,JR 62 Topicsfromone-dimensionaldynamics,KARENM.BRUCKS&HENKBRUIN 63 Singularpointsofplanecurves,C.T.C.WALL 64 AshortcourseonBanachspacetheory,N.L.CAROTHERS 65 ElementsoftherepresentationtheoryofassociativealgebrasI,IBRAHIMASSEM,DANIEL SIMSON&ANDRZEJSKOWRON´SKI 66 Anintroductiontosievemethodsandtheirapplications,ALINACARMENCOJOCARU& M.RAMMURTY 67 Ellipticfunctions,J.V.ARMITAGE&W.F.EBERLEIN 68 Hyperbolicgeometryfromalocalviewpoint,LINDAKEEN&NIKOLALAKIC 69 LecturesonKa¨hlergeometry,ANDREIMOROIANU 70 Dependencelogic,JOUKUVA¨A¨NA¨NEN 71 ElementsoftherepresentationtheoryofassociativealgebrasII,DANIELSIMSON& ANDRZEJSKOWRON´SKI 72 ElementsoftherepresentationtheoryofassociativealgebrasIII,DANIELSIMSON& ANDRZEJSKOWRON´SKI 73 Groups,graphsandtrees,JOHNMEIER 74 RepresentationtheoremsinHardyspaces,JAVADMASHREGHI 75 Anintroductiontothetheoryofgraphspectra,DRAGOSˇCVETKOVIC´,PETER ROWLINSON&SLOBODANSIMIC´ 76 NumbertheoryinthespiritofLiouville,KENNETHS.WILLIAMS 77 Lecturesonprofinitetopicsingrouptheory,BENJAMINKLOPSCH,NIKOLAYNIKOLOV& CHRISTOPHERVOLL 78 Cliffordalgebras:Anintroduction,D.J.H.GARLING 79 IntroductiontocompactRiemannsurfacesanddessinsd’enfants,ERNESTOGIRONDO& GABINOGONZA´LEZ-DIEZ 80 TheRiemannhypothesisforfunctionfields,MACHIELVANFRANKENHUIJSEN 81 Numbertheory,Fourieranalysisandgeometricdiscrepancy,GIANCARLOTRAVAGLINI 82 Finitegeometryandcombinatorialapplications,SIMEONBALL 83 Thegeometryofcelestialmechanics,HANSJO¨RGGEIGES 84 Randomgraphs,geometryandasymptoticstructure,MICHAELKRIVELEVICHetal 85 Fourieranalysis:PartI–Theory,ADRIANCONSTANTIN 86 Dispersivepartialdifferentialequations,M.BURAKERDOG˘AN&NIKOLAOSTZIRAKIS 87 Riemannsurfacesandalgebraiccurves,R.CAVALIERI&E.MILES 88 Groups,languagesandautomata,DEREKF.HOLT,SARAHREES&CLAASE.RO¨VER LondonMathematicalSocietyStudentTexts88 Groups, Languages and Automata DEREK F. HOLT UniversityofWarwick SARAH REES UniversityofNewcastleuponTyne CLAAS E. RO¨ VER NationalUniversityofIreland,Galway UniversityPrintingHouse,CambridgeCB28BS,UnitedKingdom OneLibertyPlaza,20thFloor,NewYork,NY10006,USA 477WilliamstownRoad,PortMelbourne,VIC3207,Australia 4843/24,2ndFloor,AnsariRoad,Daryaganj,Delhi-110002,India 79AnsonRoad,#06-04/06,Singapore079906 CambridgeUniversityPressispartoftheUniversityofCambridge. ItfurtherstheUniversity’smissionbydisseminatingknowledgeinthepursuitof education,learningandresearchatthehighestinternationallevelsofexcellence. www.cambridge.org Informationonthistitle:www.cambridge.org/9781107152359 DOI:10.1017/9781316588246 (cid:2)c DerekF.Holt,SarahReesandClaasE.Ro¨ver2017 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2017 PrintedintheUnitedKingdombyClays,StIvesplc AcataloguerecordforthispublicationisavailablefromtheBritishLibrary. ISBN978-1-107-15235-9Hardback ISBN978-1-316-60652-0Paperback CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyof URLsforexternalorthird-partyInternetWebsitesreferredtointhispublication anddoesnotguaranteethatanycontentonsuchWebsitesis,orwillremain, accurateorappropriate. Contents Preface pageix PARTONE INTRODUCTION 1 1 Grouptheory 3 1.1 Introductionandbasicnotation 3 1.2 Generators,congruencesandpresentations 5 1.3 Decisionproblems 7 1.4 SubgroupsandSchreiergenerators 8 1.5 Combininggroups 10 1.6 Cayleygraphs 20 1.7 Quasi-isometries 23 1.8 Endsofgraphsandgroups 25 1.9 Smallcancellation 26 1.10 Someinterestingfamiliesofgroups 28 2 Formallanguagesandautomatatheory 36 2.1 Languages,automataandgrammars 36 2.2 Typesofautomata 38 2.3 Moreongrammars 50 2.4 Syntacticmonoids 51 2.5 Finitestateautomata,regularlanguagesandgrammars 52 2.6 Pushdownautomata,context-freelanguagesandgram- mars 60 2.7 Turing machines, recursively enumerable languages andgrammars 81 2.8 Linearly bounded automata, context-sensitive lan- guagesandgrammars 85 v vi Contents 2.9 Turingmachinesanddecidability 87 2.10 Automatawithmorethanoneinputword 91 3 Introductiontothewordproblem 97 3.1 Definitionofthewordproblem 97 3.2 VanKampendiagrams 98 3.3 TheDehnfunction 102 3.4 Thewordproblemasaformallanguage 105 3.5 DehnpresentationsandDehnalgorithms 110 3.6 Fillingfunctions 114 PARTTWO FINITESTATEAUTOMATAANDGROUPS 115 4 Rewritingsystems 117 4.1 Rewritingsystemsinmonoidsandgroups 117 4.2 Theuseoffsainthereductionprocess 123 5 Automaticgroups 125 5.1 Definitionofautomaticgroups 126 5.2 Propertiesofautomaticgroups 129 5.3 Shortlexandgeodesicstructures 135 5.4 Theconstructionofshortlexautomaticstructures 135 5.5 Examplesofautomaticgroups 139 5.6 Closureproperties 142 5.7 Thefalsificationbyfellowtravellerproperty 143 5.8 Stronglygeodesicallyautomaticgroups 145 5.9 Generalisationsofautomaticity 146 6 Hyperbolicgroups 150 6.1 Hyperbolicityconditions 150 6.2 Hyperbolicityforgeodesicmetricspacesandgroups 153 6.3 Thinbigons,biautomaticityanddivergence 154 6.4 HyperbolicgroupshaveDehnpresentations 158 6.5 GroupswithlinearDehnfunctionsarehyperbolic 161 6.6 Equivalentdefinitionsofhyperbolicity 164 6.7 Quasigeodesics 165 6.8 Furtherpropertiesofhyperbolicgroups 166 7 Geodesics 169 7.1 Introduction 169 7.2 Virtuallyabeliangroupsandrelativelyhyperbolicgroups 170 7.3 Coxetergroups 173 Contents vii 7.4 Garsidegroups 176 7.5 GroupswithgeodesicslyinginsomesubclassofReg 182 7.6 Conjugacygeodesics 182 8 Subgroupsandcosetsystems 184 8.1 Rationalandquasiconvexsubsetsofgroups 184 8.2 Automaticcosetsystems 189 9 Automatagroups 194 9.1 Introducingpermutationaltransducers 194 9.2 Automatagroups 199 9.3 Groupsoftreeautomorphisms 203 9.4 Dualautomata 210 9.5 Freeautomatagroups 212 9.6 Decisionproblems 213 9.7 Resolvingfamousproblems 215 PARTTHREE THEWORDPROBLEM 219 10 Solubilityofthewordproblem 221 10.1 TheNovikov–Boonetheorem 221 10.2 Relatedresults 226 11 Context-freeandone-counterwordproblems 228 11.1 Groupswithcontext-freewordproblem 228 11.2 Groupswithone-counterwordproblem 232 12 Context-sensitivewordproblems 236 12.1 Lakin’sexample 237 12.2 Somefurtherexamples 239 12.3 Fillinglength 240 12.4 Groupswithlinearfillinglength 242 13 Wordproblemsinotherlanguageclasses 249 13.1 Real-timewordproblems 249 13.2 Indexedwordproblems 254 13.3 Poly-context-freewordproblems 254 14 Theco-wordproblemandtheconjugacyproblem 256 14.1 Theco-wordproblem 256 14.2 Co-context-freegroups 257 14.3 Indexedco-wordproblems 267 14.4 Theconjugacyproblem 268 viii Contents References 270 IndexofNotation 283 IndexofNames 284 IndexofTopicsandTerminology 287 Preface This book explores connections between group theory and automata theory. Weweremotivatedtowriteitbyourobservationsofagreatdiversityofsuch connections;weseeautomatausedtoencodecomplexity,torecogniseaspects ofunderlyinggeometry,toprovideefficientalgorithmsforpracticalcomputa- tion,andmore. Thebookispitchedatbeginninggraduatestudents,andatprofessionalaca- demicmathematicianswhoarenotfamiliarwithallaspectsoftheseintercon- nected fields. It provides background in automata theory sufficient for its ap- plicationstogrouptheory,andthengivesup-to-dateaccountsofthesevarious applications.Weassumethatthereaderalreadyhasabasicknowledgeofgroup theory,asprovidedinastandardundergraduatecourse,butwedonotassume anypreviousknowledgeofautomatatheory. Thegroupsthatweconsiderareallfinitelygenerated.Anelementofagroup G is represented as a product of powers of elements of the generating set X, andhenceasastringofsymbolsfromA := X∪X−1,alsocalledwords.Many differentstringsmayrepresentthesameelement.Thegroupmaybedefinedby apresentation;thatis,byitsgeneratingsetXtogetherwithasetRofrelations, fromwhichallequationsinthegroupbetweenstringscanbederived.Alterna- tively,asforinstanceinthecaseofautomatagroups,Gmightbedefinedasa groupoffunctionsgeneratedbytheelementsofX. Certainsetsofstrings,alsocalledlanguages,overAarenaturallyofinterest. WestudythewordproblemofthegroupG,namelythesetWP(G,A)ofstrings overAthatrepresenttheidentityelement.WedefinealanguageforGtobea languageoverAthatmapsontoG,andconsiderthelanguageofallgeodesics, andvariouslanguagesthatmapbijectivelytoG.Wealsoconsidercombings, defined to be group languages for which two words representing either the sameelementorelementsthatareadjacentintheCayleygraphfellowtravel; thatis,theyareataboundeddistantapartthroughouttheirlength. ix x Preface Weconsideranautomatontobeadevicefordefininga,typicallyinfinite,set Lofstringsoverafinitealphabet,calledthelanguageoftheautomaton.Any stringoverthefinitealphabetmaybeinputtotheautomaton,andistheneither acceptedifitisin L,orrejectedifitisnot.Weconsiderautomataofvarying degreesofcomplexity,rangingfromfinitestateautomata,whichdefineregular languages, through pushdown automata, defining context-free languages, to Turing machines, which set the boundaries for algorithmic recognition of a language. In other words, we consider the full Chomsky hierarchy of formal languagesandtheassociatedmodelsofcomputation. Finite state automata were used by Thurston in his definition of automatic groups after he realised that both the fellow traveller property and the finite- ness of the set of cone types that Cannon had identified in the fundamental groups of compact hyperbolic manifolds could be expressed in terms of reg- ularlanguages.Forautomaticgroupsaregularcombingcanbefound;useof the finite state automaton that defines this together with other automata that encode fellow travelling allows in particular a quadratic time solution to the wordproblem.Word-hyperbolicgroups,asdefinedbyGromov,canbecharac- terisedbytheirpossessionofautomaticstructuresofaparticulartype,leading tolineartimesolutionstothewordproblem. ForsomegroupsthesetofallgeodesicwordsoverAisaregularlanguage. Thisistrueforword-hyperbolicgroupsandabeliangroups,withrespecttoany generatingset,andformanyothergroups,includingCoxetergroups,virtually free groups and Garside groups, for certain generating sets. Many of these groupsareinfactautomatic. ThepositionofalanguageintheChomskyhierarchycanbeusedasamea- sureofitscomplexity.Forexample,theproblemofdecidingwhetheraninput word w over A represents the identity ofG (which, like the set it recognises, is called the word problem) can be solved by a terminating algorithm if and only if the set WP(G,A) and its complement can be recognised by a Turing machine;thatis,ifandonlyifWP(G,A)isrecursive.Wealsopresentaproof ofthewell-knownfactthatfinitelypresentedgroupsexistforwhichtheword problemisnotsoluble;theproofofthisresultencodestheexistenceofTuring machineswithnon-recursivelanguages. Whenthewordproblemissoluble,someconnectionscanbemadebetween thepositionofthelanguageWP(G,A)intheChomskyhierarchyandthealge- braicpropertiesofthegroup.ItiselementarytoseethatWP(G,A)isregularif andonlyifG isfinite,whileahighlynon-trivialresultofMullerandSchupp shows that a group has context-free word problem if and only if it has a free subgroupoffiniteindex. Attaching an output-tape to an automaton extends it from a device that