Computing minimum length representations of sets of words of uniform length

DOI10.1016/J.TCS.2015.06.038MaRDI QIDQ2355702zbMATH OpenOpenAlexWikidataFDO

Authors F. Blanchet-Sadri, Andrew Lohr

Publication date 24 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.038

zbMATH Keywords

graph theorycombinatorics on wordspartial wordsalgorithms on stringssubwordsrepresentable sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Computing Minimum Length Representations of Sets of Words of Uniform Length
• Deciding representability of sets of words of equal length
• Deciding representability of sets of words of equal length
• Recurrent Partial Words and Representable Sets.
• Deciding representability of sets of words of equal length in polynomial time

Cites work

• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• Algorithmic Combinatorics on Partial Words
• Computing Minimum Length Representations of Sets of Words of Uniform Length
• Deciding representability of sets of words of equal length
• Deciding representability of sets of words of equal length in polynomial time
• Depth-First Search and Linear Graph Algorithms
• Finding Minimum-Cost Circulations by Successive Approximation
• Introduction to modern cryptography.
• Mellin transforms and asymptotics: Digital sums
• Network flows. Theory, algorithms, and applications.
• Number of Odd Binomial Coefficients
• On Pseudo-Random Arrays
• On finding minimal length superstrings
• Sets represented as the length-\(n\) factors of a word

Cited in

(8)

• Deciding representability of sets of words of equal length
• Minimal Discriminating Words Problem Revisited
• Computing Minimum Length Representations of Sets of Words of Uniform Length
• Independent minimum length programs to translate between given strings
• Computing on binary strings
• Computing generalized de Bruijn sequences
• Deciding representability of sets of words of equal length
• Two fast constructions of compact representations of binary words with given set of periods

This page was built for publication: Computing minimum length representations of sets of words of uniform length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355702)