Deciding representability of sets of words of equal length
type: Item
instance of: scholarly article
title: Deciding representability of sets of words of equal length
zbMATH Open document ID: 1293.68158
author: F. Blanchet-Sadri
author: Sean Simmons
published in: Theoretical Computer Science
publication date: 2013-03-04T00:00:00Z
review text: 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.
reviewed by: Anton Černý
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6140798
zbMATH Keywords: partial word
zbMATH Keywords: subword
zbMATH Keywords: factor
zbMATH Keywords: complexity classes P and NP
zbMATH Keywords: representable set
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.12.042
OpenAlex ID: W2086208278
DOI: 10.1016/J.TCS.2012.12.042
description: scientific article; zbMATH DE number 6140798