2017/10/16 by Brzozowski, Janusz, Kari, Lila, Li, Bai +1
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1710.06000
The state complexity of a regular language Lm is the number m of states in a minimal deterministic finite automaton (DFA) accepting Lm. The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation where the two operands range over all languages of state complexities ≤ m and ≤ n, respectively. We find a tight upper bound on the state complexity of the binary operation overlap assembly on regular languages. This operation was introduced by Csuhaj-Varjú, Petre, and Vaszil to model the process of self-assembly of two linear DNA strands into a longer DNA strand, provided that their ends "overlap". We prove that the state complexity of the overlap assembly of languages Lm and Ln, where m≥ 2 and n≥1, is at most 2 (m-1) 3n-1 + 2n. Moreover, for m ≥ 2 and n ≥ 3 there exist languages Lm and Ln over an alphabet of size n whose overlap assembly meets the upper bound and this bound cannot be met with smaller alphabets. Finally, we prove that m+n is a tight upper bound on the overlap assembly of unary languages, and that there are binary languages whose overlap assembly has exponential state complexity at least m(2n-1-2)+2.