Name
Title | ||
|---|---|---|
Computing maximal Kleene closures that are embeddable in a given subword-closed language |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s11047-013-9364-y | Natural Computing |
Keywords | Field | DocType |
Algorithm,Automaton,Code,DNA encodings,Maximal,Regular language,Subword closure | Discrete mathematics,Closure (computer programming),Automaton,Coding (social sciences),Regular language,Time complexity,Mathematics,DNA computing | Journal |
Volume | Issue | ISSN |
12 | 2 | 1567-7818 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stavros Konstantinidis | 1 | 283 | 31.10 |
| Nicolae Santean | 2 | 109 | 13.05 |