moteur de recherche

Séminaire Algo - Edwin Hamel
Séminaire Algo - Edwin Hamel
13-Apr-2021 14:00
Age: 8 days

Edwin Hamel

An algebraic theory for state complexity

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Abstract: Operational state complexity is an active topic of research in theoretical computer science. However, there is no general framework built for computing state complexities. A usual method is to compute an upper bound by resorting to some ingenious tricks, and then to provide a family of languages, called a witness, whose image by the operation matches this upper bound. Furthermore, witnesses are chosen in an ad hoc manner, and no general results are known.

In 2013, Brzozowski introduced a heuristic to find witnesses that consists in choosing them when they are "complex" in a certain sense. In order to precise and formalize this heuristic, we build a general framework designed for studying the state complexities of a large class of regular operations, which we call 1-uniform. As reasoning directly on automata is easier to compute state complexities, we build a counterpart to 1-uniform operations in the space of operations over complete, deterministic and finite automata, which we call modifiers. We show that, for any 1-uniform regular operation, we can choose a witness in a small pool of DFAs with a large alphabet.

From these results, we derive a method to compute the state complexity of any 1-uniform operation. This method can be used to recover some well-known state complexity results, like the exact state complexity of the Kleene star, catenation, or of any boolean operation. In addition, we very quickly give some ideas that we used to compute the exact state complexity of the Kleene star composed with symmetric difference, which is a new result.

Finally, we study a class of modifiers defined by simple algebraic properties, called friendly modifiers. We give the regular operations associated with friendly modifiers, and we give their maximal state complexity.

<- Back to: Accueil