{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:46:09Z","timestamp":1725860769073},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319409450"},{"type":"electronic","value":"9783319409467"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40946-7_21","type":"book-chapter","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T11:52:20Z","timestamp":1467719540000},"page":"248-259","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Fixed-Height Patterned Tile Self-assembly"],"prefix":"10.1007","author":[{"given":"Shinnosuke","family":"Seki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Winslow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D Angluin","year":"1978","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets. Inf. Control 39, 337\u2013350 (1978)","journal-title":"Inf. Control"},{"key":"21_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2013.05.009","volume":"499","author":"E Czeizler","year":"2013","unstructured":"Czeizler, E., Popa, A.: Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. Theor. Comput. Sci. 499, 23\u201337 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"21_CR3","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/2380656.2380675","volume":"55","author":"D Doty","year":"2012","unstructured":"Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55(12), 78\u201388 (2012)","journal-title":"Commun. ACM"},{"issue":"4","key":"21_CR4","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397\u2013411 (1975)","journal-title":"SIAM J. Comput."},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/978-3-642-18305-8_7","volume-title":"Dna Computing and Molecular Programming","author":"M G\u00f6\u00f6s","year":"2011","unstructured":"G\u00f6\u00f6s, M., Orponen, P.: Synthesizing minimal tile sets for patterned DNA self-assembly. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16 2010. LNCS, vol. 6518, pp. 71\u201382. Springer, Heidelberg (2011)"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/978-3-642-45030-3_65","volume-title":"Algorithms and Computation","author":"AC Johnsen","year":"2013","unstructured":"Johnsen, A.C., Kao, M.-Y., Seki, S.: Computing minimum tile sets to self-assemble color patterns. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 699\u2013710. Springer, Heidelberg (2013)"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Johnsen, A.C., Kao, M.-Y., Seki, S.: A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tile set synthesis. J. Comb. Optim. (2015) (In press)","DOI":"10.1007\/s10878-015-9975-6"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1007\/978-3-662-47672-7_83","volume-title":"Automata, Languages, and Programming","author":"L Kari","year":"2015","unstructured":"Kari, L., Kopecki, S., Meunier, P.\u00c9., Patitz, M.J., Seki, S.: Binary pattern tile set synthesis is NP-hard. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 1022\u20131034. Springer, Heidelberg (2015)"},{"issue":"5","key":"21_CR9","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1109\/TCAD.2008.917973","volume":"27","author":"X Ma","year":"2008","unstructured":"Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27(5), 963\u2013967 (2008)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/978-3-642-32894-7_6","volume-title":"Unconventional Computation and Natural Computation","author":"MJ Patitz","year":"2012","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly. In: Durand-Lose, J., Jonoska, N. (eds.) UCNC 2012. LNCS, vol. 7445, pp. 34\u201362. Springer, Heidelberg (2012)"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/978-3-642-39074-6_21","volume-title":"Unconventional Computation and Natural Computation","author":"S Seki","year":"2013","unstructured":"Seki, S.: Combinatorial optimization in pattern assembly. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 220\u2013231. Springer, Heidelberg (2013)"},{"issue":"3","key":"21_CR12","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(83)90004-X","volume":"24","author":"UV Vazirani","year":"1983","unstructured":"Vazirani, U.V., Vazirani, V.V.: A natural encoding scheme proved probabilistic polynomial complete. Theor. Comput. Sci. 24(3), 291\u2013300 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR13","unstructured":"Winfree, E.: Algorithmic self-Assembly of DNA. Ph.D. thesis, Caltech (1998)"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. A 373(2046) (2015)","DOI":"10.1098\/rsta.2014.0214"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40946-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T18:29:46Z","timestamp":1568140186000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40946-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409450","9783319409467"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40946-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}