2026-07-24T06:45:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17704 2024-03-06T11:00:21Z ddc:004 open_access

Reconstructing Words Using Queries on Subwords or Factors Richomme, Gwenaël Rosenfeld, Matthieu Word reconstruction Subwords Factors 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gwenaël Richomme and Matthieu Rosenfeld 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.52 urn:nbn:de:0030-drops-177041 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.52 eng https://creativecommons.org/licenses/by/4.0/legalcode