Deciding representability of sets of words of equal length
The authors investigate the complexity of the problem {\textsc{Rep}} of the representability of a set \(S\) of words of equal length \(n\) by a partial word \(w\) such that \(S\) is precisely the set of all subwords of \(w\) of length \(n\), i.e., \(S\) is the set of all words compatible with factors of \(w\) of length \(n.\) A partial word may contain, besides the symbols of the alphabet, holes -- positions compatible with any alphabet symbol. As well, a variant \(h\)-{\textsc{Rep}} is considered requiring \(w\) to contain exactly \(h\) gaps. It is shown that {\textsc{Rep}} belongs to the class NP, while a deterministic polynomial algorithm is described for constructing a solution to \(h\)-{\textsc{Rep}}. The question whether {\textsc{Rep}} belongs to the class P remains open.
- Deciding representability of sets of words of equal length
- Deciding representability of sets of words of equal length in polynomial time
- Computing minimum length representations of sets of words of uniform length
- Computing Minimum Length Representations of Sets of Words of Uniform Length
- Computing generalized de Bruijn sequences
- Computing generalized de Bruijn sequences
- Computing minimum length representations of sets of words of uniform length
- Sets represented as the length-n factors of a word
- Deciding representability of sets of words of equal length in polynomial time
- Computing Minimum Length Representations of Sets of Words of Uniform Length
- Deciding representability of sets of words of equal length
This page was built for publication: Deciding representability of sets of words of equal length
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939274)
