A theory of (co-lex) ordered regular languages

Equipping the domain of a structure with some kind of order is often a fruitful move performed in both Computer Science and Mathematics. An order provides direct access to data or domain elements and sometimes allows to tackle problems otherwise too computationally difficult to cope with. In general, the price to be paid when requiring/imposing an order, is a restriction of the class of structures to which subsequent results are referred. If we do not wish to pay such a price, a partial order can be a natural alternative. In this talk I will cast these considerations onto the class of finite automata. A partial order among the states of NFAs will be obtained by "lifting" the co-lexicographic order of words reaching each state. I will then show that the width of such an order is an important parameter for finite automata: hard problems such as universality, equivalence, membership, indexing, and compression can indeed be solved very efficiently on NFAs whose partial order has a small width.