4 citations · 6 across the 9 of their papers we have counts for
10 papers
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…
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…
Uniform Interpolation for Propositional and Modal Team Logics
Giovanna D'Agostino
In this paper we consider Modal Team Logic, a generalization of Classical Modal Logic in which it is possible to describe dependence phenomena between data. We prove that most know…
The logic of the reverse mathematics zoo
Giovanna D'Agostino, Alberto Marcone
Building on previous work by Mummert, Saadaoui and Sovine, we study the logic underlying the web of implications and nonimplications which constitute the so called reverse mathemat…
Proceedings of Second International Symposium on Games, Automata, Logics and Formal Verification
Giovanna D'Agostino, Salvatore La Torre
This volume contains the Proceedings of the Second International Symposium on Games, Automata, Languages, and Formal Verification (GandALF 2011). The conference was held in Minori…
On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components
Giovanna D'Agostino, Giacomo Lenzi
For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculu…