Computing minimum length representations of sets of words of uniform length

DOI10.1016/J.TCS.2015.06.038zbMATH Open1328.68322OpenAlexW850370502WikidataQ115036536 ScholiaQ115036536MaRDI QIDQ2355702FDOQ2355702

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

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

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)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Depth-First Search and Linear Graph Algorithms
• Finding Minimum-Cost Circulations by Successive Approximation
• Mellin transforms and asymptotics: Digital sums
• On finding minimal length superstrings
• Introduction to modern cryptography.
• Algorithmic Combinatorics on Partial Words
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• Number of Odd Binomial Coefficients
• On Pseudo-Random Arrays
• Deciding representability of sets of words of equal 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

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)