Word Processing in Groups

From Wikipedia, the free encyclopedia

Word Processing in Groups is a monograph in mathematics on the theory of automatic groups, a type of abstract algebra whose operations are defined by the behavior of finite automata. The book's authors are David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Mike Paterson, and William Thurston. Widely circulated in preprint form, it formed the foundation of the study of automatic groups even before its 1992 publication by Jones and Bartlett Publishers (ISBN 0-86720-244-0).[1][2][3]

Topics[edit]

The book is divided into two parts, one on the basic theory of these structures and another on recent research, connections to geometry and topology, and other related topics.[1]

The first part has eight chapters. They cover automata theory and regular languages, and the closure properties of regular languages under logical combinations; the definition of automatic groups and biautomatic groups; examples from topology and "combable" structure in the Cayley graphs of automatic groups; abelian groups and the automaticity of Euclidean groups; the theory of determining whether a group is automatic, and its practical implementation by Epstein, Holt, and Sarah Rees; extensions to asynchronous automata; and nilpotent groups.[1][2][4]

The second part has four chapters, on braid groups, isoperimetric inequalities, geometric finiteness, and the fundamental groups of three-dimensional manifolds.[1][4]

Audience and reception[edit]

Although not primarily a textbook, the first part of the book could be used as the basis for a graduate course.[1][4] More generally, reviewer Gilbert Baumslag recommends it "very strongly to everyone who is interested in either group theory or topology, as well as to computer scientists."

Baumslag was an expert in a related but older area of study, groups defined by finite presentations, in which research was eventually stymied by the phenomenon that many basic problems are undecidable. Despite tracing the origins of automatic groups to early 20th-century mathematician Max Dehn, he writes that the book studies "a strikingly new class of groups" that "conjures up the fascinating possibility that some of the exploration of these automatic groups can be carried out by means of high-speed computers" and that the book is "very likely to have a great impact".[2]

Reviewer Daniel E. Cohen adds that two features of the book are unusual. First, that the mathematical results that it presents all have names, not just numbers, and second, that the cost of the book is low.[3]

In 2009, mathematician Mark V. Lawson wrote that despite its "odd title," the book made automata theory more respectable among mathematicians stating that it became part of "a quiet revolution in the diplomatic relations between mathematics and computer science".[5]

References[edit]

  1. ^ a b c d e Apanasov, B. N., "Review of Word Processing in Groups", zbMATH, Zbl 0764.20017
  2. ^ a b c Baumslag, Gilbert (1994), "Review of Word Processing in Groups", Bulletin of the American Mathematical Society, New Series, 31 (1): 86–91, doi:10.1090/S0273-0979-1994-00481-1, MR 1568123
  3. ^ a b Cohen, D. E. (November 1993), "Review of Word Processing in Groups", Bulletin of the London Mathematical Society, 25 (6): 614–616, doi:10.1112/blms/25.6.614
  4. ^ a b c Thomas, Richard M. (1993), "Review of Word Processing in Groups", Mathematical Reviews, MR 1161694
  5. ^ Lawson, Mark V. (December 2009), "Review of A Second Course in Formal Languages and Automata Theory by Jeffrey Shallit", SIAM Review, 51 (4): 797–799, JSTOR 25662348