Indexing Finite State Automata via Co-lex orders

Ordering data structure is a powerful operation that can significantly enhance query performance. Building on this concept, there has been growing interest in co-lexicographically sorting the states of a non-deterministic finite state automaton (NFA) to construct an efficient index. This index compresses the NFA while allowing to perform pattern matching queries on it, like locating how many states can be reached by a given string. This thesis aims to study and refine an existing NFA index that leverages this ordering. The main contributions include a clear exposition of the underlying intuitions and examples demonstrating how the index operates. Additionally, it is shown that the index is an encoding data structure under certain conditions for the order. Furthermore, a variation of the original index is proposed that is more practical for real-case scenarios, and different implementations are provided to explore the space-time trade-off.