Sequence reconstruction problem for deletion channels: a complete asymptotic solution
Transmit a codeword x, that belongs to an (ℓ−1)-deletion-correcting code of length n, over a t-deletion channel for some 1≤ℓ≤t<n. Levenshtein (2001) [10], proposed the problem of determining N(n,ℓ,t)+1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to th...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/182329 |
| _version_ | 1826121648694099968 |
|---|---|
| author | Pham, Van Long Phuoc Goyal, Keshav Kiah, Han Mao |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Pham, Van Long Phuoc Goyal, Keshav Kiah, Han Mao |
| author_sort | Pham, Van Long Phuoc |
| collection | NTU |
| description | Transmit a codeword x, that belongs to an (ℓ−1)-deletion-correcting code of length n, over a t-deletion channel for some 1≤ℓ≤t<n. Levenshtein (2001) [10], proposed the problem of determining N(n,ℓ,t)+1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ∈{1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that [Formula presented]. In the special instances: where ℓ=t, we show that N(n,ℓ,ℓ)=(2ℓℓ); and when ℓ=3 and t=4, we show that N(n,3,4)≤20n−150. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t. |
| first_indexed | 2025-03-09T13:01:54Z |
| format | Journal Article |
| id | ntu-10356/182329 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-03-09T13:01:54Z |
| publishDate | 2025 |
| record_format | dspace |
| spelling | ntu-10356/1823292025-01-22T01:49:12Z Sequence reconstruction problem for deletion channels: a complete asymptotic solution Pham, Van Long Phuoc Goyal, Keshav Kiah, Han Mao School of Physical and Mathematical Sciences Mathematical Sciences Sequence reconstruction problem Deletion-correcting codes Transmit a codeword x, that belongs to an (ℓ−1)-deletion-correcting code of length n, over a t-deletion channel for some 1≤ℓ≤t<n. Levenshtein (2001) [10], proposed the problem of determining N(n,ℓ,t)+1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ∈{1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that [Formula presented]. In the special instances: where ℓ=t, we show that N(n,ℓ,ℓ)=(2ℓℓ); and when ℓ=3 and t=4, we show that N(n,3,4)≤20n−150. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t. Ministry of Education (MOE) Nanyang Technological University Pham Van Long Phuoc acknowledges the funding support from Nanyang Technological University - URECA Undergraduate Research Programme. This research of Han Mao Kiah is supported by the Ministry of Education, Singapore, under its MOE AcRF Tier 2 Award MOE-T2EP20121-0007. 2025-01-22T01:49:12Z 2025-01-22T01:49:12Z 2025 Journal Article Pham, V. L. P., Goyal, K. & Kiah, H. M. (2025). Sequence reconstruction problem for deletion channels: a complete asymptotic solution. Journal of Combinatorial Theory, Series A, 211, 105980-. https://dx.doi.org/10.1016/j.jcta.2024.105980 0097-3165 https://hdl.handle.net/10356/182329 10.1016/j.jcta.2024.105980 2-s2.0-85210137828 211 105980 en MOE-T2EP20121-0007 URECA Journal of Combinatorial Theory, Series A © 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies. |
| spellingShingle | Mathematical Sciences Sequence reconstruction problem Deletion-correcting codes Pham, Van Long Phuoc Goyal, Keshav Kiah, Han Mao Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title | Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title_full | Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title_fullStr | Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title_full_unstemmed | Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title_short | Sequence reconstruction problem for deletion channels: a complete asymptotic solution |
| title_sort | sequence reconstruction problem for deletion channels a complete asymptotic solution |
| topic | Mathematical Sciences Sequence reconstruction problem Deletion-correcting codes |
| url | https://hdl.handle.net/10356/182329 |
| work_keys_str_mv | AT phamvanlongphuoc sequencereconstructionproblemfordeletionchannelsacompleteasymptoticsolution AT goyalkeshav sequencereconstructionproblemfordeletionchannelsacompleteasymptoticsolution AT kiahhanmao sequencereconstructionproblemfordeletionchannelsacompleteasymptoticsolution |