50 citations · 416 across the 42 of their papers we have counts for
51 papers
Digital Convexity and Combinatorics on Words
Alessandro De Luca, Gabriele Fici, Andrea Frosini
An upward (resp. downward) digitally convex word is a binary word that best approximates from below (resp. from above) an upward (resp. downward) convex curve in the plane. We stud…
Some Results on Digital Segments and Balanced Words
Alessandro De Luca, Gabriele Fici
We exhibit combinatorial results on Christoffel words and binary balanced words that are motivated by their geometric interpretation as approximations of digital segments. We give…
Maximal Closed Substrings
Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici +1
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper we introduce the definition of a \emph{maximal closed substring} (MCS), w…
On the Lie complexity of Sturmian words
Alessandro De Luca, Gabriele Fici
Bell and Shallit recently introduced the Lie complexity of an infinite word as the function counting for each length the number of conjugacy classes of words whose elements are…
Abelian Combinatorics on Words: a Survey
Gabriele Fici, Svetlana Puzynina
We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of c…
Properties of a Class of Toeplitz Words
Gabriele Fici, Jeffrey Shallit
We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form , where is a…
Adaptive Learning of Compressible Strings
Gabriele Fici, Nicola Prezza, Rossano Venturini
Suppose an oracle knows a string that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is a substring of ?". In 1995, Skiena an…
Substring Complexity in Sublinear Space
Giulia Bernardini, Gabriele Fici, Paweł Gawrychowski +1
Shannon's entropy is a definitive lower bound for statistical compression. Unfortunately, no such clear measure exists for the compressibility of repetitive strings. Thus, ad hoc m…
Primitive Sets of Words
Giuseppa Castiglione, Gabriele Fici, Antonio Restivo
Given a (finite or infinite) subset of the free monoid over a finite alphabet , the rank of is the minimal cardinality of a set such that . We…
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A prefix normal word is a binary word with the property that no substring has more s than the prefix of the same length. By proving that the set of prefix normal words is a bubb…
Minimal Absent Words in Rooted and Unrooted Trees
Gabriele Fici, Paweł Gawrychowski
We extend the theory of minimal absent words to (rooted and unrooted) trees, having edges labeled by letters from an alphabet of cardinality . We show that the set $\text{MA…
Constructing Antidictionaries in Output-Sensitive Space
Lorraine A. K. Ayad, Golnaz Badkobeh, Gabriele Fici +2
A word that is absent from a word is called minimal if all its proper factors occur in . Given a collection of words over an alphabet , we ar…
Abelian Anti-Powers in Infinite Words
Gabriele Fici, Mickael Postic, Manuel Silva
An abelian anti-power of order (or simply an abelian -anti-power) is a concatenation of consecutive words of the same length having pairwise distinct Parikh vectors. Thi…
On Sets of Words of Rank Two
Giuseppa Castiglione, Gabriele Fici, Antonio Restivo
Given a (finite or infinite) subset of the free monoid over a finite alphabet , the rank of is the minimal cardinality of a set such that . A…
Alignment-free sequence comparison using absent words
Panagiotis Charalampopoulos, Maxime Crochemore, Gabriele Fici +2
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. Thi…
On Prefix Normal Words
Gabriele Fici, Zsuzsanna Lipták
We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length , no factor of length has more 's than the pre…
Algorithms for Anti-Powers in Strings
Golnaz Badkobeh, Gabriele Fici, Simon J. Puglisi
A string is a power (or tandem repeat) of order and period if it can decomposed into consecutive equal-length blocks of letters. Powers and periods are funda…
Minimal Forbidden Factors of Circular Words
Gabriele Fici, Antonio Restivo, Laura Rizzo
Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactor…
Abelian-Square-Rich Words
Gabriele Fici, Filippo Mignosi, Jeffrey Shallit
An abelian square is the concatenation of two words that are anagrams of one another. A word of length can contain at most distinct factors, and there exist words of l…
The sequence of open and closed prefixes of a Sturmian word
Alessandro De Luca, Gabriele Fici, Luca Q. Zamboni
A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the…
On Prefix Normal Words and Prefix Normal Forms
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A -prefix normal word is a binary word with the property that no factor has more s than the prefix of the same length; a -prefix normal word is defined analogously. These…
Anti-Powers in Infinite Words
Gabriele Fici, Antonio Restivo, Manuel Silva +1
In combinatorics of words, a concatenation of consecutive equal blocks is called a power of order . In this paper we take a different point of view and define an anti-power…
On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski +2
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings is sought containing as a factor ever…
Splicing Systems from Past to Future: Old and New Challenges
Luc Boasson, Paola Bonizzoni, Clelia De Felice +4
A splicing system is a formal model of a recombinant behaviour of sets of double stranded DNA molecules when acted on by restriction enzymes and ligase. In this survey we will conc…