In the present work, we study the hierarchy of p-sortable languages: regular languages accepted by automata of width p. In this hierarchy, regular languages are sorted according to the new fundamental measure of NFA complexity p. Our main contributions are the following: (i) we show that the hierarchy is strict and does not collapse, (ii) we provide (exponential  ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs , and (iii) we characterize DFAs of minimum p for a given \mathcal L via a co-lexicographic variant of the Myhill-Nerode theorem. Our findings imply that in polynomial time  we can build an index breaking the worst-case conditional lower bound of \Omega( \pi m), whenever the input NFA's width is at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.
In the present work, we tackle the regular language indexing problem by first studying the hierarchy of p-sortable languages: regular languages accepted by automata of width p. We show that the hierarchy is strict and does not collapse, and provide (exponential in p ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs . Our bounds indicate the importance of being able to index NFAs, as they enable indexing regular languages with much faster and smaller indexes. Our second contribution solves precisely this problem, optimally: we devise a polynomial-time algorithm that indexes any NFA with the optimal value p for its width, without explicitly computing p (NP-hard to find). In particular, this implies that we can index in polynomial time the well-studied case p=1 (Wheeler NFAs). More in general, in polynomial time we can build an index breaking the worst-case conditional lower bound of \Omega( |P| m), whenever the input NFA's width is p \in o(\sqrt{m
R
study the
tackle the regular language indexing problem by first studying the
R
In this hierarchy, regular languages are sorted according to the new fundamental measure of NFA complexity p. Our main contributions are the following: (i) we
We
R
(ii) we
and
A
in p
R
, and (iii) we characterize DFAs of minimum p for a given \mathcal L via a co-lexicographic variant of the Myhill-Nerode theorem. Our findings imply that
. Our bounds indicate the importance of being able to index NFAs, as they enable indexing regular languages with much faster and smaller indexes. Our second contribution solves precisely this problem, optimally: we devise a polynomial-time algorithm that indexes any NFA with the optimal value p for its width, without explicitly computing p (NP-hard to find). In particular, this implies that we can index
A
the well-studied case p=1 (Wheeler NFAs). More in general, in polynomial time
R
\pi
|P|
R
at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.
p \in o(\sqrt{m