Calcul de longueurs de chaînes de réécriture dans le monoïde libre (Q2266711)
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 3895047
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Calcul de longueurs de chaînes de réécriture dans le monoïde libre |
scientific article; zbMATH DE number 3895047 |
Statements
Calcul de longueurs de chaînes de réécriture dans le monoïde libre (English)
0 references
1985
0 references
A measure of the complexity of a rewriting system on its terms is defined as the maximum number of elements of a chain starting in a term f. The main result derived here is that we increase this complexity by a factor \(| f|^ k\) in the case where the system consists of only one rule \(w\to v\) with \(| w| =| v| =k\).
0 references
congruence
0 references
free monoid
0 references
complexity measure
0 references
rewriting system
0 references
terms
0 references
0.7816808819770813
0 references
0.7590725421905518
0 references
0.7451128959655762
0 references
