Using groups for investigating rewrite systems
Preprint
Abstract
We describe several technical tools that prove to be efficient for investigating the rewrite systems associated with a family of algebraic laws, and might be useful for more general rewrite systems. These tools consist in introducing a monoid of partial operators, listing the monoid relations expressing the possible local confluence of the rewrite system, then introducing the group presented by these relations, and finally replacing the initial rewrite system with a internal process entirely sitting in the latter group. When the approach can be completed, one typically obtains a practical method for constructing algebras satisfying prescribed laws and for solving the associated word problem.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- FREE AUGMENTED LD-SYSTEMSJournal of Algebra and Its Applications, 2007
- THE ALGEBRA OF STRAND SPLITTING II: A PRESENTATION FOR THE BRAID GROUP ON ONE STRANDInternational Journal of Algebra and Computation, 2006
- Geometric presentations for Thompson's groupsJournal of Pure and Applied Algebra, 2005
- Complete positive group presentationsJournal of Algebra, 2003
- Braids and Self-Distributivity2000
- Groupoids, Inverse Semigroups, and their Operator Algebras1999
- The structure group for the associativity identityJournal of Pure and Applied Algebra, 1996
- Thue systems as rewriting systemsJournal of Symbolic Computation, 1987
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting SystemsJournal of the ACM, 1980
- A Machine-Oriented Logic Based on the Resolution Principle1965