Sparse Tiling through Overlap Closures for Termination of String Rewriting

Alfons Geser, Dieter Hofbauer, Johannes Waldmann

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…