Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
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

Links full text

Identifiers

Citation

Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot, Bruno Patrou. State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach. International Journal of Foundations of Computer Science, World Scientific Publishing, 2016, 27 (06), pp.675-703. ⟨10.1142/S0129054116500234⟩. ⟨hal-02088118⟩

Share

Metrics

Record views

30