Characterizing Languages by Normalization and Termination in String Rewriting (Extended Abstract)
Jeroen Ketema, Jakob Grue Simonsen · Developments in Language Theory · 2012
We characterize sets of strings using two central properties from rewriting: normalization and termination. We recall the well-known result that any recursively enumerable set of strings can occur as the set of normalizing strings over a small alphabet if the rewriting system is allowed access to a larger alphabet (and extend the result to ter- mination). We then show that these results do not hold when alphabet extension is disallowed. Finally, we prove that for every reasonably well- behaved deterministic time complexity class, there is a set of strings complete for the class that also occurs as the set of normalizing or ter- minating strings, without alphabet extension.