Wheelerness and Complementation

Abstract

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.