2014/05/06 by Ivan, Szabolcs
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1405.1107
It has been conjectured in 2011 by Brzozowski et al. that if K and L are factor-free regular languages over a binary alphabet having state complexity m and n, resp, then the state complexity of K∪ L is at most mn-(m+n)+3-min\m,n\. We disprove this conjecture by giving a lower bound of mn-(m+n)-2-\lfloor\fracmin\m,n\-22\rfloor, which exceeds the conjectured bound whenever min\m,n\≥ 10.