Sparse Tiling through Overlap Closures for Termination of String Rewriting
Preprint
Abstract
We over-approximate reachability sets in string rewriting by languages defined by admissible factors, called tiles. A sparse set of tiles contains only those that are reachable in derivations, and is constructed by completing an automaton. Using the partial algebra defined by a sparse tiling for semantic labelling, we obtain a transformational method for proving local termination. With a known result on forward closures, and a new characterisation of overlap closures, we obtain methods for proving termination and relative termination, respectively. We report on experiments showing the strength of these methods.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Reachability, confluence, and termination analysis with state-compatible automataInformation and Computation, 2017
- Termination of String Rewriting Proved AutomaticallyJournal of Automated Reasoning, 2005
- Match-Bounded String Rewriting SystemsApplicable Algebra in Engineering, Communication and Computing, 2004
- Termination of term rewriting using dependency pairsTheoretical Computer Science, 2000
- Non-Looping String RewritingRAIRO - Theoretical Informatics and Applications, 1999
- TERMINATION OF TERM REWRITING BY SEMANTIC LABELLINGFundamenta Informaticae, 1995
- The smallest automation recognizing the subwords of a textTheoretical Computer Science, 1985
- On Proving Uniform Termination and Restricted Termination of Rewriting SystemsSIAM Journal on Computing, 1983
- Locally testable languagesJournal of Computer and System Sciences, 1972