Automatic monoids and change of generators (Q4934090)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1389578
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Automatic monoids and change of generators |
scientific article; zbMATH DE number 1389578 |
Statements
Automatic monoids and change of generators (English)
0 references
17 May 2000
0 references
regular languages
0 references
automatic structures
0 references
generating sets
0 references
finite automata
0 references
automatic monoids
0 references
free products of monoids
0 references
0.816301703453064
0 references
0.8155072927474976
0 references
0.813826858997345
0 references
0.8138039112091064
0 references
0.8092622756958008
0 references
An automatic structure of a monoid \(M\) is an ordered pair \((A,L)\), where \(A\) is a generating set of \(M\) and \(L\) is a regular (i.e., acceptable by a finite automaton) language over the alphabet \(A\), which fulfills certain conditions. If \(M\) has an automatic structure, it is called an automatic monoid. The main results are the following: Theorem 1.1. Let \(M\) be a monoid with automatic structure \((A,L)\) and let \(B\) be a finite generating set for \(M\). Then there exists an automatic structure \((B,K)\) for \(M\). Theorem 1.2. Let \(M=N_1*N_2\) be the free product of monoids \(N_1\) and \(N_2\). If \(M\) is automatic, then \(N_i\) is automatic for \(i=1,2\).
0 references
