{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:10:56Z","timestamp":1648685456190},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We study a class of functions for which, instead of evaluating the extensions on a given set of transients, it is possible to get the same values by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.<\/jats:p>","DOI":"10.1142\/s0129054112400023","type":"journal-article","created":{"date-parts":[[2012,2,20]],"date-time":"2012-02-20T10:57:11Z","timestamp":1329735431000},"page":"21-35","source":"Crossref","is-referenced-by-count":0,"title":["ON THE COMPLEXITY OF THE EVALUATION OF TRANSIENT EXTENSIONS OF BOOLEAN FUNCTIONS"],"prefix":"10.1142","volume":"23","author":[{"given":"JANUSZ","family":"BRZOZOWSKI","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BAIYU","family":"LI","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YULI","family":"YE","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, ON, M5S 3G4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026218512171"},{"key":"rf3","first-page":"155","volume":"16","author":"Brzozowski J.","journal-title":"J. of Mult.-Valued Logic & Soft Computing"},{"key":"rf4","volume-title":"Switching Circuits and Logical Design","author":"Caldwell S. H.","year":"1958"},{"key":"rf5","volume-title":"Introduction to Switching and Automata Theory","author":"Harrison M. A.","year":"1965"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"#R72","DOI":"10.37236\/161","volume":"16","author":"Richmond L. B.","journal-title":"Electronic J. Combinatorics"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112400023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T18:41:23Z","timestamp":1593715283000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112400023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":6,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1142\/S0129054112400023"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112400023","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}