3 papers
cs.LO2025
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…
cs.FL2025
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…
cs.FL2024
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…