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 metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02088082
Contributor : Pascal Caron <>
Submitted on : Tuesday, April 2, 2019 - 3:27:14 PM
Last modification on : Wednesday, April 3, 2019 - 1:59:59 AM

Links full text

Identifiers

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

Citation

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

Share

Metrics

Record views

15