[en] A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word w in {a,b}^* can be reconstructed from the number of occurrences of at most min(|w|_a, |w|_b) + 1 scattered factors of the form a^ib, where |w|_a is the number of occurrences of the letter a in w. Moreover, we generalise the result to alphabets of the form {1,...,q} by showing that at most $\sum_{i=1}^{q−1} |w|_i (q − i + 1)$ scattered factors suffices to reconstruct w. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.
Disciplines :
Computer science Mathematics
Author, co-author :
Fleischmann, Pamela
Lejeune, Marie
Manea, Florin
Nowotka, Dirk
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Reconstructing Words from Right-Bounded-Block Words
Publication date :
2021
Journal title :
International Journal of Foundations of Computer Science
ISSN :
0129-0541
Publisher :
World Scientific Publishing Co., Singapore
Volume :
32
Issue :
6
Pages :
619-640
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
This is the long version of the submission presented during the DLT conference.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Volume 3: Beyond Words (Springer, 1997).
J. Berstel and J. Karhumäki, Combinatorics on words: A tutorial, Bull. EATCS 79 (2003) 178.
V. Berthé, J. Karhumäki, D. Nowotka and J. Shallit, Mini-workshop: Combinatorics on words Oberwolfach Rep. 7 (2010) 2195-2244.
K. Bringmann, Fine-grained complexity theory (tutorial) STACS 126 (2019) 4:1-4:7.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition (MIT Press, 2009).
A. W. M. Dress and P. L. Erdös, Reconstructing words from subwords in linear time, Ann. Comb. 8 (2004) 457-462.
M. Dudík and L. J. Schulman, Reconstruction from subsequences, J. Comb. Theory, Ser. A 103(2) (2003) 337-348.
P. L. Erdös, P. Ligeti, P. Sziklai and D. C. Torney, Subwords in reverse-complement order, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery, 14.05.-19.05.2006, Dagstu hl Seminar Proceedings Vol. 06201 (Internationales Begegnungs-und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006).
M. Ferov, Irreducible polynomial modulo p (2008).
W. Foster and I. Krasikov, An improvement of a Borwein-Erdélyi-Kós result, Methods Appl. Anal. 7(4) (2000) 605-614.
D. D. Freydenberger, P. Gawrychowski, J. Karhumäki, F. Manea and W. Rytter, Testing k-binomial equivalence, CoRR abs/1509.00622 (2015).
F. Harary, On the reconstruction of a graph from a collection of subgraphs, Theory of Graphs and its Applications (1964), pp. 47-52.
L. I. Kalashnik, The reconstruction of a word from fragments, Numerical Mathematics and Computer Technology (1973) 56-57.
P. J. Kelly, A congruence theorem for trees, Pacific J. Math. 7(1) (1957) 961-968.
I. Krasikov and Y. Roditty, On a reconstruction problem for sequences, J. Comb. Theory, Ser. A 77(2) (1997) 344-348.
V. I. Levenshtein, On perfect codes in deletion and insertion metric, Discr. Math. Appl. 2 (1992) 241-258.
M. Lothaire, Combinatorics on Words, 2nd edition (Cambridge Mathematical Library, 1997).
J. Manuch, Characterization of a word by its subwords, Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999 (World Scientific, 1999), pp. 210-219.
B. Manvel, A. Meyerowitz, A. J. Schwenk, K. Smith and P. K. Stockmeyer, Reconstruction of sequences, Discret. Math. 94(3) (1991) 209-219.
B. Manvel and P. K. Stockmeyer, On reconstruction of matrices, Math. Mag. 44 (1971) 218-221.
P. O'Neil, Ulam's conjecture and graph reconstructions, Amer. Math. Monthly 77 (1970) 35-43.
C. Reutenauer, Free Lie Algebras, Vol. 7, London Math. Soc. Monogr. (N.S.) (Oxford University Press, 1993).
M. Rigo and P. Salimov, Another generalization of abelian equivalence: Binomial complexity of infinite words, Theor. Comput. Sci. 601 (2015) 47-57.
I. Simon, Piecewise testable events, Automata Theory and Formal Languages, 2nd GI Conference, Kaiserslautern, May 20-23, 1975, Lecture Notes in Computer Science, Vol. 33 (Springer, 1975), pp. 214-222.
L. van Iersel and V. Moulton, Leaf-reconstructibility of phylogenetic networks, SIAM J. Discret. Math. 32(3) (2018) 2047-2066.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.