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.