State complexity of catenation combined with boolean operations

Pascal Caron (1, 2) , Jean-Gabriel Luque (1, 2) , Bruno Patrou (1, 2)

1 CA - LITIS - Equipe Combinatoire et algorithmes
2 UNIROUEN - Université de Rouen Normandie

We exhaustively investigate possible combinations of a boolean operation together with a catenation. In many cases we prove and improve some conjectures by Brzozowski. For each family of operation, we endeavour to provide a common witness with a small size alphabet.

Domains: Computer Science [cs]

Pascal Caron, Jean-Gabriel Luque, Bruno Patrou. State complexity of catenation combined with boolean operations. 2019. ⟨hal-02088082⟩