Automatic group

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 whether a given word representation of a group element is in a "canonical form" and can tell whether 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 A^\ast representing it; *multipliers, one for each a \in A \cup \{1\} , which accept a pair (w 1 , w 2 ), for words w i accepted by the word-acceptor, precisely when w_1 a = w_2 in G. The property of being automatic does not depend on the set of generators.

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 whether a given word representation of a group element is in a "canonical form" and can tell whether 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 A^\ast representing it; multipliers, one for each a \in A \cup \{1\} , which accept a pair (w 1 , w 2 ), for words w i accepted by the word-acceptor, precisely when w_1 a = w_2 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 a = 1 ). Automatic groups are characterized by the fellow traveler property. Let d(x,y) denote the distance between x, y \in G in the Cayley graph of G . Then, G is automatic with respect to a word acceptor L if and only if there is a constant C \in \mathbb{N} such that for all words u, v \in L which differ by at most one generator, the distance between the respective prefixes of u and v is bounded by C. In other words, \forall u, v \in L, d(u,v) \leq 1 \Rightarrow \forall k \in \mathbb{N}, d(u_{|k},v_{|k}) \leq C where w_{|k} for the k-th prefix of w (or w itself if k > |w| ). 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).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376141180 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.