by Olivier Carton and Chloé Rispal
Dans les article suivants, on étudie le problème de la complémentation pour ces automates. On montre que les automates déterministes n'ont pas le même pouvoir d'expression que les non déterministes. Malgré ce résultat négatif, on montre que si on se restreint aux ordres dispersés et dénombrables, alors la classe des langages rationnels est close par complémentation. Dans un premier article, on prouve le résultat pour les ordres dispersés de rang fini en utilisant la méthode de Büchi. Dans un second article, on prouve le résultat pour tous les ordres dispersés dénombrables avec une approche algébrique. On définit une généralisation des semigroupes appelés ◇-semigroupes. On montre que les ◇-semigroupes finis sont équivalents aux automates.
In the following papers, we address the problem of complementation for these automata. We show that deterministic automata do not have the same expressive power as deterministic ones. Despite this negative result, we prove that if only scattered and countable linear orderings are considered, the class of rational sets of words is closed under complementation. I a first paper, we prove the result for scattered orderings of finite ranks using Büchi's method. In a second paper, we prove the whole result for all countable scattered linear orderings using an algebraic approach. We define a generalization of semigroups, called ◇-semigroups. We show that, when finite, these ◇-semigroups are equivalent to automata.