Concept

Automatic group

In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata represent the Cayley graph of the group. That is, they can tell if a given word representation of a group element is in a "canonical form" and can tell if two elements given in canonical words differ by a generator. More precisely, let G be a group and A be a finite set of generators. Then an automatic structure of G with respect to A is a set of finite-state automata: the word-acceptor, which accepts for every element of G at least one word in representing it; multipliers, one for each , which accept a pair (w1, w2), for words wi accepted by the word-acceptor, precisely when in G. The property of being automatic does not depend on the set of generators. Automatic groups have word problem solvable in quadratic time. More strongly, a given word can actually be put into canonical form in quadratic time, based on which the word problem may be solved by testing whether the canonical forms of two words represent the same element (using the multiplier for ). Automatic groups are characterized by the fellow traveler property. Let denote the distance between in the Cayley graph of . Then, G is automatic with respect to a word acceptor L if and only if there is a constant such that for all words which differ by at most one generator, the distance between the respective prefixes of u and v is bounded by C. In other words, where for the k-th prefix of (or itself if ). This means that when reading the words synchronously, it is possible to keep track of the difference between both elements with a finite number of states (the neighborhood of the identity with diameter C in the Cayley graph). The automatic groups include: Finite groups. To see this take the regular language to be the set of all words in the finite group. Euclidean groups All finitely generated Coxeter groups Geometrically finite groups Baumslag–Solitar groups Non-Euclidean nilpotent groups A group is biautomatic if it has two multiplier automata, for left and right multiplication by elements of the generating set, respectively.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.