{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:53:50Z","timestamp":1757310830836},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> The problem of negative design of DNA languages is addressed, that is, properties and construction methods of large sets of words that prevent undesired bonds when used in DNA computations. We recall a few existing formalizations of the problem and then define the property of sim-bond-freedom, where sim is a similarity relation between words. We show that this property is decidable for context-free languages and polynomial-time decidable for regular languages. The maximality of this property also turns out to be decidable for regular languages and polynomial-time decidable for an important case of the Hamming similarity. Then we consider various construction methods for Hamming bond-free languages, including the recently introduced method of templates, and obtain a complete structural characterization of all maximal Hamming bond-free languages. This result is applicable to the \u03b8-k-code property introduced by Jonoska and Mahalingam. <\/jats:p>","DOI":"10.1142\/s0129054105003467","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T07:41:41Z","timestamp":1129189301000},"page":"1039-1070","source":"Crossref","is-referenced-by-count":9,"title":["BOND-FREE LANGUAGES: FORMALIZATIONS, MAXIMALITY AND CONSTRUCTION METHODS"],"prefix":"10.1142","volume":"16","author":[{"given":"LILA","family":"KARI","sequence":"first","affiliation":[{"name":"Department of Computer Science,  The University of Western Ontario, London, Ontario, N6A 5B7, Canada"}]},{"given":"STAVROS","family":"KONSTANTINIDIS","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science,  Saint Mary's University, Halifax, Nova Scotia, B3H 3C3, Canada"}]},{"given":"PETR","family":"SOS\u00cdK","sequence":"additional","affiliation":[{"name":"Department of Computer Science,  The University of Western Ontario, London, Ontario, N6A 5B7, Canada"},{"name":"Institute of Computer Science,  Silesian University, 74601 Opava, Czech Republic"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037360"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1051\/ita\/1986200100891","volume":"20","author":"Ehrenfeucht A.","journal-title":"RAIRO Inform. Ther. Appl."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0751-4_11"},{"key":"rf11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2001"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90230-5"},{"key":"rf18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/3-540-45711-9_21","volume":"2300","author":"Kari L.","year":"2002"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0118-7"},{"key":"rf24","first-page":"278","volume":"8","author":"Konstantinidis S.","journal-title":"J. Universal Comp. Science"},{"key":"rf25","first-page":"201","volume":"8","author":"Condon A. E.","journal-title":"J. Computational Biology"},{"key":"rf28","volume-title":"DNA Computing. New Computing Paradigms","author":"P\u0103un G.","year":"1998"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"rf31","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"rf34","volume-title":"Theory of Computation","author":"Wood D.","year":"1987"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:41:34Z","timestamp":1565124094000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":13,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003467"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003467","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}