×

Prefix rewriting and descriptional complexity. (English) Zbl 0971.68083

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)].

MSC:

68Q42 Grammars and rewriting systems

Citations:

Zbl 0813.68125
PDF BibTeX XML Cite