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

      0 references
      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references