State Complexity of Two Combined Operations: Reversal-Catenation and Star-Catenation

Bo Cui, Yuan Gao, Lila Kari, Sheng Yu

In this paper, we show that, due to the structural properties of the resulting automaton obtained from a prior operation, the state complexity of a combined operation may not be equal but close to the mathematical composition of the state complexities of its component operations. In particular, we provide two witness combined operations: reversal combined with catenation and star combined with catenation.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment