Reconstructing Binary Words of Unknown Length with #-Subword Queries

lax-100001·created ·Lean v4.33.0 epoch · mathlib db584cd6d46c

Abstract

A guesser reconstructs a binary word ww of unknown length nn. A #-subword query gives the number of occurrences of a chosen word uu as a subword of ww. Querying 00 and 11 gives the length. A deterministic algorithm reconstructs ww in O(log⁡n log⁡log⁡n)O(\sqrt{\log n\,\log\log n}) queries. A second deterministic algorithm uses only Lyndon words for 0<10<1 and makes O(log⁡(n+2))O(\log(n+2)) queries. Both bounds count the first two queries and hold for every ww.

View annotated paper

19 pages · 13 marked passages

Concepts

Concept map
100%

Preparing this local graph with the browser’s fonts…

Proven claimDefinitionThis submissionA → B: B builds on A

Proofs

Proof network

100%

Preparing this local graph with the browser’s fonts…

assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submissionProof — open large view for details
Proof list

Proof code is not displayed; the archive records each proof's checked relationship between claims.

Related submissions

No other submission in the archive builds on this one, and this one builds on none.

References

  1. Gwenaël Richomme and Matthieu Rosenfeld. Reconstructing Words Using Queries on Subwords or Factors. In STACS, 2023. doi:10.4230/LIPIcs.STACS.2023.52
  2. Pamela Fleischmann, Marie Lejeune, Florin Manea, Dirk Nowotka and Michel Rigo. Reconstructing Words from Right-Bounded-Block Words. In Developments in Language Theory, 2020. doi:10.1007/978-3-030-48516-0_8