{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T19:06:20Z","timestamp":1768590380791,"version":"3.49.0"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DFG Grant","award":["5725\/2-1"],"award-info":[{"award-number":["5725\/2-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>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 [Formula: see text] can be reconstructed from the number of occurrences of at most [Formula: see text] scattered factors of the form [Formula: see text], where [Formula: see text] is the number of occurrences of the letter [Formula: see text] in [Formula: see text]. Moreover, we generalise the result to alphabets of the form [Formula: see text] by showing that at most [Formula: see text] scattered factors suffices to reconstruct [Formula: see text]. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.<\/jats:p>","DOI":"10.1142\/s0129054121420016","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T14:13:41Z","timestamp":1620656021000},"page":"619-640","source":"Crossref","is-referenced-by-count":7,"title":["Reconstructing Words from Right-Bounded-Block Words"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1531-7970","authenticated-orcid":false,"given":"Pamela","family":"Fleischmann","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5620-8052","authenticated-orcid":false,"given":"Marie","family":"Lejeune","sequence":"additional","affiliation":[{"name":"D\u00e9partement de Math\u00e9matiques, University of Li\u00e8ge, All\u00e9e de la d\u00e9couverte 12, 4000 Li\u00e8ge, Belgium"}]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of G\u00f6ttingen, Goldschmidtstr. 7, 37077 G\u00f6ttingen, Germany"}]},{"given":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7463-8507","authenticated-orcid":false,"given":"Michel","family":"Rigo","sequence":"additional","affiliation":[{"name":"D\u00e9partement de Math\u00e9matiques, University of Li\u00e8ge, All\u00e9e de la d\u00e9couverte 12, 4000 Li\u00e8ge, Belgium"}]}],"member":"219","published-online":{"date-parts":[[2021,5,7]]},"reference":[{"key":"S0129054121420016BIB001","volume-title":"Handbook of Formal Languages, Volume 3: Beyond Words","author":"Rozenberg G.","year":"1997"},{"key":"S0129054121420016BIB002","first-page":"178","volume":"79","author":"Berstel J.","year":"2003","journal-title":"Bull. EATCS"},{"key":"S0129054121420016BIB003","doi-asserted-by":"publisher","DOI":"10.4171\/OWR\/2010\/37"},{"key":"S0129054121420016BIB004","first-page":"4:1","volume":"126","author":"Bringmann K.","year":"2019","journal-title":"STACS"},{"key":"S0129054121420016BIB005","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S0129054121420016BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-004-0232-4"},{"key":"S0129054121420016BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00103-1"},{"issue":"4","key":"S0129054121420016BIB010","doi-asserted-by":"crossref","first-page":"605","DOI":"10.4310\/MAA.2000.v7.n4.a1","volume":"7","author":"Foster W.","year":"2000","journal-title":"Methods Appl. Anal."},{"key":"S0129054121420016BIB014","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.961"},{"key":"S0129054121420016BIB015","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2732"},{"key":"S0129054121420016BIB016","first-page":"241","volume":"2","author":"Levenshtein V. I.","year":"1992","journal-title":"Discr. Math. Appl."},{"key":"S0129054121420016BIB017","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097"},{"key":"S0129054121420016BIB018","first-page":"210","volume-title":"Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6\u20139 July 1999","author":"Manuch J.","year":"1999"},{"key":"S0129054121420016BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90026-X"},{"key":"S0129054121420016BIB021","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1970.11992413"},{"key":"S0129054121420016BIB022","series-title":"London Math. Soc. Monogr. (N.S.)","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198536796.001.0001","volume-title":"Free Lie Algebras","volume":"7","author":"Reutenauer C.","year":"1993"},{"key":"S0129054121420016BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.025"},{"key":"S0129054121420016BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07407-4_23"},{"key":"S0129054121420016BIB025","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111930"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121420016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T15:07:00Z","timestamp":1725030420000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121420016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,7]]},"references-count":19,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.1142\/S0129054121420016"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121420016","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,7]]}}}