4 citations · 6 across the 9 of their papers we have counts for
6 papers · 1 filter
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…