Prefix Rewriting and Descriptional Complexity
Holger Petersen · Journal of automata, languages and combinatorics · 2000
We investigate rewriting-systems that rewrite a prefix of a given string. B{\"{u}}chi has shown that these systems and some of their generalizations generate the regular sets from finite sets of axioms, which justifies the name regular canonical systems. Here we consider the descriptional power of these systems in comparison to finite automata, answering questions left open by Frazier and Page.