Automatic group

An automatic group admits an automatic structure for a group: a regular language of representatives and synchronous group multiplier automata recognizing right multiplication by each generator and equality of representatives. Representatives need not be unique. This finite-state description yields effective algorithms for the word problem for a group.

Table of contents
- Automatic structure for a group Automatic group
  - Group multiplier automaton Automatic structure for a group
    - Linear-time multiplication in an automatic structure Group multiplier automaton
    - Pumping of a group multiplier automaton Group multiplier automaton

Automatic structure for a group ( $(A, L)$ )

An automatic structure for a group consists of a finite generating alphabet

A

, a surjective representative regular language

L \subseteq A^{*}

, and finite-state automata accepting the padded convolutions of words

(u, v)

in

L

satisfying

\overline{u} x = \overline{v}

for each

x \in A \cup {ε}

A

and uniqueness of representatives are additional conditions, not part of this definition.

Group multiplier automaton ( $M_{x}$ )

A group multiplier automaton accepts exactly the padded convolutions of words

u \otimes v

with

u, v \in L

and

\overline{u} x = \overline{v}

. The case

x = ε

recognizes equality in the group, rather than equality of literal words over an alphabet.

Linear-time multiplication in an automatic structure ( $∣ v ∣ \leq ∣ u ∣ + N$ )

Fix the first tape of a group multiplier automaton and use dynamic programming over automaton states and output-padding status, retaining predecessor pointers. The pumping of a group multiplier automaton bounds the search by

∣ u ∣ + N

layers, each of fixed size. This constructs a representative of

\overline{u} x

O (∣ u ∣ + 1)

without assuming uniqueness of representatives.

Pumping of a group multiplier automaton

In an accepted padded convolution of words, a loop after one tape ends can be deleted or repeated while keeping that entire tape fixed. The altered other tape still represents the same required neighbouring group element. A shortest representative has a suffix no longer than the fixed number of automaton states; an accepted longer suffix gives infinitely many representatives of the same element.

 Ancestors (5)

 Incoming links (1)

Automatic group

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Automatic group by

Wikipedia Bot  1

An "automatic group" can refer to different concepts depending on the context in which it is used. Here are a few possibilities: 1. **Sociology/Psychology**: In social contexts, an automatic group might refer to a category of individuals who are grouped together based on certain inherent characteristics, such as demographic factors (age, gender, etc.). This grouping occurs without intentional or conscious effort on the part of the individuals.

 Read the full article

  See all articles in the same topic Create my own version