Rewriting systems, finiteness conditions, and associated functions (Q4942275)
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 1419256
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Rewriting systems, finiteness conditions, and associated functions |
scientific article; zbMATH DE number 1419256 |
Statements
14 December 2000
0 references
semigroups
0 references
groups
0 references
rewriting systems
0 references
Dehn functions
0 references
Squier complexes
0 references
finite derivation type
0 references
finite homological type
0 references
finiteness conditions
0 references
0.96459585
0 references
0.95695174
0 references
0.91210693
0 references
0.8927211
0 references
0.8907743
0 references
0.8894027
0 references
0 references
0.8864801
0 references
Rewriting systems, finiteness conditions, and associated functions (English)
0 references
In a rewriting system \(\mathcal P=[X;R]\) the rules in \(R\) are ordered pairs \(r=(r_{+1},r_{-1})\) of words (over \(X\)). With \(\mathcal P\) a two-dimensional complex \(\mathcal D(\mathcal P)\), known as the Squier complex, is associated. Two finiteness conditions are considered for the finite rewriting systems \(\mathcal P\) in the context of \(\mathcal D(\mathcal P)\). These are FDT (being of finite derivation type) and FHT (being of finite homological type). In the first five sections the authors introduce the concepts needed, and they state known results about the finiteness conditions, including the invariance theorem of the conditions FDT and FHT for the monoids presented by the finite rewriting systems. In the fifth section the second-order homotopical Dehn functions are defined, and in the next section the authors prove an upper bound for these functions when the rewriting systems are complete (that is, confluent and Noetherian). In the last section, it is proved that if \(S_0\) is a submonoid of a monoid \(S\) such that \(S\setminus S_0\) is an ideal of \(S\), and \(S\) has a finite complete rewriting system (\(S\) satisfies FDT, \(S\) satisfies FHT), then \(S_0\) has these properties, respectively. For the entire collection see [Zbl 0931.00032].
0 references