Reconstructing Words Using Queries on Subwords or Factors

Richomme, Gwenaël; Rosenfeld, Matthieu

doi:10.4230/LIPIcs.STACS.2023.52

File

LIPIcs.STACS.2023.52.pdf

Filesize: 0.71 MB
15 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2023.52
URN: urn:nbn:de:0030-drops-177041

Author Details

Gwenaël Richomme

LIRMM, Université Paul-Valéry Montpellier 3, Université de Montpellier, CNRS, Montpellier, France

Matthieu Rosenfeld

LIRMM, Université de Montpellier, CNRS, Montpellier, France

Acknowledgements

Authors thank Victor Poupet for useful discussions. Many thanks also for the referees for their accurate reading and their valuable suggestions.

Cite AsGet BibTex

Gwenaël Richomme and Matthieu Rosenfeld. Reconstructing Words Using Queries on Subwords or Factors. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.52

Abstract

We study word reconstruction problems. Improving a previous result by P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka and M. Rigo, we prove that, for any unknown word w of length n over an alphabet of cardinality k, w can be reconstructed from the number of occurrences as subwords (or scattered factors) of O(k²√{nlog₂(n)}) words. Two previous upper bounds obtained by S. S. Skiena and G. Sundaram are also slightly improved: one when considering information on the existence of subwords instead of on the numbers of their occurrences, and, the other when considering information on the existence of factors.

Subject Classification

ACM Subject Classification

Theory of computation → Design and analysis of algorithms
Mathematics of computing → Combinatorics on words

Keywords

Word reconstruction
Subwords
Factors

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

M. Dudik and L.J. Schulman. Reconstruction from subsequences. J. Combin. Theory Ser. A, 103:337-348, 2003.
P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka, and M. Rigo. Reconstructing words from right-bounded-block words. In N. Jonoska and D. Savchuk, editors, Developments in Language Theory - 24th International Conference, DLT 2020, Tampa, FL, USA, May 11-15, 2020, Proceedings, volume 12086 of Lecture Notes in Computer Science, pages 96-109. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-48516-0_8.
P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka, and M. Rigo. Reconstructing words from right-bounded-block words. Internat. J. Found. Comput. Sci., 32(6):619-640, 2021. URL: https://doi.org/10.1142/S0129054121420016.
Kazuo Iwama, Junichi Teruyama, and Shuntaro Tsuyama. Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms. arXiv e-prints, 2018. URL: http://arxiv.org/abs/1808.00674.
L.O. Kalashnik. The reconstruction of a word from fragments. In Numerical Mathematics and Computer Technology, Preprint IV, pages 56-57. Akad. Nauk. Ukrain. SSR Inst. Mat., 1973.
I. Krasikov and Y. Roditty. On a reconstruction problem for sequences. J. Combin. Theory Ser. A, 77:344-348, 1997.
V. I. Levenshtein. Efficient reconstruction of sequences from their subsequences or supersequences. In J. Combin. Theory Ser. A, volume 93, pages 310-332, 2001.
M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, UK, 1997.
S. Skiena and G. Sundaram. Reconstructing strings from substrings (extended abstract). In F. Dehne, J.-R. Sack, N. Santoro, and S. Whitesides, editors, Proceedings of the third workshop an Algorithms and Data Structures (WADS '93), Montréal, Canada, August 11-13, number 709 in Lecture Notes in Comput. Sci., pages 565-576. Springer-Verlag, Berlin, 1993.
S.S. Skiena and G. Sundaram. Reconstructing strings from substrings. J. Comput. Bio., 2(2):333-353, 1995.