On state complexity of unions of binary factor-free languages
Ivan, Szabolcs
Original · EN
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-{m,n}. We disprove this conjecture by giving a lower bound of mn-(m+n)-2-{m,n}-2/2, which exceeds the conjectured bound whenever {m,n}≥ 10.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.