|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050305,
author = {Petersen, Holger},
title = {Prefix Rewriting and Descriptional Complexity},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {245--254},
keywords = {descriptional complexity, prefix rewriting, regular
canonical systems},
abstract = {We investigate rewriting-systems that rewrite a prefix
of a given string. {\sc 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
{\sc Frazier} and {\sc Page}.}
}