{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T03:58:40Z","timestamp":1770523120384,"version":"3.49.0"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> In this paper we are interested in the study of the combinatorial aspects related to the extension of the Burrows-Wheeler transform to a multiset of words. Such study involves the notion of suffixes and conjugates of words and is based on two different order relations, denoted by &lt;<jats:sub>lex<\/jats:sub> and \u227a<jats:sub>\u03c9<\/jats:sub>, that, even if strictly connected, are quite different from the computational point of view. In particular, we introduce a method that only uses the &lt;<jats:sub>lex<\/jats:sub> sorting among suffixes of a multiset of words in order to sort their conjugates according to \u227a<jats:sub>\u03c9<\/jats:sub>-order. In this study an important role is played by Lyndon words. This strategy could be used in applications specially in the field of Bioinformatics, where for instance the advent of \u201cnext-generation\u201d DNA sequencing technologies has meant that huge collections of DNA sequences are now commonplace. <\/jats:p>","DOI":"10.1142\/s0129054114400309","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T06:32:14Z","timestamp":1424845934000},"page":"1161-1175","source":"Crossref","is-referenced-by-count":12,"title":["SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET"],"prefix":"10.1142","volume":"25","author":[{"given":"SILVIA","family":"BONOMO","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy"}]},{"given":"SABRINA","family":"MANTACI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy"}]},{"given":"ANTONIO","family":"RESTIVO","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy"}]},{"given":"GIOVANNA","family":"ROSONE","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy"}]},{"given":"MARINELLA","family":"SCIORTINO","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Palermo, Via Archirafi 34, 90123 Palermo, Italy"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_2","first-page":"219","volume":"6661","author":"Bauer M. J.","year":"2011","journal-title":"LNCS"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.002"},{"key":"p_4","first-page":"131","volume":"7907","author":"Bonomo S.","year":"2013","journal-title":"LNCS"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.014"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90017-2"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(93)90095-P"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.019"},{"key":"p_13","first-page":"257","volume":"7354","author":"Hon W.-K.","year":"2012","journal-title":"LNCS"},{"key":"p_14","first-page":"65","volume":"2009","author":"Kufleitner M.","year":"2009","journal-title":"Proceedings of the Prague Stringology Conference"},{"key":"p_16","first-page":"178","volume":"3537","author":"Mantaci S.","year":"2005","journal-title":"LNCS"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.014"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9078-6"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/s00726-010-0547-x"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:14:21Z","timestamp":1565190861000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":14,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400309"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400309","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}