State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach - Archive ouverte HAL Access content directly
Journal Articles International Journal of Foundations of Computer Science Year : 2016

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.

Dates and versions

hal-02088118 , version 1 (02-04-2019)

Identifiers

Cite

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, 2016, 27 (06), pp.675-703. ⟨10.1142/S0129054116500234⟩. ⟨hal-02088118⟩
20 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More