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.
Wheelerness and Complementation
D'Agostino G.;Policriti A.;
2025-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
