Petersen, Holger Prefix rewriting and descriptional complexity. (English) Zbl 0971.68083 J. Autom. Lang. Comb. 5, No. 3, 245-254 (2000). Summary: We investigate rewriting-systems that rewrite a prefix of a given string. Bü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 M. Frazier and C. D. Page, jun. [Inf. Process. Lett. 51, No. 2, 67-71 (1994; Zbl 0813.68125)]. Cited in 1 Document MSC: 68Q42 Grammars and rewriting systems Keywords:rewriting-systems Citations:Zbl 0813.68125 PDF BibTeX XML Cite \textit{H. Petersen}, J. Autom. Lang. Comb. 5, No. 3, 245--254 (2000; Zbl 0971.68083) OpenURL