{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:27:07Z","timestamp":1725496027839},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_21","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T03:39:22Z","timestamp":1196048362000},"page":"253-264","source":"Crossref","is-referenced-by-count":1,"title":["Satisfiability of Algebraic Circuits over Sets of Natural Numbers"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[]},{"given":"Christian","family":"Reitwie\u00dfner","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Travers","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Waldherr","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Annals of Mathematics\u00a0160, 781\u2013793 (2004)","journal-title":"Annals of Mathematics"},{"key":"21_CR2","first-page":"151","volume-title":"Proceedings 3rd Symposium on Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings 3rd Symposium on Theory of Computing, pp. 151\u2013158. ACM Press, New York (1971)"},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/1970289","volume":"74","author":"M. Davis","year":"1961","unstructured":"Davis, M., Putnam, H., Robinson, J.: The decision problem for exponential Diophantine equations. Annals of Mathematics\u00a074(2), 425\u2013436 (1961)","journal-title":"Annals of Mathematics"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/978-3-540-74510-5_15","volume-title":"CSR 2007","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Herr, K., Reitwie\u00dfner, C., Travers, S., Waldherr, M.: Equivalence problems for circuits over sets of natural numbers. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol.\u00a04649, pp. 127\u2013138. Springer, Heidelberg (2007)"},{"key":"21_CR5","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Mathematical sciences series. Freeman (1979)"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"21_CR7","unstructured":"Matiyasevich, Y.V.: Enumerable sets are diophantine. Doklady Akad. Nauk SSSR 191, 279\u2013282, 1970. Translation in Soviet Math. Doklady 11, 354\u2013357 (1970)"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/3-540-36494-3_50","volume-title":"STACS 2003","author":"P. McKenzie","year":"2003","unstructured":"McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 571\u2013582. Springer, Heidelberg (2003)"},{"key":"21_CR9","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1994)"},{"key":"21_CR10","first-page":"1","volume-title":"Proceedings 5th ACM Symposium on the Theory of Computing","author":"L.J. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings 5th ACM Symposium on the Theory of Computing, pp. 1\u20139. ACM Press, New York (1973)"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BFb0030338","volume-title":"Mathematical Foundations of Computer Science 1984","author":"K. Wagner","year":"1984","unstructured":"Wagner, K.: The complexity of problems concerning graphs with regularities. In: Chytil, M.P., Koubek, V. (eds.) Mathematical Foundations of Computer Science 1984. LNCS, vol.\u00a0176, pp. 544\u2013552. Springer, Heidelberg (1984)"},{"key":"21_CR12","unstructured":"Yang, K.: Integer circuit evaluation is PSPACE-complete. In: IEEE Conference on Computational Complexity, pp. 204\u2013213 (2000)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:55:52Z","timestamp":1619506552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}