UID:
almafu_9960117655902883
Umfang:
1 online resource (xi, 294 pages) :
,
digital, PDF file(s).
Ausgabe:
First edition.
ISBN:
1-108-20699-9
,
1-108-21644-7
,
1-316-58824-6
Serie:
London Mathematical Society student texts ; 88
Inhalt:
Fascinating connections exist between group theory and automata theory, and a wide variety of them are discussed in this text. Automata can be used in group theory to encode complexity, to represent aspects of underlying geometry on a space on which a group acts, and to provide efficient algorithms for practical computation. There are also many applications in geometric group theory. The authors provide background material in each of these related areas, as well as exploring the connections along a number of strands that lead to the forefront of current research in geometric group theory. Examples studied in detail include hyperbolic groups, Euclidean groups, braid groups, Coxeter groups, Artin groups, and automata groups such as the Grigorchuk group. This book will be a convenient reference point for established mathematicians who need to understand background material for applications, and can serve as a textbook for research students in (geometric) group theory.
Anmerkung:
Title from publisher's bibliographic system (viewed on 20 Mar 2017).
,
Cover -- Series page -- Title page -- Copyright information -- Table of contents -- Preface -- Part 1 Introduction -- 1 Group theory -- 1.1 Introduction and basic notation -- 1.2 Generators, congruences and presentations -- 1.3 Decision problems -- 1.4 Subgroups and Schreier generators -- 1.5 Combining groups -- 1.6 Cayley graphs -- 1.7 Quasi-isometries -- 1.8 Ends of graphs and groups -- 1.9 Small cancellation -- 1.10 Some interesting families of groups -- 2 Formal languages and automata theory -- 2.1 Languages, automata and grammars -- 2.2 Types of automata -- 2.3 More on grammars -- 2.4 Syntactic monoids -- 2.5 Finite state automata, regular languages and grammars -- 2.6 Pushdown automata, context-free languages andgrammars -- 2.7 Turing machines, recursively enumerable languages andgrammars -- 2.8 Linearly bounded automata, context-sensitive languagesand grammars -- 2.9 Turing machines and decidability -- 2.10 Automata with more than one input word -- 3 Introduction to the word problem -- 3.1 Definition of the word problem -- 3.2 Van Kampen diagrams -- 3.3 The Dehn function -- 3.4 The word problem as a formal language -- 3.5 Dehn presentations and Dehn algorithms -- 3.6 Filling functions -- Part 2 Finite State Automata and Groups -- 4 Rewriting systems -- 4.1 Rewriting systems in monoids and groups -- 4.2 The use of fsa in the reduction process -- 5 Automatic groups -- 5.1 Definition of automatic groups -- 5.2 Properties of automatic groups -- 5.3 Shortlex and geodesic structures -- 5.4 The construction of shortlex automatic structures -- 5.5 Examples of automatic groups -- 5.6 Closure properties -- 5.7 The falsification by fellow traveller property -- 5.8 Strongly geodesically automatic groups -- 5.9 Generalisations of automaticity -- 6 Hyperbolic groups -- 6.1 Hyperbolicity conditions.
,
6.2 Hyperbolicity for geodesic metric spaces and groups -- 6.3 Thin bigons, biautomaticity and divergence -- 6.4 Hyperbolic groups have Dehn presentations -- 6.5 Groups with linear Dehn functions are hyperbolic -- 6.6 Equivalent definitions of hyperbolicity -- 6.7 Quasigeodesics -- 6.8 Further properties of hyperbolic groups -- 7 Geodesics -- 7.1 Introduction -- 7.2 Virtually abelian groups and relatively hyperbolic groups -- 7.3 Coxeter groups -- 7.4 Garside groups -- 7.5 Groups with geodesics lying in some subclass of Reg -- 7.6 Conjugacy geodesics -- 8 Subgroups and coset systems -- 8.1 Rational and quasiconvex subsets of groups -- 8.2 Automatic coset systems -- 9 Automata groups -- 9.1 Introducing permutational transducers -- 9.2 Automata groups -- 9.3 Groups of tree automorphisms -- 9.4 Dual automata -- 9.5 Free automata groups -- 9.6 Decision problems -- 9.7 Resolving famous problems -- Part 3 The Word Problem -- 10 Solubility of the word problem -- 10.1 The Novikov-Boone theorem -- 10.2 Related results -- 11 Context-free and one-counter word problems -- 11.1 Groups with context-free word problem -- 11.2 Groups with one-counter word problem -- 12 Context-sensitive word problems -- 12.1 Lakin's example -- 12.2 Some further examples -- 12.3 Filling length -- 12.4 Groups with linear filling length -- 13 Word problems in other language classes -- 13.1 Real-time word problems -- 13.2 Indexed word problems -- 13.3 Poly-context-free word problems -- 14 The co-word problem and the conjugacy problem -- 14.1 The co-word problem -- 14.2 Co-context-free groups -- 14.3 Indexed co-word problems -- 14.4 The conjugacy problem -- References -- Index of Notation -- Index of Names -- Index of Topics and Terminology.
Weitere Ausg.:
ISBN 1-316-60652-X
Weitere Ausg.:
ISBN 1-107-15235-6
Sprache:
Englisch
Bookmarklink
