.png){kind=icon}
.png){kind=icon}
Return
Completing Wheeler Automata
.png){kind=icon}
OA
AI
DOI：10.1016/j.tcs.2025.115631.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 DFA containing A: it is called the minimal 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.
Keywords:
Wheeler Automata
Complete Automata
Boolean Operations
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.