Non-Looping String Rewriting

DOI10.1051/ITA:1999118MaRDI QIDQ4718895zbMATH OpenOpenAlexFDO

Authors Alfons Geser, Hans Zantema

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, https://semanticscholar.org/paper/4562eb1767e4fd93120439497a5ba8cbca12b0a4

zbMATH Keywords

loopsstring rewriting reductions

Mathematics Subject Classification ID

General structure theory for semigroups (20M10) Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 789389
• scientific article; zbMATH DE number 42096
• Logical string rewriting
• Transforming cycle rewriting into string rewriting
• Maximally parallel contextual string rewriting
• String Noninclusion Optimization Problems
• Applying string-rewriting to sequence-based specification
• Observation of string-rewriting systems
• scientific article; zbMATH DE number 6665209
• Infinite string rewrite systems and complexity

Cites work

• scientific article; zbMATH DE number 3729436 (Why is no real title available?)
• scientific article; zbMATH DE number 42096 (Why is no real title available?)
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• Natural termination
• On Proving Uniform Termination and Restricted Termination of Rewriting Systems
• One-rule semi-Thue systems with loops of length one, two or three
• Problems of equality and divisibility in semigroups with a single defining relation
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Termination of rewriting
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Tree-Manipulating Systems and Church-Rosser Theorems

Cited in

(20)

• On normalizing, non-terminating one-rule string rewriting systems
• Loop detection by logically constrained term rewriting
• 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
• On prefixal one-rule string rewrite systems
• Proof relevant corecursive resolution
• One-rule semi-Thue systems with loops of length one, two or three
• Finding and certifying loops
• scientific article; zbMATH DE number 4035120 (Why is no real title available?)
• scientific article; zbMATH DE number 2090078 (Why is no real title available?)
• Sparse tiling through overlap closures for termination of string rewriting
• Termination of cycle rewriting
• scientific article; zbMATH DE number 6665209 (Why is no real title available?)
• On string replacement exponentiation
• Non-termination in Term Rewriting and Logic Programming
• Implementing field extensions of the form Q[sqrt(b)]
• Termination of string rewriting proved automatically
• Loop detection in term rewriting using the eliminating unfoldings

This page was built for publication: Non-Looping String Rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4718895)