31 citations · 86 across the 21 of their papers we have counts for
22 papers
Martin Davis: An Overview of his Work in Logic, Computer Science, and Philosophy
Liesbeth De Mol, Yuri V. Matiyasevich, Eugenio G. Omodeo +3
In his autobiographic essay written in 1999, ``From logic to computer science and back'', Martin David Davis (3/8/1928--1/1/2023) indicated that he viewed himself as a logician \em…
Universally Wheeler Languages
Ruben Becker, Giuseppa Castiglione, Giovanna D'Agostino +4
The notion of Wheeler languages is rooted in the Burrows-Wheeler transform (BWT), one of the most central concepts in data compression and indexing. The BWT has been generalized to…
On the Complexity of Computing the Co-lexicographic Width of a Regular Language
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +4
Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA 2021 and JACM 2023) as a powerful tool to index finite state automata, with applications to regular expre…
In Memory of Martin Davis
Wesley Calvert, Valentina Harizanov, Eugenio G. Omodeo +2
The present paper gives an account for the general mathematical reader of the life and work of Martin Davis. Since two rather comprehensive autobiographical accounts and two long b…
Optimal Wheeler Language Recognition
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +3
A Wheeler automaton is a finite state automaton whose states admit a total Wheeler order, reflecting the co-lexicographic order of the strings labeling source-to-node paths. A Whee…
Co-lexicographically Ordering Automata and Regular Languages -- Part I
Nicola Cotumaccio, Giovanna D'Agostino, Alberto Policriti +1
In the present work, we lay out a new theory showing that all automata can always be co-lexicographically partially ordered, and an intrinsic measure of their complexity can be def…
Ordering Regular Languages and Automata: Complexity
Giovanna D'Agostino, Davide Martincigh, Alberto Policriti
Given an order of the underlying alphabet we can lift it to the states of a finite deterministic automaton: to compare states we use the order of the strings reaching them. When th…
The Labeled Direct Product Optimally Solves String Problems on Graphs
Nicola Rizzo, Alexandru I. Tomescu, Alberto Policriti
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matchin…
Ordering regular languages: a danger zone
Giovanna D'Agostino, Davide Martincigh, Alberto Policriti
Ordering the collection of states of a given automaton starting from an order of the underlying alphabet is a natural move towards a computational treatment of the language accepte…
On (co-lex) Ordering Automata
Giovanna D'Agostino, Nicola Cotumaccio, Alberto Policriti +1
The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted…
Co-lexicographically Ordering Automata and Regular Languages -- Part II
Nicola Cotumaccio, Giovanna D'Agostino, Alberto Policriti +1
In the present work, we tackle the regular language indexing problem by first studying the hierarchy of -sortable languages: regular languages accepted by automata of width .…
Wheeler Languages
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti +1
The recently introduced class of Wheeler graphs, inspired by the Burrows-Wheeler Transform (BWT) of a given string, admits an efficient index data structure for searching for subpa…
Adding the Power-Set to Description Logics
Laura Giordano, Alberto Policriti
We explore the relationships between Description Logics and Set Theory. The study is carried on using, on the set-theoretic side, a very rudimentary axiomatic set theory Omega, con…
Regular Languages meet Prefix Sorting
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti +1
Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages…
Encoding Sets as Real Numbers (Extended version)
Domenico Cantone, Alberto Policriti
We study a variant of the Ackermann encoding of the hereditarily finite sets by the natural numbers, applicable to the larger coll…
String Attractors: Verification and Optimization
Dominik Kempa, Alberto Policriti, Nicola Prezza +1
String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set is a…
An Active Learning Approach to the Falsification of Black Box Cyber-Physical Systems
Simone Silvetti, Alberto Policriti, Luca Bortolussi
Search-based testing is widely used to find bugs in models of complex Cyber-Physical Systems. Latest research efforts have improved this approach by casting it as a falsification p…
From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back
Alberto Policriti, Nicola Prezza
The Lempel-Ziv factorization (LZ77) and the Run-Length encoded Burrows-Wheeler Transform (RLBWT) are two important tools in text compression and indexing, being their sizes and…
Fast Longest Common Extensions in Small Space
Alberto Policriti, Nicola Prezza
In this paper we address the longest common extension (LCE) problem: to compute the length of the longest common prefix between any two suffixes of with $ Σ= \{0,…
Computing LZ77 in Run-Compressed Space
Nicola Prezza, Alberto Policriti
In this paper, we show that the LZ77 factorization of a text T {\inΣ^n} can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the B…
Programmable models of growth and mutation of cancer-cell populations
Luca Bortolussi, Alberto Policriti
In this paper we propose a systematic approach to construct mathematical models describing populations of cancer-cells at different stages of disease development. The methodology w…
Hybrid Semantics of Stochastic Programs with Dynamic Reconfiguration
Luca Bortolussi, Alberto Policriti
We begin by reviewing a technique to approximate the dynamics of stochastic programs --written in a stochastic process algebra-- by a hybrid system, suitable to capture a mixed dis…