{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:53:37Z","timestamp":1759146817296},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_57","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T18:41:48Z","timestamp":1277232108000},"page":"632-641","source":"Crossref","is-referenced-by-count":8,"title":["On the Complexity of Some Equivalence Problems for Propositional Calculi"],"prefix":"10.1007","author":[{"given":"Steffen","family":"Reith","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"57_CR1","first-page":"422","volume-title":"37th Symposium on Foundation of Computer Science","author":"M. Agrawal","year":"1996","unstructured":"Agrawal, M., Thierauf, T.: The Boolean isomorphism problem. In: 37th Symposium on Foundation of Computer Science, pp. 422\u2013430. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"57_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. Computer Science Logic","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence problems for boolean constraint satisfaction. In: Proc. Computer Science Logic. LNCS, Springer, Heidelberg (2002)"},{"key":"57_CR3","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s002240000109","volume":"31","author":"B. Borchert","year":"1998","unstructured":"Borchert, B., Ranjan, D., Stefan, F.: On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions. Theory of Computing Systems\u00a031, 679\u2013693 (1998)","journal-title":"Theory of Computing Systems"},{"key":"57_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L.M. Goldschlager","year":"1986","unstructured":"Goldschlager, L.M., Parberry, I.: On The Construction Of Parallel Computers From Various Bases Of Boolean Functions. Theoretical Computer Science\u00a043, 43\u201358 (1986)","journal-title":"Theoretical Computer Science"},{"key":"57_CR5","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0020-0190(00)00091-0","volume":"75","author":"U. Hertrampf","year":"2000","unstructured":"Hertrampf, U., Reith, S., Vollmer, H.: A note on closure properties of logspace MOD classes. Information Processing Letters\u00a075, 91\u201393 (2000)","journal-title":"Information Processing Letters"},{"issue":"5","key":"57_CR6","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM Journal on Computing\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"57_CR7","doi-asserted-by":"crossref","unstructured":"Jablonski, S.W., Gawrilow, G.P., Kudrajawzew, W.B.: Boolesche Funktionen und Postsche Klassen. Akademie-Verlag (1970)","DOI":"10.1515\/9783112649282"},{"key":"57_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H.R. Lewis","year":"1979","unstructured":"Lewis, H.R.: Satisfiability Problems for Propositional Calculi. Mathematical Systems Theory\u00a013, 45\u201353 (1979)","journal-title":"Mathematical Systems Theory"},{"key":"57_CR9","first-page":"1","volume":"5","author":"E.L. Post","year":"1941","unstructured":"Post, E.L.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"key":"57_CR10","unstructured":"Reith, S.: Generalized Satisfiability Problems. PhD thesis, University of W\u00fcrzburg (2001)"},{"key":"#cr-split#-57_CR11.1","unstructured":"Reith, S., Wagner, K.W.: The Complexity of Problems Defined by Boolean Circuits. Technical Report 255, Institut f??r Informatik, Universit??t W??rzburg (2000);"},{"key":"#cr-split#-57_CR11.2","unstructured":"To appear in Proceedings International Conference Mathematical Foundation of Informatics, Hanoi, October 25???28 (1999)"},{"key":"57_CR12","first-page":"216","volume-title":"Proccedings 10th Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proccedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"57_CR13","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi, R.: The method of forcing for nondeterministic automata. Bulletin of the European Association for Theoretical Computer Science\u00a033, 96\u2013100 (1987)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T14:21:17Z","timestamp":1685629277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}