Determining exponential density and maximal encoding capabilities
of a regular language
Stavros Konstantinidis and Nicolae Santean}
Department of Mathematics and Computing Science,
Saint Mary's University, Halifax, Nova Scotia, B3H 3C3 Canada,
s.konstantinidis@smu.ca, nic.santean@smu.a
The density of a language is the function that returns, for each $n$, the
number of words in the language of length $n$. In the first place, we
consider deciding whether the density of a given regular language $L$ is
exponential. This question can be answered in linear time when $L$ is given
via a DFA. We show that the same question can be decided in quadratic time
when $L$ is given via an NFA. It turns out that this question is equivalent
to whether $L$ is an encoding language: it includes $xD^*y$, for some
nontrivial code $D$ and words $x,y$.
Then, motivated by certain coding techniques for reliable DNA computing,
we consider the problem of characterizing nontrivial languages $D$ that are
maximal with the property that $D^*$ is contained in the subword closure of
a given set $S$ of words of some fixed length $k$ -- this closure is simply
the set of all words whose subwords of length $k$ must be in $S$. We provide
a deep structural characterization of these languages $D$, which leads to
polynomial time algorithms for computing such languages.