State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach

Pascal Caron; Jean-Gabriel Luque; Ludovic Mignot; Bruno Patrou

doi:10.1142/S0129054116500234

Journal articles

State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach

Pascal Caron ^{1, 2} Jean-Gabriel Luque ^{1, 2} Ludovic Mignot ^{3, 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

2 UNIROUEN - Université de Rouen Normandie

3 LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes

Abstract : We study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we relate this work with the study of state complexity for two other combinations: catenation with union and catenation with intersection. We extract a unified approach which allows to obtain the state complexity of any combination involving catenation and a binary boolean operation.

Keywords : State complexity boolean operations catenation Brzozowski automata

Document type :

Journal articles

Domain :

Computer Science [cs]

Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02088118
Contributor : Pascal Caron <>
Submitted on : Tuesday, April 2, 2019 - 3:43:24 PM
Last modification on : Tuesday, July 23, 2019 - 9:26:45 AM

State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach

Links full text

Identifiers

Collections

Citation

Export

Metrics

30

State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach

Links full text

Identifiers

Collections

Citation

Export

Share

Metrics

30