Reconstructing words from subwords in linear time

DOI10.1007/S00026-004-0232-4MaRDI QIDQ1764477zbMATH OpenOpenAlexFDO

Authors Andreas W. M. Dress, Péter L. Erdős

Publication date 25 February 2005

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00026-004-0232-4

zbMATH Keywords

algorithmic complexityreconstruction of wordssubwords

Mathematics Subject Classification ID

Combinatorics on words (68R15) Protein sequences, DNA sequences (92D20)

Recommendations

• Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words
• Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. II: Reconstruction with forbidden words
• Word assembly through minimal forbidden words
• A linear algorithm for string reconstruction in the reverse complement equivalence model
• On a reconstruction problem for sequences

Cited in

(22)

• Discovering subword associations in strings in time linear in the output size
• On a reconstruction problem for sequences
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Universal reconstruction of a string
• Adaptive learning of compressible strings
• Characterization of binary words by subwords
• Universal reconstruction of a string
• A linear algorithm for string reconstruction in the reverse complement equivalence model
• Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words
• Reconstructing words from right-bounded-block words
• Relations on words
• Counting the number of non-zero coefficients in rows of generalized Pascal triangles
• On the possibility of a periodic word reconstruction from the subwords of fixed length
• Efficient reconstruction of sequences from their subsequences of supersequences
• Absent Subsequences in Words
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Reconstructing Words from Right-Bounded-Block Words
• Tight bounds for the number of absent subsequences
• Jumbled scattered factors
• Subwords in reverse-complement order
• Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. II: Reconstruction with forbidden words
• Finite automata for testing composition-based reconstructibility of sequences

This page was built for publication: Reconstructing words from subwords in linear time

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