Reconstructing Binary Words of Unknown Length with #-Subword Queries
Abstract
A guesser reconstructs a binary word of unknown length . A #-subword query gives the number of occurrences of a chosen word as a subword of . Querying and gives the length. A deterministic algorithm reconstructs in queries. A second deterministic algorithm uses only Lyndon words for and makes queries. Both bounds count the first two queries and hold for every .
19 pages · 13 marked passages
Concepts
Concept map
Preparing this local graph with the browser’s fonts…
Proofs
Proof network
Preparing this local graph with the browser’s fonts…
Proof list
-
no assumptions
thm✓Lax100001.Rows -
no assumptions
thm✓Lax100001.Lyndon -
no assumptions
thm✓Lax100001.Tail
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
- Gwenaël Richomme and Matthieu Rosenfeld. Reconstructing Words Using Queries on Subwords or Factors. In STACS, 2023. doi:10.4230/LIPIcs.STACS.2023.52
- 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