Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Pascal Caron Connect in order to contact the contributor
Submitted on : Tuesday, April 2, 2019 - 3:27:14 PM
Last modification on : Wednesday, March 2, 2022 - 10:10:10 AM

Links full text


  • HAL Id : hal-02088082, version 1
  • ARXIV : 1707.03174


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



Record views