4 papers · 1 filter
A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
Nicola Cotumaccio
The model of generalized automata, introduced by Eilenberg in 1974, allows representing a regular language more concisely than conventional automata by allowing edges to be labeled…
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…
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 .…