Séminaire Algorithmique : « State complexity: Inverting a language reduces the complexity of the root operation », Alexandre Durand (LITIS, Univ. Rouen)

Automata (DFA) are state machines that accept or reject words. The set of words recognized by an automaton is its its language. Regular languages coincide with languages that can be recognized by automata. Here, we’re going to focus on a measure, namely state complexity. For rational languages, this is defined as the size of the smallest (deterministic) automaton that recognizes the language. On operations, it is defined as the action of an operation on the minimal automata of rational languages. The root and reverse operations are well-known. Their state complexity are nⁿ – n(n-1)/2 and 2ⁿ respectively. One might expect an explosion in the number of states when composing them.

The aim of this seminar will be to lay the foundations for the understanding of the problem, and then to show that not only does root-reverse composition does not produce a combinatorial explosion but in fact produces an automaton smaller than the root automaton in the worst cases.