{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:51Z","timestamp":1725663531643},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540510833"},{"type":"electronic","value":"9783540461524"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"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":[[1989]]},"DOI":"10.1007\/3-540-51083-4_64","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:40:54Z","timestamp":1330202454000},"page":"250-258","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the complexity of satisfiability problems for algebraic structures (preliminary report)"],"prefix":"10.1007","author":[{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"22_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1093\/imamat\/15.2.161","volume":"15","author":"R.C. Backhouse","year":"1975","unstructured":"R.C. Backhouse and B.A. Carre, \u201cRegular algebra applied to path finding problems,\u201d J. Inst. Maths. Applics., vol. 15, pp. 161\u2013186, 1975.","journal-title":"J. Inst. Maths. Applics."},{"key":"22_CR3","unstructured":"G. Birkhoff, Lattice Theory (3rd Edition), Am. Math. Soc., Providence, R.I., 1967."},{"key":"22_CR4","volume-title":"Regular Algebra and Finite Machines","author":"J.H. Conway","year":"1971","unstructured":"J.H. Conway, Regular Algebra and Finite Machines, Chapman and Hill, Ltd., London, 1971."},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"S.A. Cook, \u201cThe complexity of theorem-proving procedures,\u201d Proc. Third Annual ACM Symp. on Theory of Computing, pp. 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"22_CR6","volume-title":"Computability and Unsolvability","author":"M. Davis","year":"1982","unstructured":"M. Davis, Computability and Unsolvability, Dover Publications, Inc., New York, 1982."},{"key":"22_CR7","volume-title":"Automata, Languages, and Machines, vol. A","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg, Automata, Languages, and Machines, vol. A, Academic Press, New York, 1974."},{"key":"22_CR8","unstructured":"A.S. Fraenkel and Y. Yesha, \u201cComplexity of problems in games, graphs, and algebraic equations,\u201d unpublished manuscript, 1977."},{"key":"22_CR9","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":"22_CR10","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1137\/0216059","volume":"16","author":"H.B. Hunt III","year":"1987","unstructured":"H.B. Hunt III and R.E. Stearns, \u201cNonlinear algebra and optimization on rings are \u201chard\u201d,\u201d SICOMP, vol. 16, pp. 910\u2013929, 1987.","journal-title":"SICOMP"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"H.B. Hunt III and R.E. Stearns, \u201cThe complexities of satisfiability problems for algebraic structures,\u201d in preparation, 1988.","DOI":"10.1007\/3-540-51083-4_64"},{"key":"22_CR12","unstructured":"H.B. Hunt III and R.E. Stearns, \u201cOn the complexities of equivalence for communtative rings,\u201d Technical Report 87-22, SUNY Albany, 1987 (submutted for publication). Also see Abstracts of Communications at 5-th International Conference on: Applied Algebra, Error-Correcting Codes and Cryptography, Applied Algorithms and Combinatorics, Computer Algebra and Complexity Theory, pp. 43\u201344, Menorca, Spain."},{"key":"22_CR13","unstructured":"H.B. Hunt III, R.E. Stearns, and S.S. Ravi, \u201cSAT, Finite Algebra, and the structure of NP,\u201d in preparation, 1988."},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinational problems,\u201d in Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher, pp. 85\u2013103, Plenum Press, New York, 1972."},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.L. Lipton","year":"1980","unstructured":"R.L. Lipton and R.E. Tarjan, \u201cApplications of a planar separator theorem,\u201d SICOMP, vol. 9, pp. 615\u2013627, 1980.","journal-title":"SICOMP"},{"key":"22_CR16","volume-title":"Algebra","author":"S. MacLane","year":"1967","unstructured":"S. MacLane and G. Birkhoff, Algebra, MacMillan, New York, 1967."},{"key":"22_CR17","first-page":"354","volume":"77","author":"Y. Matisjasevic","year":"1970","unstructured":"Yu.V. Matisjasevic, \u201cEnumerable sets are diophantine,\u201d Soviet Math. Dokl., vol. 77, pp. 354\u2013357, 1970. (English translation).","journal-title":"Soviet Math. Dokl."},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(87)90206-7","volume":"25","author":"S.S. Ravi","year":"1987","unstructured":"S.S. Ravi and H.B. Hunt III, \u201cApplication of planar separator theorem to counting problems,\u201d IPL, vol. 25, pp. 317\u2013321, 1987.","journal-title":"IPL"},{"key":"22_CR19","series-title":"Technical Report","volume-title":"On the complexity of the satisfiability problem and the structure of NP","author":"R.E. Stearns","year":"1986","unstructured":"R.E. Stearns and H.B. Hunt III, \u201cOn the complexity of the satisfiability problem and the structure of NP,\u201d Technical Report 86-21, Department of Computer Science, SUNY at Albany, Albany, New York, 1986."},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/322261.322272","volume":"28","author":"R.E. Tarjan","year":"1980","unstructured":"R.E. Tarjan, \u201cA unified approach to path problems,\u201d J. ACM, vol. 28, pp. 577\u2013593, 1980.","journal-title":"J. ACM"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant, \u201cThe complexity of enumeration and reliability problems,\u201d SICOMP, vol. 8, pp. 410\u2013421, 1979.","journal-title":"SICOMP"},{"key":"22_CR22","volume-title":"Modern Algebra volumes 1 and 2","author":"B.L. Waerden van der","year":"1953","unstructured":"B.L. van der Waerden, Modern Algebra volumes 1 and 2, Frederick Ungar Publishing Co., New York, 1953."},{"key":"22_CR23","volume-title":"Linear and Combinatorial Optimization in Ordered Algebraic Structures","author":"U. Zimmermann","year":"1981","unstructured":"U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures, North Holland, Amsterdam, 1981."}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51083-4_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T18:11:07Z","timestamp":1580321467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51083-4_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540510833","9783540461524"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-51083-4_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}