{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:18:45Z","timestamp":1774369125665,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1987,12,1]],"date-time":"1987-12-01T00:00:00Z","timestamp":565315200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch math Logik"],"published-print":{"date-parts":[[1987,12]]},"DOI":"10.1007\/bf02017492","type":"journal-article","created":{"date-parts":[[2005,8,12]],"date-time":"2005-08-12T07:11:20Z","timestamp":1123830680000},"page":"77-99","source":"Crossref","is-referenced-by-count":3,"title":["Parallelizable algebras"],"prefix":"10.1007","volume":"26","author":[{"given":"Matthias","family":"Ragaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02017492_CR1","unstructured":"Borodin, A., Munro, I.: The computational complexity of algebraic and numeric problems. New York 1975."},{"key":"BF02017492_CR2","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/T-C.1973.223757","volume":"C-22","author":"E. Brent","year":"1973","unstructured":"Brent, E., Kuck, D., Maruyama, K.: The parallel evaluation of arithmetic expressions without division. IEEE Transactions on Computers C-22 (1973) 532\u2013534.","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"BF02017492_CR3","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0211033","volume":"11","author":"M.J. Fischer","year":"1982","unstructured":"Fischer, M.J., Meyer, A.R., Paterson, M.S.: \u03a9(nlogn) lower bounds on length of Boolean formulas. SIAM J. Comput.11, 3 (1982) 416\u2013427.","journal-title":"SIAM J. Comput."},{"key":"BF02017492_CR4","doi-asserted-by":"crossref","unstructured":"Hodes, L.E., Specker, E.: Length of formulas and elimination of quantifiers I. Contributions to Mathematical Logic. Amsterdam 1968.","DOI":"10.1016\/S0049-237X(08)70524-X"},{"key":"BF02017492_CR5","unstructured":"Krapchenko, V.M.: Complexity of the realization of a linear function in the class of II-circuits. Math. Notes Acad. Sci. USSR (1971) 21\u201323."},{"key":"BF02017492_CR6","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1090\/S0002-9947-1951-0044470-3","volume":"71","author":"R. Lyndon","year":"1951","unstructured":"Lyndon, R.: Identities in two-valued calculi. Trans. Am. Math. Soc.71 (1951) 457\u2013465.","journal-title":"Trans. Am. Math. Soc."},{"key":"BF02017492_CR7","first-page":"1020","volume":"6","author":"V.L. Murskii","year":"1965","unstructured":"Murskii, V.L.: The existence in three-valued logic of a closed class with finite basis, not having a finite complete system of identities. Sov. Math. Dokl.6 (1965) 1020\u20131024.","journal-title":"Sov. Math. Dokl."},{"key":"BF02017492_CR8","first-page":"999","volume":"7","author":"E.I. Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk, E.I.: A Boolean function. Sov. Math. Dokl.7 (1966) 999\u20131000.","journal-title":"Sov. Math. Dokl."},{"key":"BF02017492_CR9","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0021-8693(69)90058-1","volume":"11","author":"P. Perkins","year":"1969","unstructured":"Perkins, P.: Bases for equational theories of semigroups. J. Algebra11 (1969) 293\u2013314.","journal-title":"J. Algebra"},{"key":"BF02017492_CR10","doi-asserted-by":"crossref","unstructured":"Post, E.L.: The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies5, Princeton 1941; reprint New York 1965.","DOI":"10.1515\/9781400882366"},{"key":"BF02017492_CR11","first-page":"119","volume":"16","author":"V.R. Pratt","year":"1975","unstructured":"Pratt, V.R.: The effect of basis on size of Boolean expressions. Proc. Annual IEEE Symposium on Foundations of Computer Science16 (1975) 119\u2013121.","journal-title":"Proc. Annual IEEE Symposium on Foundations of Computer Science"},{"key":"BF02017492_CR12","doi-asserted-by":"crossref","unstructured":"Pudlak, P.: Bounds for Hodes-Specker theorem. In: Logic and machines: Decision problems and complexity. Proceedings. Lecture Notes in Computer Science 171. Berlin 1984.","DOI":"10.1007\/3-540-13331-3_57"},{"key":"BF02017492_CR13","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF00401653","volume":"XL","author":"W. Rautenberg","year":"1981","unstructured":"Rautenberg, W.: 2-element matrices. Studia LogicaXL (1981) 315\u2013353.","journal-title":"Studia Logica"},{"key":"BF02017492_CR14","unstructured":"Savage, J.E.: The complexity of Computing. New York 1976."},{"key":"BF02017492_CR15","unstructured":"Spira, P.M.: On time-hardware complexity tradeoffs for Boolean functions. Proc. Fourth Hawaii International Symposium on System Sciences (1971) 525\u2013527."},{"key":"BF02017492_CR16","first-page":"110","volume":"2","author":"B.A. Subbotovskaya","year":"1961","unstructured":"Subbotovskaya, B.A.: Realizations of linear functions by formulas using &, \u2228,\u2212. Sov. Math. Dokl.2 (1961) 110\u2013112.","journal-title":"Sov. Math. Dokl."},{"key":"BF02017492_CR17","first-page":"478","volume":"4","author":"B.A. Subbotovskaya","year":"1963","unstructured":"Subbotovskaya, B.A.: Comparison of bases in the realization by formulas of functions of the algebra of logic. Sov. Math. Dokl.4 (1963) 478\u2013481.","journal-title":"Sov. Math. Dokl."}],"container-title":["Archiv f\u00fcr Mathematische Logik und Grundlagenforschung"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02017492.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02017492\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02017492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T22:35:39Z","timestamp":1586385339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02017492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,12]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,12]]}},"alternative-id":["BF02017492"],"URL":"https:\/\/doi.org\/10.1007\/bf02017492","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,12]]}}}