16 citations · 39 across the 17 of their papers we have counts for
22 papers
Two-dimensional Dyck words
Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro
We propose different ways of lifting the notion of Dyck language from words to 2-dimensional (2D) pictures, by means of new definitions of increasing comprehensiveness. Two of the…
Recognizability in S-adic shifts
Marie-Pierre Béal, Dominique Perrin, Antonio Restivo +1
We investigate questions related to the notion of recognizability of sequences of morphisms, a generalization of Moss{é}'s Theorem. We consider the most general class of morphisms…
BosonSampling.jl: A Julia package for quantum multi-photon interferometry
Benoit Seron, Antoine Restivo
We present a free open source package for high performance simulation and numerical investigation of boson samplers and, more generally, multi-photon interferometry. Our package is…
Possibilistic approach to network nonlocality
Antoine Restivo, Nicolas Brunner, Denis Rosset
The investigation of Bell nonlocality traditionally relies on joint probabilities of observing certain measurement outcomes. In this work we explore a possibilistic approach, where…
Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
Stefano {Crespi Reghizzi}, Antonio Restivo, Pierluigi {San Pietro}
A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of…
String Attractors and Infinite Words
Antonio Restivo, Giuseppe Romana, Marinella Sciortino
The notion of string attractor has been introduced in [Kempa and Prezza, 2018] in the context of Data Compression and it represents a set of positions of a finite word in which all…
A New Class of String Transformations for Compressed Text Indexing
Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo +2
Introduced about thirty years ago in the field of Data Compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance…
A note on one-sided recognizable morphisms
Marie-Pierre Béal, Valérie Berthé, Dominique Perrin +1
We revisit the notion of one-sided recognizability of morphisms and its relation to two-sided recognizability.
Decidable problems in substitution shifts
Marie-Pierre Béal, Dominique Perrin, Antonio Restivo
In this paper, we investigate the structure of the most general kind of substitution shifts, including non-minimal ones, and allowing erasing morphisms. We prove the decidability o…
Recognizability of morphisms
Marie-Pierre Béal, Dominique Perrin, Antonio Restivo
We investigate several questions related to the notion of recognizable morphism. The main result is a new proof of Mossé's theorem and actually of a generalization to non primitive…
A new distance based on minimal absent words and applications to biological sequences
Giuseppa Castiglione, Jia Gao, Sabrina Mantaci +1
A minimal absent word of a sequence x, is a sequence yt hat is not a factorof x, but all of its proper factors are factors of x as well. The set of minimal absent words uniquely de…
Unambiguously coded shifts
Marie-Pierre Béal, Dominique Perrin, Antonio Restivo
We study the coded systems introduced by Blanchard and Hansel. We give several constructions which allow one to represent a coded system as a strongly unambiguous one.
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…
String Attractors and Combinatorics on Words
Sabrina Mantaci, Antonio Restivo, Giuseppe Romana +2
The notion of \emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-ba…
The Alternating BWT: an algorithmic perspective
Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo +2
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures,…
Some variations on Lyndon words
Francesco Dolce, Antonio Restivo, Christophe Reutenauer
In this paper we compare two finite words and by the lexicographical order of the infinite words and . Informally, we say that we compare and by the infi…
On generalized Lyndon words
Francesco Dolce, Antonio Restivo, Christophe Reutenauer
A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every…
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…
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…
Birecurrent sets
Francesco Dolce, Dominique Perrin, Antonio Restivo +2
A set is called recurrent if its minimal automaton is strongly connected and birecurrent if it is recurrent as well as its reversal. We prove a series of results concerning birecur…
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…
Sorting suffixes of a text via its Lyndon Factorization
Sabrina Mantaci, Antonio Restivo, Giovanna Rosone +1
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…