{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T09:39:48Z","timestamp":1649151588201},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540160786","type":"print"},{"value":"9783540397588","type":"electronic"}],"license":[{"start":{"date-parts":[[1985,1,1]],"date-time":"1985-01-01T00:00:00Z","timestamp":473385600000},"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":[[1985]]},"DOI":"10.1007\/3-540-16078-7_83","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:37:03Z","timestamp":1330195023000},"page":"277-290","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Monotone boolean formulas, distributive lattices, and the complexities of logics, algebraic structures, and computation structures (preliminary report)"],"prefix":"10.1007","author":[{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"first","affiliation":[]},{"given":"R. E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"23_CR1","volume-title":"Sets, Lattices, and Boolean Algebras","author":"J.C. Abbott","year":"1969","unstructured":"J.C. Abbott, Sets, Lattices, and Boolean Algebras, Allyn and Bacon, Boston, Mass., 1969."},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TC.1978.1675141","volume":"C-27","author":"S.B. Akers","year":"1978","unstructured":"S.B. Akers, Binary decision diagrams, IEEE Trans. on Computers, vol. C-27, 1978, pp. 509\u2013516.","journal-title":"IEEE Trans. on Computers"},{"key":"23_CR3","unstructured":"S.B. Akers, A procedure for functional design verification, Digest of 10-th International Symp. on Fault Tolerant Computing, 1980, pp. 65\u201367."},{"key":"23_CR4","series-title":"Technical Report","volume-title":"Computational probability with application to fault detection","author":"D.N. Arden","year":"1984","unstructured":"D.N. Arden, S. Chakravarty, H.B. Hunt III, and R.M. Murray, Computational probability with application to fault detection, Technical Report 84-17, Department of Computer Science, SUNY Albany, Albany, New York, 1984."},{"key":"23_CR5","volume-title":"Lattice Theory","author":"G. Birkhoff","year":"1967","unstructured":"G. Birkhoff, Lattice Theory, (3rd Edition), Am. Math. Soc., Providence, R.I., 1967.","edition":"3rd Edition"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","volume":"10","author":"M. Blum","year":"1980","unstructured":"M. Blum, A.K. Chandra, and M.N. Wegman, Equivalence of free Boolean graphs can be decided probabilistically in polynomial time, Information Processing Letters 10, 1980, pp. 80\u201382.","journal-title":"Information Processing Letters"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1145\/1634.1639","volume":"31","author":"P.A. Bloniarz","year":"1984","unstructured":"P.A. Bloniarz, H.B. Hunt III, and D.J. Rosenkrantz, Algebraic structures with hard equivalence and minimization problems, J. ACM, 31, 1984, pp. 879\u2013904.","journal-title":"J. ACM"},{"key":"23_CR8","unstructured":"S.K. Chakravarti and H.B. Hunt III, Binary decision diagrams, unpublished manuscript."},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"R.L. Constable, H.B. Hunt III, and S. Sahni, On the computational complexity of scheme equivalence, Proc. 8-th Annual Princeton Conference of Information Sciences and Systems, Princeton, N.J., 1974. Also appears as \u2014 H.B.Hunt III, R.L. Constable, and S. Sahni, On the computational complexity of program scheme equivalence, SICOMP 9, 1980, pp. 349\u2013416.","DOI":"10.1137\/0209031"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, Proc. Third Annual ACM Symp. on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"23_CR11","volume-title":"An Introduction to Probability Theory and its Applications Vol. 1","author":"W. Feller","year":"1968","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications Vol. 1 (3rd Edition), John Wiley and Sons, New York, 1968.","edition":"3rd Edition"},{"key":"23_CR12","series-title":"Technical Report TR","volume-title":"The complexity of equivalence and containment for free single variable program schemes","author":"S. Fortune","year":"1977","unstructured":"S. Fortune, J. Hopcroft, and E.M. Schmidt, The complexity of equivalence and containment for free single variable program schemes, Technical Report TR 77-310, Department of Computer Science, Cornell University, Ithaca, New York, 1977."},{"key":"23_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, Ca., 1979."},{"key":"23_CR14","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"E.M. Gold, Complexity of automaton identification from given data, Inf. and Control 37, 1978, pp. 302\u2013320.","journal-title":"Inf. and Control"},{"key":"23_CR15","volume-title":"Intuitionism","author":"A. Heyting","year":"1959","unstructured":"A. Heyting, Intuitionism, North-Holland, Amsterdam, 1959."},{"key":"23_CR16","volume-title":"Grundlagen der Mathematik, vol. 1","author":"D. Hibert","year":"1934","unstructured":"D. Hibert and P. Bernays, Grundlagen der Mathematik, vol. 1, Springer, Berlin, 1934."},{"key":"23_CR17","unstructured":"H.B. Hunt III and R.E. Stearns, Distributive lattices, and the complexity of logics and probability, submitted for publication."},{"key":"23_CR18","unstructured":"H.B. Hunt III and R.E. Stearns, Nonlinear algebra for rings is \u201chard\u201d, submitted for publication."},{"key":"23_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O.H. Ibarra","year":"1983","unstructured":"O.H. Ibarra and S. Moran, Probabilistic algorithms for deciding equivalence of straight-line programs, JACM 30, 1983, pp. 217\u2013228.","journal-title":"JACM"},{"key":"23_CR20","volume-title":"Introduction to Metamathematics","author":"S.C. Kleene","year":"1950","unstructured":"S.C. Kleene, Introduction to Metamathematics, D. VanNostrand Co., Inc., Princeton, N.J., 1950."},{"key":"23_CR21","unstructured":"C.I. Lewis and C.H. Langford, Symbolic Logic, New York, 1932."},{"key":"23_CR22","volume-title":"Algebra","author":"S. MacLane","year":"1967","unstructured":"S. MacLane and G. Birkhoff, Algebra, MacMillan, New York, 1967."},{"key":"23_CR23","volume-title":"Mathematical Theory of Computation","author":"Z. Manna","year":"1974","unstructured":"Z. Manna, Mathematical Theory of Computation, McGraw-Hill, New York, 1974."},{"key":"23_CR24","volume-title":"Introduction to Mathematical Logic","author":"E. Mendelson","year":"1979","unstructured":"E. Mendelson, Introduction to Mathematical Logic (2nd edition), D. VanNostrand, New York, 1979.","edition":"2nd edition"},{"key":"23_CR25","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1145\/356893.356898","volume":"14","author":"B.M.E. Moret","year":"1982","unstructured":"B.M.E. Moret, Decision trees and diagrams, Computing Surveys 14, 1982, pp. 593\u2013623.","journal-title":"Computing Surveys"},{"key":"23_CR26","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/T-C.1975.224279","volume":"24","author":"K.P. Parker","year":"1975","unstructured":"K.P. Parker and E.J. McCluskey, Probabilistic treatment of general combinational networks, IEEE Trans. on Computers, 24, 1975, pp. 668\u2013670.","journal-title":"IEEE Trans. on Computers"},{"key":"23_CR27","first-page":"165","volume":"43","author":"E.L. Post","year":"1921","unstructured":"E.L. Post, Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 1921, pp. 165\u2013185.","journal-title":"Amer. J. Math."},{"key":"23_CR28","volume-title":"An Algebraic Approach to Non-Classical Logics","author":"H. Rasiowa","year":"1974","unstructured":"H. Rasiowa, An Algebraic Approach to Non-Classical Logics, North-Holland, Amsterdam, 1974."},{"key":"23_CR29","volume-title":"The Mathematics of Meta-mathematics","author":"H. Rasiowa","year":"1963","unstructured":"H. Rasiowa and R. Sikorski, The Mathematics of Meta-mathematics, Panstwowe Wydawnictwo Naukowe, Warzawa, 1963."},{"key":"23_CR30","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"C.A. Tovey, A simplified NP-complete satisfiability problem, Discrete Applied Mathematics 8, 1984, pp. 85\u201389.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR31","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8, 1979, pp. 410\u2013421.","journal-title":"SIAM J. Comput."}],"container-title":["STACS 86","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16078-7_83","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T14:12:35Z","timestamp":1580307155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16078-7_83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985]]},"ISBN":["9783540160786","9783540397588"],"references-count":31,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-16078-7_83","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1985]]},"assertion":[{"value":"5 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}