We consider the problem of embedding a Wheeler Deterministic Finite Automaton (WDFA, in short) into an equivalent complete WDFA, preserving the order of states and the accepted language. In some cases, such a complete WDFA does not exist. We say that a WDFA is Wheeler-complete (W-complete, in short) if it cannot be properly embedded into an equivalent WDFA. We give an algorithm that, given as input a WDFA A, returns the smallest W-complete WDFA containing A: it is called the W-completion of A. We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages.
Castiglione G., Restivo A. (2024). Completing Wheeler Automata. In U. de'Liguoro, M. Palazzo, L. Roversi (a cura di), Proceedings of the 25th Italian Conference on Theoretical Computer Science (pp. 120-132). CEUR-WS.
Completing Wheeler Automata
Castiglione G.
Co-primo
;Restivo A.
Co-primo
2024-01-01
Abstract
We consider the problem of embedding a Wheeler Deterministic Finite Automaton (WDFA, in short) into an equivalent complete WDFA, preserving the order of states and the accepted language. In some cases, such a complete WDFA does not exist. We say that a WDFA is Wheeler-complete (W-complete, in short) if it cannot be properly embedded into an equivalent WDFA. We give an algorithm that, given as input a WDFA A, returns the smallest W-complete WDFA containing A: it is called the W-completion of A. We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages.File | Dimensione | Formato | |
---|---|---|---|
Completion_W_automata-26.pdf
accesso aperto
Tipologia:
Versione Editoriale
Dimensione
716.87 kB
Formato
Adobe PDF
|
716.87 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.