LIPIcs.STACS.2023.52.pdf
- Filesize: 0.71 MB
- 15 pages
Document
Reconstructing Words Using Queries on Subwords or Factors
Authors
Gwenaël Richomme 
,
Matthieu Rosenfeld
-
Part of:
Volume:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-03-03
File
Document Identifiers
Author Details
- LIRMM, Université Paul-Valéry Montpellier 3, 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 As Get 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)
0PDF Downloads
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.