{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:42:12Z","timestamp":1742974932608,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":31,"publisher":"Springer Singapore","isbn-type":[{"type":"print","value":"9789811534140"},{"type":"electronic","value":"9789811534157"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-981-15-3415-7_7","type":"book-chapter","created":{"date-parts":[[2020,4,1]],"date-time":"2020-04-01T19:02:58Z","timestamp":1585767778000},"page":"79-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Probe Machine Based Computing Model for Solving Satisfiability Problem"],"prefix":"10.1007","author":[{"given":"Jianzhong","family":"Cui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhixiang","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianya","family":"Geng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,2]]},"reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cor.2015.11.004","volume":"68","author":"O Sobeyko","year":"2016","unstructured":"Sobeyko, O., Monch, L.: Heuristic approaches for scheduling jobs in large-scale flexible job shops. Comput. Oper. Res. 68, 97\u2013109 (2016)","journal-title":"Comput. Oper. Res."},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2016.09.014","volume":"653","author":"K Cechlrov","year":"2016","unstructured":"Cechlrov, K., Fleiner, T., Manlove, D.F., McBride, I.: Stable matchings of teachers to schools. Theoret. Comput. Sci. 653, 15\u201325 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.dam.2015.02.015","volume":"216","author":"VV Lozin","year":"2015","unstructured":"Lozin, V.V., Malyshev, D.S.: Vertex coloring of graphs with few obstructions. Discrete Appl. Math. 216, 273\u2013280 (2015)","journal-title":"Discrete Appl. Math."},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.dam.2016.10.025","volume":"219","author":"DS Malyshev","year":"2016","unstructured":"Malyshev, D.S., Lobanova, O.O.: Two complexity results for the vertex coloring problem. Discrete Appl. Math. 219, 158\u2013166 (2016)","journal-title":"Discrete Appl. Math."},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.dam.2015.10.039","volume":"209","author":"H Li","year":"2016","unstructured":"Li, H., Bai, Y., He, W., Sun, Q.: Vertex-distinguishing proper arc colorings of digraphs. Discrete Appl. Math. 209, 276\u2013286 (2016)","journal-title":"Discrete Appl. Math."},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2016.10.011","volume":"659","author":"M Karpiski","year":"2017","unstructured":"Karpiski, M.: Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete. Theor. Comput. Sci. 659, 88\u201394 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2017.02.005","volume":"674","author":"Y Shitov","year":"2017","unstructured":"Shitov, Y.: A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length. Theor. Comput. Sci. 674, 116\u2013118 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"7_CR9","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.orl.2016.03.015","volume":"44","author":"JS Borrero","year":"2016","unstructured":"Borrero, J.S., Gillen, C., Prokopyev, O.A.: A simple technique to improve linearized reformulations of fractional (hyperbolic) 0\u20131 programming problems. Oper. Res. Lett. 44(4), 479\u2013486 (2016)","journal-title":"Oper. Res. Lett."},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.ins.2017.03.014","volume":"400","author":"A Kodama","year":"2017","unstructured":"Kodama, A., Nishi, T.: Petri net representation and reachability analysis of 0\u20131 integer linear programming problems. Inf. Sci. 400, 157\u2013172 (2017)","journal-title":"Inf. Sci."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.dam.2016.08.007","volume":"218","author":"K Yan","year":"2017","unstructured":"Yan, K., Ryoo, H.S.: 0\u20131 multilinear programming as a unifying theory for LAD pattern generation. Discrete Appl. Math. 218, 21\u201339 (2017)","journal-title":"Discrete Appl. Math."},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-540-24622-0_9","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"E Clarke","year":"2004","unstructured":"Clarke, E., Kroening, D., Ouaknine, J., Strichman, O.: Completeness and complexity of bounded model checking. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 85\u201396. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-24622-0_9"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/11513988_6","volume-title":"Computer Aided Verification","author":"R Jhala","year":"2005","unstructured":"Jhala, R., McMillan, K.L.: Interpolant-based transition relation approximation. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 39\u201351. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11513988_6"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-18275-4_7","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"AR Bradley","year":"2011","unstructured":"Bradley, A.R.: SAT-based model checking without unrolling. In: Jhala, R., Schmidt, D. (eds.) VMCAI 2011. LNCS, vol. 6538, pp. 70\u201387. Springer, Heidelberg (2011). \nhttps:\/\/doi.org\/10.1007\/978-3-642-18275-4_7"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"LM Adleman","year":"1994","unstructured":"Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021\u20131024 (1994)","journal-title":"Science"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1126\/science.1069528","volume":"296","author":"RS Braich","year":"2002","unstructured":"Braich, R.S., Chelyapov, N., Johnson, C.P., Rothemund, W.K., Adleman, L.M.: Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296, 499\u2013502 (2002)","journal-title":"Science"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1023\/A:1023980828489","volume":"4","author":"N Jonoska","year":"2003","unstructured":"Jonoska, N., Sa-Ardyen, P., Seeman, N.C.: Computation by self-assembly of DNA graphs. Genet. Program Evolvable Mach. 4(2), 123\u2013137 (2003)","journal-title":"Genet. Program Evolvable Mach."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1090\/dimacs\/054\/02","volume":"54","author":"H Yoshida","year":"2000","unstructured":"Yoshida, H.: Solution to 3-SAT by breadth first search. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 54, 9\u201320 (2000)","journal-title":"DIMACS Ser. Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.biosystems.2005.01.001","volume":"81","author":"CN Yang","year":"2005","unstructured":"Yang, C.N., Yang, C.B.: A DNA solution of SAT problem by a modified sticker model. BioSystems 81(1), 1\u20139 (2005)","journal-title":"BioSystems"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.biosystems.2007.08.006","volume":"91","author":"XL Wang","year":"2008","unstructured":"Wang, X.L., Bao, Z.M., Hu, J.J., Wang, S., Zhan, A.B.: Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction. BioSystems 91(1), 117\u2013125 (2008)","journal-title":"BioSystems"},{"issue":"6","key":"7_CR21","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1016\/j.jcss.2016.03.008","volume":"82","author":"BS Song","year":"2016","unstructured":"Song, B.S., Prez-Jimnez, M.J., Pan, L.Q.: An efficient time-free solution to SAT problem by P systems with proteins on membranes. J. Comput. Syst. Sci. 82(6), 1090\u20131099 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"7_CR22","doi-asserted-by":"publisher","first-page":"506C521","DOI":"10.1109\/12.769433","volume":"48","author":"JP Marques-Silva","year":"1999","unstructured":"Marques-Silva, J.P., Sakallah, K.: GRASP: a search algorithm for propositional satisfiability. IEEE Trans. Comput. 48(5), 506C521 (1999)","journal-title":"IEEE Trans. Comput."},{"key":"7_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-642-02777-2_33","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"C Sinz","year":"2009","unstructured":"Sinz, C., Iser, M.: Problem-sensitive restart heuristics for the DPLL procedure. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 356\u2013362. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-02777-2_33"},{"key":"7_CR24","unstructured":"Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-SAT formulae. In: Proceedings of IJCAI, pp. 248\u2013253 (2001)"},{"issue":"11","key":"7_CR25","doi-asserted-by":"publisher","first-page":"2021","DOI":"10.1109\/JPROC.2015.2455034","volume":"103","author":"Y Vizel","year":"2015","unstructured":"Vizel, Y., Weissenbacher, G., Malik, S.: Boolean satisfiability solvers and their applications in model checking. Proc. IEEE 103(11), 2021\u20132035 (2015)","journal-title":"Proc. IEEE"},{"issue":"3","key":"7_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1080\/0952813X.2014.954274","volume":"27","author":"A Palu Dal","year":"2015","unstructured":"Dal Palu, A., Dovier, A., Formisano, A., Pontelli, E.: CUD@SAT: SAT solving on GPUS. J. Exp. Theor. Artif. Intell. 27(3), 293\u2013316 (2015)","journal-title":"J. Exp. Theor. Artif. Intell."},{"key":"7_CR27","unstructured":"Lamya, A,G., Aziza, I.H., Hanafy, M.A.: Parallelization of unit propagation algorithm for SAT-based ATPG of digital circuits. In: Proceedings of ICM, pp. 184\u2013188 (2016)"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.jpdc.2016.12.014","volume":"106","author":"AA Sohanghpurwala","year":"2017","unstructured":"Sohanghpurwala, A.A., Hassan, M.W., Athanas, P.: Hardware accelerated SAT solvers\u2014a survey. J. Parallel Distrib. Comput. 106, 170\u2013184 (2017)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"12","key":"7_CR29","doi-asserted-by":"publisher","first-page":"1514","DOI":"10.1016\/j.dam.2006.10.004","volume":"155","author":"H Kautz","year":"2007","unstructured":"Kautz, H., Selman, B.: The state of SAT. Discrete Appl. Math. 155(12), 1514\u20131524 (2007)","journal-title":"Discrete Appl. Math."},{"key":"7_CR30","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic \u2018phase transitions\u2019. Nature 400, 133\u2013137 (1999)","journal-title":"Nature"},{"issue":"3","key":"7_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF03037360","volume":"20","author":"M Arita","year":"2002","unstructured":"Arita, M., Kobayashi, S.: DNA sequence design using templates. New Gener. Comput. 20(3), 263\u2013277 (2002). \nhttps:\/\/doi.org\/10.1007\/BF03037360","journal-title":"New Gener. Comput."}],"container-title":["Communications in Computer and Information Science","Bio-inspired Computing: Theories and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-15-3415-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,2]],"date-time":"2020-04-02T01:21:54Z","timestamp":1585790514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-15-3415-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9789811534140","9789811534157"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-981-15-3415-7_7","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"2 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"BIC-TA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Bio-Inspired Computing: Theories and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zhengzhou","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 November 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 November 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"bicta2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/2019.bicta.org","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"197","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"121","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"61% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}