Computing generalized de Bruijn sequences
type: Item
instance of: scholarly article
title: Computing generalized de Bruijn sequences
zbMATH Open document ID: 1390.68511
author: Sinziana Munteanu
author: F. Blanchet-Sadri
published in: Theoretical Computer Science
publication date: 2017-11-16T00:00:00Z
review text: A \textit{de Brujin sequence} of order \(n\) is a cyclic sequence over an alphabet \(A\) where each of the words of length \(n\) over \(A\) occurs as a subword exactly once. A \textit{partial word} over an alphabet \(A\) is a sequence from \(A_{\diamond} = A \cup \{ \diamond \}\), where \(\diamond \notin A\) is a symbol, called the \textit{hole symbol}, which matches every letter in \(A\). A \textit{subword} of a partial word \(w\) is a word over \(A\) that can be obtained from a factor of \(w\) by replacing the holes with letters of \(A\). A set \(S\) of words of length \(n\) over \(A\), is said to be \textit{representable} if there exists a partial word \(w\) such that the set of subwords of \(w\) of length \(n\) is exactly \(S\). The computational problem of representing subsets of \(A^n\) by partial words was shown to be in \(\mathcal{NP}\). In this paper, the authors show that this problem is actually in \(\mathcal{P}\). In particular, they describe an algorithm that, given a subset \(S\) of \(A^n\), decides in polynomial time (in the size \(n|S|\) of the input) whether \(S\) is represented by a partial word or not and, in the positive case, gives the partial word representing the set.
reviewed by: Francesco Dolce
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 6807596
zbMATH Keywords: algorithms on words
zbMATH Keywords: combinatorics on words
zbMATH Keywords: graph theory
zbMATH Keywords: partial words
zbMATH Keywords: subwords
zbMATH Keywords: representable sets
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.09.010
OpenAlex ID: W2755302573
cites work: The origins of combinatorics on words
cites work: Algorithmic Combinatorics on Partial Words
cites work: Computing minimum length representations of sets of words of uniform length
cites work: Deciding Representability of Sets of Words of Equal Length in Polynomial Time
cites work: Deciding representability of sets of words of equal length
cites work: On universal partial words
cites work: Universal cycles for combinatorial structures
cites work: Q5834367
cites work: Q4085749
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: Necklaces of beads in k colors and k-ary de Bruijn sequences
cites work: Handbook of Graph Theory
cites work: Shorthand universal cycles for permutations
cites work: On the de Bruijn torus problem
cites work: m-ary closed sequences
cites work: An Introduction to Symbolic Dynamics and Coding
cites work: A problem in arrangements
cites work: The coolest way to generate binary strings
cites work: Sets Represented as the Length-n Factors of a Word
cites work: Depth-First Search and Linear Graph Algorithms
cites work: De Bruijn sequences with efficient decoding algorithms
cites work: On Pseudo-Random Arrays
cites work: Binary Ring Sequences
DOI: 10.1016/J.TCS.2017.09.010
description: scientific article; zbMATH DE number 6807596