0000000000268052
AUTHOR
A. Restivo
Sorting suffixes of a text via its Lyndon Factorization
The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the suffix array, widely used in several fields of Computer Science. For this reason, several recent researches have been devoted to finding new strategies to obtain effective methods for such a sorting. In this paper we introduce a new methodology in which an important role is played by the Lyndon factorization, so that the local suffixes inside factors detected by this factorization keep their mutual order when extended to the suffixes of the whole word. This property suggests a versatile technique that easily can b…
Coding Sequences with Constraints
In this paper we consider the following problem: given all bi-infinite sequences of symbols satisfying certain constraints, search for a set X of words such that i): any concatenation of elements of X satisfies these constraints and ii): any sequence verifying the constraints can be “parsed” in elements of X.
The Star Height One Problem for Irreducible Automata
The star height of a regular expression is, informally, the maximum number of nested stars in the expression. The star height of a regular language is the minimal star height of a regular expression denoting this language. The notion of star height indicates in a certain sense the “loop complexity” of a regular expression and thus it gives a measure of the complexity of a regular language.