Calcul de longueurs de chaînes de réécriture dans le monoïde libre (Q2266711): Difference between revisions

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\).