On the complexity of deciding avoidability of sets of partial words
type: Item
instance of: scholarly article
title: On the complexity of deciding avoidability of sets of partial words
zbMATH Open document ID: 1208.68164
author: Brandon Blakeley
author: F. Blanchet-Sadri
author: Josh Gunter
author: Narad Rampersad
published in: Theoretical Computer Science
publication date: 2010-11-19T00:00:00Z
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5817532
zbMATH Keywords: computational complexity
zbMATH Keywords: combinatorics on words
zbMATH Keywords: partial words
zbMATH Keywords: unavoidable sets
zbMATH Keywords: NP-hard problems
zbMATH Keywords: de Bruijn graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.09.006
OpenAlex ID: W2129749965
cites work: Efficient string matching
cites work: On the Complexity of Deciding Avoidability of Sets of Partial Words
cites work: Algorithmic Combinatorics on Partial Words
cites work: Unavoidable sets of partial words
cites work: Testing avoidability on sets of partial words is hard
cites work: UNAVOIDABLE SETS OF CONSTANT LENGTH
cites work: Q4714446
cites work: Simple deterministic wildcard matching
cites work: Crucial words and the complexity of some extremal problems for sets of prohibited words
cites work: Q4198056
cites work: Q3994681
cites work: Q4255576
cites work: Q4142699
cites work: Repetition-free words
cites work: Q4529547
cites work: A proof of Golomb's conjecture for the de Bruijn graph
cites work: Relationships between nondeterministic and deterministic tape complexities
DOI: 10.1016/J.TCS.2010.09.006
description: scientific article; zbMATH DE number 5817532