SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET
- Bonomo, S.
- Mantaci, S.
- Restivo, A.
- Rosone, G.
- Sciortino, M.
DOIAbstract
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 <lex and 7a\u3c9, that, even if strictly connected, are quite different from the computational point of view. In particular, we introduce a method that only uses the <lex sorting among suffixes of a multiset of words in order to sort their conjugates according to 7a\u3c9-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...
Add to ORKG