Calcul de longueurs de chaînes de réécriture dans le monoïde libre

DOI10.1016/0304-3975(85)90006-4zbMath0562.03019OpenAlexW1973072128MaRDI QIDQ2266711

Yves Métivier

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90006-4

zbMATH Keywords

congruencerewriting systemfree monoidcomplexity measureterms

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Complexity of computation (including implicit computational complexity) (03D15) Thue and Post systems, etc. (03D03)

Related Items

Open problems in rewriting ⋮ More problems in rewriting ⋮ Termination of rewriting ⋮ Thue systems as rewriting systems ⋮ On confluence of one-rule trace-rewriting systems ⋮ An upper bound on the derivational complexity of Knuth-Bendix orderings. ⋮ The word problem for one-relation monoids: a survey ⋮ On normalizing, non-terminating one-rule string rewriting systems ⋮ One-rule semi-Thue systems with loops of length one, two or three

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• About the rewriting systems produced by the Knuth-Bendix completion algorithm
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems