Calcul de longueurs de chaînes de réécriture dans le monoïde libre (Q2266711): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q690236 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Yves Métivier / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90006-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1973072128 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5680296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5633999 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Confluent and Other Types of Thue Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3964028 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5581665 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3853827 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: About the rewriting systems produced by the Knuth-Bendix completion algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4105657 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5668779 / rank | |||
Normal rank |
Latest revision as of 16:20, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Calcul de longueurs de chaînes de réécriture dans le monoïde libre |
scientific article |
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