Paper Info
Title
State Complexity Of Overlap Assembly
Abstract
The state complexity of a regular language Lm is the number m of states in a minimal deterministic finite automaton (DFA) accepting L-m. 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 determine, for m >= 2, n >= 3, the exact value of the state complexity of the binary operation overlap assembly on regular languages. This operation was introduced by Csuhaj-Varju, 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)3(n-1) + 2(n). Moreover, for m >= 2 and n >= 3 there exist languages L-m and L-n 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 the state complexity of the overlap assembly in the case of unary languages and that there are binary languages whose overlap assembly has exponential state complexity at least m(2(n-1) - 2) + 2.
Year
DOI
Venue
2020
10.1142/S012905412042006X
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Overlap assembly, regular language, state complexity, tight upper bound
Journal
31
Issue
ISSN
Citations 
8
0129-0541
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Janusz A. Brzozowski171.74
Lila Kari21123124.45
Bai Li3102.33
Marek Szykuła400.34