FORMAL DESCRIPTIONS OF CODE PROPERTIES:
DECIDABILITY, COMPLEXITY, IMPLEMENTATION
KRYSTIAN DUDZINSKI and STAVROS KONSTANTINIDIS
The branch of coding theory that is based on formal languages
has produced several methods for defining code properties, including
word relations, dependence systems, implicational conditions,
trajectories, and language inequations. Of those, the latter three
can be viewed as formal methods in the sense that a certain formal
expression can be used to describe a code property. In this work we
present a formal method which is based on transducers, in the sense
that each transducer of a certain type defines/describes a desired
code property, and provides simple and uniform decision procedures
for the basic questions of property satisfaction and maximality for
regular languages. Our work includes statements about the hardness of
deciding some of the problems involved. It turns out that maximality
can be hard to decide even for "classical" code properties of finite
languages. We also present an initial implementation of a LAnguage
SERver capable of deciding the satisfaction problem for a given
transducer code property and regular language.