{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:46:33Z","timestamp":1648809993995},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> The state complexity of a regular language [Formula: see text] is the number [Formula: see text] of states in a minimal deterministic finite automaton (DFA) accepting [Formula: see text]. 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 [Formula: see text] and [Formula: see text], respectively. We determine, for [Formula: see text], [Formula: see text], the exact value of the state complexity of the binary operation overlap assembly on regular languages. This operation was introduced by Csuhaj-Varj\u00fa, Petre, and Vaszil to model the process of self-assembly of two linear DNA strands into a longer DNA strand, provided that their ends \u201coverlap\u201d. We prove that the state complexity of the overlap assembly of languages [Formula: see text] and [Formula: see text], where [Formula: see text] and [Formula: see text], is at most [Formula: see text]. Moreover, for [Formula: see text] and [Formula: see text] there exist languages [Formula: see text] and [Formula: see text] over an alphabet of size [Formula: see text] whose overlap assembly meets the upper bound and this bound cannot be met with smaller alphabets. Finally, we prove that [Formula: see text] 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 [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s012905412042006x","type":"journal-article","created":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T03:46:01Z","timestamp":1608090361000},"page":"1113-1132","source":"Crossref","is-referenced-by-count":0,"title":["State Complexity of Overlap Assembly"],"prefix":"10.1142","volume":"31","author":[{"given":"Janusz A.","family":"Brzozowski","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3G1, Canada"}]},{"given":"Lila","family":"Kari","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3G1, Canada"}]},{"given":"Bai","family":"Li","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3G1, Canada"}]},{"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Joliot-Curie 15, PL-50-383 Wroc\u0142aw, Poland"}]}],"member":"219","published-online":{"date-parts":[[2020,12,15]]},"reference":[{"key":"S012905412042006XBIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400133"},{"issue":"1","key":"S012905412042006XBIB002","first-page":"67","volume":"23","author":"Brzozowski J. A.","year":"2018","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"S012905412042006XBIB003","series-title":"LNCS","first-page":"109","volume-title":"CIAA 2018","volume":"10977","author":"Brzozowski J. A.","year":"2018"},{"key":"S012905412042006XBIB004","first-page":"713","volume":"26","author":"Carausu A.","year":"1981","journal-title":"Revue Roumaine des Mathematiques Pures et Appliquees"},{"key":"S012905412042006XBIB005","first-page":"216","volume-title":"Proc. Transgressive Computing, TC","author":"Cheptea D.","year":"2006"},{"issue":"1","key":"S012905412042006XBIB006","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2006.12.004","volume":"374","author":"Csuhaj-Varj\u00fa E.","year":"2007","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"S012905412042006XBIB007","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0303-2647(99)00030-1","volume":"52","author":"Cukras A. R.","year":"1999","journal-title":"Biosystems"},{"issue":"11","key":"S012905412042006XBIB008","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1016\/j.ic.2009.02.009","volume":"207","author":"Domaratzki M.","year":"2009","journal-title":"Inform. Comput."},{"issue":"1","key":"S012905412042006XBIB009","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s11047-015-9538-x","volume":"16","author":"Enaganti S. K.","year":"2016","journal-title":"Nat. Comput."},{"issue":"1","key":"S012905412042006XBIB010","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ic.2017.01.009","volume":"253","author":"Enaganti S. K.","year":"2017","journal-title":"Inform. Comput."},{"key":"S012905412042006XBIB011","doi-asserted-by":"crossref","first-page":"179","DOI":"10.3233\/FI-2015-1206","volume":"138","author":"Enaganti S. K.","year":"2015","journal-title":"Fundamenta Informaticae"},{"issue":"4","key":"S012905412042006XBIB012","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1073\/pnas.97.4.1385","volume":"97","author":"Faulhammer D.","year":"2000","journal-title":"Proc. Natl. Acad. Sci."},{"key":"S012905412042006XBIB013","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/11560586_20","volume-title":"Theoretical Computer Science","volume":"3701","author":"Franco G.","year":"2005"},{"key":"S012905412042006XBIB014","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/11493785_9","volume-title":"Proc. DNA Computing, (DNA 11)","volume":"3384","author":"Franco G.","year":"2005"},{"issue":"2","key":"S012905412042006XBIB015","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s11047-010-9199-8","volume":"10","author":"Franco G.","year":"2011","journal-title":"Nat. Comput."},{"key":"S012905412042006XBIB016","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/11753681_5","volume-title":"Proc. DNA Computing, (DNA 12)","volume":"3892","author":"Franco G.","year":"2006"},{"issue":"4","key":"S012905412042006XBIB017","first-page":"251","volume":"21","author":"Gao Y.","year":"2016","journal-title":"J. Autom. Lang. Comb."},{"key":"S012905412042006XBIB018","volume-title":"The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science","author":"Golan J. S.","year":"1992"},{"key":"S012905412042006XBIB019","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.tcs.2017.02.002","volume":"682","author":"Holzer M.","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"S012905412042006XBIB020","series-title":"LNCS","first-page":"264","volume-title":"DLT","author":"Holzer M.","year":"2011"},{"key":"S012905412042006XBIB021","series-title":"LNCS","first-page":"169","volume-title":"DCFS","volume":"7386","author":"Holzer M.","year":"2012"},{"key":"S012905412042006XBIB022","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-48017-X_6","volume-title":"Proc. DNA Computing, (DNA 7)","volume":"2340","author":"Hussini S.","year":"2002"},{"issue":"1","key":"S012905412042006XBIB023","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/malq.200610030","volume":"53","author":"Ito M.","year":"2007","journal-title":"Math. Log. Quart."},{"issue":"3","key":"S012905412042006XBIB024","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1006\/jtbi.1997.0475","volume":"188","author":"Kaplan P. D.","year":"1997","journal-title":"J. Theoret. Biol."},{"key":"S012905412042006XBIB025","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/3-540-45711-9_21","volume-title":"Formal and Natural Computing","volume":"2300","author":"Kari L.","year":"2002"},{"issue":"29","key":"S012905412042006XBIB026","doi-asserted-by":"crossref","first-page":"3629","DOI":"10.1016\/j.tcs.2011.03.009","volume":"412","author":"Kopecki S.","year":"2011","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"S012905412042006XBIB027","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.mbs.2007.08.010","volume":"211","author":"Manca V.","year":"2008","journal-title":"Math. Biosci."},{"key":"S012905412042006XBIB028","doi-asserted-by":"crossref","first-page":"2143","DOI":"10.1016\/j.dam.2007.09.022","volume":"157","author":"Manea F.","year":"2009","journal-title":"Discr. Appl. Math."},{"key":"S012905412042006XBIB029","series-title":"LNCS","first-page":"532","volume-title":"Proc. Computability in Europe, CiE","volume":"4497","author":"Manea F.","year":"2007"},{"issue":"2","key":"S012905412042006XBIB030","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0304-3975(02)00659-X","volume":"296","author":"Mart\u00edn-Vide C.","year":"2003","journal-title":"Theoret. Comput. Sci."},{"issue":"5337","key":"S012905412042006XBIB032","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1126\/science.278.5337.446","volume":"278","author":"Ouyang Q.","year":"1997","journal-title":"Science"},{"issue":"22","key":"S012905412042006XBIB033","doi-asserted-by":"crossref","first-page":"10747","DOI":"10.1073\/pnas.91.22.10747","volume":"91","author":"Stemmer W. P.","year":"1994","journal-title":"Proc. Natl. Acad. Sci."},{"key":"S012905412042006XBIB034","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"Yu S.","year":"1994","journal-title":"Theoret. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412042006X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:34:05Z","timestamp":1611200045000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905412042006X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":33,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S012905412042006X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412042006x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}