{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T17:12:36Z","timestamp":1673457156298},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[1996,10]]},"abstract":"We present a Unison algorithm to evaluate arbitrarily complex Boolean expressions. This novel algorithm, based on the total differential of a Boolean function, enables fast evaluation of Boolean expressions in software. Any combination of Boolean operations can be packed into the bits of one computer word and evaluated in parallel by bitwise logical operations. Sample runs of the Unison algorithm show that many Boolean operations can evaluated in one clock cycle. The Unison algorithm is able to evaluate Boolean expressions at an execution speed that is comparable to compiled evaluation while retaining the flexibility of interpreted approaches. The algorithm lends itself well to many practical applications.<\/jats:p>","DOI":"10.1145\/238997.239009","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:28:46Z","timestamp":1027769326000},"page":"456-477","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["The Unison algorithm"],"prefix":"10.1145","volume":"1","author":[{"given":"Rok","family":"Sosi\u010d","sequence":"first","affiliation":[{"name":"Griffith Univ., Nathan, Queensland, Australia"}]},{"given":"Jun","family":"Gu","sequence":"additional","affiliation":[{"name":"Univ. of Calgary, Calgary, Alta., Canada"}]},{"given":"Robert R.","family":"Johnson","sequence":"additional","affiliation":[{"name":"Univ. of Utah, Salt Lake City"}]}],"member":"320","published-online":{"date-parts":[[1996,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/0107041","article-title":"On a theory of Boolean functions","author":"AKERS S. B.","year":"1959","unstructured":"AKERS , S. B. 1959 . On a theory of Boolean functions . J. Soc. Ind. Appl. Math. 7 , ( Dec. ), 487 - 498 . AKERS, S. B. 1959. On a theory of Boolean functions. J. Soc. Ind. Appl. Math. 7, (Dec.), 487-498.","journal-title":"J. Soc. Ind. Appl. Math. 7"},{"key":"e_1_2_1_2_1","volume-title":"24th ACM\/IEEE Design Automation Conference, 9-16","author":"BRYANT R.E.","year":"1987","unstructured":"BRYANT , R.E. , BEATTY , D. , BRACE , K. , CHO , K. , AND SHEFFLER , T. 1987 . COSMOS: A compiled simulator for MOS circuits . In 24th ACM\/IEEE Design Automation Conference, 9-16 . 10.1145\/37888.37890 BRYANT,R.E.,BEATTY, D., BRACE, K., CHO, K., AND SHEFFLER, T. 1987. COSMOS: A compiled simulator for MOS circuits. In 24th ACM\/IEEE Design Automation Conference, 9-16. 10.1145\/37888.37890"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Third ACM Symposium on Theory of Computing, 151-158","author":"COOK S. A.","year":"1971","unstructured":"COOK , S. A. 1971 . The complexity of theorem-proving procedures . In Proceedings of the Third ACM Symposium on Theory of Computing, 151-158 . 10.1145\/800157.805047 COOK, S. A. 1971. The complexity of theorem-proving procedures. In Proceedings of the Third ACM Symposium on Theory of Computing, 151-158. 10.1145\/800157.805047"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TCAD.1985.1270120","article-title":"A hardware architecture for switch-level simulation","volume":"4","author":"DALLY W.J.","year":"1985","unstructured":"DALLY , W.J. AND BRYANT , R. E. 1985 . A hardware architecture for switch-level simulation . IEEE Trans. Comput. Aided Des. 4 , 3 (July), 239-250. DALLY,W.J.AND BRYANT, R. E. 1985. A hardware architecture for switch-level simulation. IEEE Trans. Comput. Aided Des. 4, 3 (July), 239-250.","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"e_1_2_1_5_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"GAREY M.R.","unstructured":"GAREY , M.R. AND JOHNSON , D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company , San Francisco . GAREY,M.R.AND JOHNSON, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90014-4"},{"key":"e_1_2_1_7_1","first-page":"4","article-title":"Local search for satisfiability (SAT) problem","volume":"23","author":"GU J.","year":"1993","unstructured":"GU , J. 1993 . Local search for satisfiability (SAT) problem . IEEE Trans. Syst. Man, Cybern. 23 , 4 (July), 1108-1129. GU, J. 1993. Local search for satisfiability (SAT) problem. IEEE Trans. Syst. Man, Cybern. 23, 4 (July), 1108-1129.","journal-title":"IEEE Trans. Syst. Man, Cybern."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.334864"},{"key":"e_1_2_1_9_1","first-page":"105","volume-title":"DIMACS","volume":"22","author":"GU J.","year":"1995","unstructured":"GU , J. 1995 . Parallel algorithms for satisfiability (SAT) problem . In DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science, Vol. 22 , American Mathematical Society, Providence, RI , 105 - 161 . GU, J. 1995. Parallel algorithms for satisfiability (SAT) problem. In DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science, Vol. 22, American Mathematical Society, Providence, RI, 105-161."},{"key":"e_1_2_1_10_1","volume-title":"Constraint-Based Search","author":"GU J.","unstructured":"GU , J. 1996. Constraint-Based Search . Cambridge University Press , New York (to appear). GU, J. 1996. Constraint-Based Search. Cambridge University Press, New York (to appear)."},{"key":"e_1_2_1_11_1","volume-title":"DIMACS","author":"GU J.","unstructured":"GU , J. , PURDOM , P.W. , FRANCO , J. , AND WAH , B. W. 1997. Algorithms for satisfiability (SAT) problem: A survey . In DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science: The Satisfiability (SAT) Problem, American Mathematical Society, Providence, RI (to appear). GU, J., PURDOM,P.W.,FRANCO, J., AND WAH, B. W. 1997. Algorithms for satisfiability (SAT) problem: A survey. In DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science: The Satisfiability (SAT) Problem, American Mathematical Society, Providence, RI (to appear)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1987.4767988"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318.3321"},{"key":"e_1_2_1_14_1","volume-title":"Fundamentals of Data Structures","author":"HOROWITZ E.","unstructured":"HOROWITZ , E. AND SAHNI , S. 1976. Fundamentals of Data Structures . Computer Science Press , New York . HOROWITZ,E.AND SAHNI, S. 1976. Fundamentals of Data Structures. Computer Science Press, New York."},{"key":"e_1_2_1_15_1","volume-title":"Search: A survey of recent results","author":"KORF R. E.","year":"1988","unstructured":"KORF , R. E. 1988 . Search: A survey of recent results . In Exploring Artificial Intelligence, H. E. Shrobe, ed., Morgan-Kaufmann Publishers, Inc. , San Mateo, CA , Chap. 6. KORF, R. E. 1988. Search: A survey of recent results. In Exploring Artificial Intelligence, H. E. Shrobe, ed., Morgan-Kaufmann Publishers, Inc., San Mateo, CA, Chap. 6."},{"key":"e_1_2_1_16_1","volume-title":"Introduction to VLSI Systems","author":"MEAD C.","unstructured":"MEAD , C. AND CONWAY , L. 1980. Introduction to VLSI Systems . Addison-Wesley , Reading, MA . MEAD,C.AND CONWAY, L. 1980. Introduction to VLSI Systems. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.6163"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1109\/C-M.1981.220255","article-title":"Monitoring program execution: A survey","volume":"14","author":"PLATTNER B.","year":"1981","unstructured":"PLATTNER , B. AND NIEVERGELT , J. 1981 . Monitoring program execution: A survey . IEEE Comput. 14 , 11 (Nov.), 76-93. PLATTNER,B.AND NIEVERGELT, J. 1981. Monitoring program execution: A survey. IEEE Comput. 14, 11 (Nov.), 76-93.","journal-title":"IEEE Comput."},{"key":"e_1_2_1_20_1","first-page":"12","article-title":"Sequential evaluation of Boolean functions","volume":"28","author":"PLAVC SIC V.M.","year":"1979","unstructured":"PLAVC SIC , V.M. AND DANIELSSON , P. E. 1979 . Sequential evaluation of Boolean functions . IEEE Trans. Comput. 28 , 12 (Dec.), 879-887. PLAVC SIC,V.M.AND DANIELSSON, P. E. 1979. Sequential evaluation of Boolean functions. IEEE Trans. Comput. 28, 12 (Dec.), 879-887.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_21_1","first-page":"38","article-title":"A class of multiple error correcting codes and the decoding scheme. IRE","author":"REED I. S.","year":"1954","unstructured":"REED , I. S. 1954 . A class of multiple error correcting codes and the decoding scheme. IRE Trans. Inf. Theory IT-4. ( Sept. ), 38 - 49 . REED, I. S. 1954. A class of multiple error correcting codes and the decoding scheme. IRE Trans. Inf. Theory IT-4. (Sept.), 38-49.","journal-title":"Trans. Inf. Theory IT-4."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1109\/TC.1968.227417","article-title":"Analyzing errors with the Boolean difference","volume":"17","author":"SELLERS F.","year":"1968","unstructured":"SELLERS , F. , JR ., HSIAO , M.Y. , AND BEARNSON , L. W. 1968 . Analyzing errors with the Boolean difference . IEEE Trans. Comput. 17 , ( July ), 676 - 683 . SELLERS, F., JR., HSIAO,M.Y.,AND BEARNSON, L. W. 1968. Analyzing errors with the Boolean difference. IEEE Trans. Comput. 17, (July), 676-683.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_23_1","article-title":"A universal Boolean evaluator","author":"SOSIC R.","year":"1996","unstructured":"SOSIC , R. , GU , J. , AND JOHNSON , R. 1996 . A universal Boolean evaluator . IEEE Trans. Comput. (to appear). SOSIC, R., GU, J., AND JOHNSON, R. 1996. A universal Boolean evaluator. IEEE Trans. Comput. (to appear).","journal-title":"IEEE Trans. Comput. (to appear)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1109\/T-C.1973.223729","article-title":"Boolean differential calculus and its application to switching theory","volume":"22","author":"THAYSE A.","year":"1973","unstructured":"THAYSE , A. AND DAVIO , M. 1973 . Boolean differential calculus and its application to switching theory . IEEE Trans. Comput. 22 ( April ), 409 - 420 . THAYSE,A.AND DAVIO, M. 1973. Boolean differential calculus and its application to switching theory. IEEE Trans. Comput. 22 (April), 409-420.","journal-title":"IEEE Trans. Comput."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/238997.239009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T09:28:32Z","timestamp":1672392512000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/238997.239009"}},"subtitle":["fast evaluation of Boolean expressions"],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["10.1145\/238997.239009"],"URL":"http:\/\/dx.doi.org\/10.1145\/238997.239009","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]},"assertion":[{"value":"1996-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}