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.
2024
Settore INFO-01/A - Informatica
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.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/666813
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact