Descriptional Complexity of Error/Edit Systems
Lila Kari and Stavros Konstantinidis
Errors appear in a wide range of information processing and transmission
applications, such as data communications, biological computing, computer
typesetting, speech recognition, etc. It can be said indeed that errors are
truly natural phenomena. In this work we introduce error or edit systems
(e-systems, for short), which are formal languages over the alphabet of the
basic edit operations. Our formalism allows one to model essentially any
kind of error situations. For certain natural regular e-systems,
we investigate their descriptional complexity in terms of the number
of states of the automata accepting such systems. This problem is
of interest in its own right as well as in the computation of maximal
error-correcting capabilities of known languages.
Key words: error models, automata, descriptional complexity, formal languages