State Complexity of Two Combined Operations: Reversal-Catenation and Star-Catenation
arXiv:1006.4646
Abstract
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.
20 pages, 7 figures