Wheelerness and Complementation

Wheeler languages, introduced to capture a class of regular languages compatible with an ordered and indexable structure, form a well-behaved subclass of the regular languages. In this paper, we study a little-explored property of such languages: closure under complementation. Specifically, we provide a complete characterization of Wheeler languages whose complement is also Wheeler. Our results offer a deeper understanding of the internal structure of these languages and have both theoretical implications-within the classification of regular languages-and practical applications, particularly in fields leveraging coherent orderings, such as text indexing and genomic data analysis.