Non-Looping String Rewriting

DOI10.1051/ita:1999118zbMath0951.68054MaRDI QIDQ4718895

Hans Zantema, Alfons Geser

Publication date: 4 January 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222096

zbMATH Keywords

loops; string rewriting reductions

Mathematics Subject Classification ID

20M10: General structure theory for semigroups

68Q42: Grammars and rewriting systems

Related Items

Termination of string rewriting proved automatically, Loop detection in term rewriting using the eliminating unfoldings, On normalizing, non-terminating one-rule string rewriting systems, Match-bounded string rewriting systems, Decision problems for semi-Thue systems with a few rules, Relative undecidability in term rewriting. I: The termination hierarchy, Relative undecidability in term rewriting. II: The confluence hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Problems of equality and divisibility in semigroups with a single defining relation
• Natural termination
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Termination of rewriting
• On Proving Uniform Termination and Restricted Termination of Rewriting Systems
• One-rule semi-Thue systems with loops of length one, two or three
• Tree-Manipulating Systems and Church-Rosser Theorems
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems