{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:32Z","timestamp":1725664712131},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60249-6_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:58:31Z","timestamp":1330279111000},"page":"89-105","source":"Crossref","is-referenced-by-count":0,"title":["On polynomial ideals, their complexity, and applications"],"prefix":"10.1007","author":[{"given":"Ernst W.","family":"Mayr","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"5_CR1","first-page":"263","volume-title":"Constrained logic programming language CAL","author":"A. Aiba","year":"1988","unstructured":"Akira Aiba, K\u00f4 Sakai, Yosuke Sato, David J. Hawley, and Ryuzo Hasegawa. Constrained logic programming language CAL. In Proceedings of the International Conference on Fifth Generation Computer Systems 1988 (Tokyo, Japan, November\/December 1988), volume 1, pages 263\u2013276. Institute for New Generation Computer Technology, ICOT, 1988."},{"issue":"1","key":"5_CR2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1307\/mmj\/1029004064","volume":"37","author":"C. Berenstein","year":"1990","unstructured":"Carlos Berenstein and Alain Yger. Bounds for the degrees in the division problem. Michigan Math. J., 37(1):25\u201343, 1990.","journal-title":"Michigan Math. J."},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"577","DOI":"10.2307\/1971361","volume":"126","author":"W. D. Brownawell","year":"1987","unstructured":"W. Dale Brownawell. Bounds for the degrees in the Nullstellensatz. Ann. of Math., 126:577\u2013591, 1987.","journal-title":"Ann. of Math."},{"key":"5_CR4","unstructured":"Bruno Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.d. thesis, Department of Mathematics, University of Innsbruck, 1965."},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/978-94-009-5225-6_6","volume-title":"Multidimensional systems theory","author":"B. Buchberger","year":"1985","unstructured":"Bruno Buchberger. Gr\u00f6bner bases: An algorithmic method in polynomial ideal theory. In N.K. Bose, editor, Multidimensional systems theory, pages 184\u2013232. D. Reidel Publishing Company, Dordrecht-Boston-London, 1985."},{"key":"5_CR6","first-page":"131","volume-title":"volume 357 of LNCS","author":"L. Caniglia","year":"1988","unstructured":"L\u00e9andro Caniglia, Andr\u00e9 Galligo, and Joos Heintz. Some new effectivity bounds in computational geometry. In Proceedings of AAECC-6 (Roma, 1988), volume 357 of LNCS, pages 131\u2013152, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest, 1988. Springer-Verlag."},{"key":"5_CR7","first-page":"50","volume-title":"Exponential space complete problems for Petri nets and commutative semigroups","author":"E. Cardoza","year":"1976","unstructured":"E. Cardoza, R. Lipton, and A.R. Meyer. Exponential space complete problems for Petri nets and commutative semigroups. In Proceedings of the 8th Ann. ACM Symposium on Theory of Computing (Hershey, PA), pages 50\u201354, New York, 1976. ACM, ACM Press."},{"key":"5_CR8","unstructured":"Edward W. Cardoza. Computational complexity of the word problem for commutative semigroups. Technical Memorandum TM 67, Project MAC, M.I.T., October 1975."},{"key":"5_CR9","volume-title":"Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra","author":"C. David","year":"1992","unstructured":"David Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Springer-Verlag, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest, 1992."},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1137\/0219053","volume":"19","author":"T. W. Dub\u00e9","year":"1990","unstructured":"Thomas W. Dub\u00e9. The structure of polynomial ideals and Gr\u00f6bner bases. SIAM J. Comput., 19:750\u2013773, 1990.","journal-title":"SIAM J. Comput."},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0021-8693(69)90070-2","volume":"13","author":"S. Eilenberg","year":"1969","unstructured":"Samuel Eilenberg and M.P. Sch\u00fctzenberger. Rational sets in commutative monoids. J. Algebra, 13:173\u2013191, 1969.","journal-title":"J. Algebra"},{"volume-title":"Computational algebraic geometry and commutative algebra, volume XXXIV of Symposia Mathematica","year":"1993","key":"5_CR12","unstructured":"David Eisenbud and Lorenzo Robbiano, editors. Computational algebraic geometry and commutative algebra, volume XXXIV of Symposia Mathematica. Cambridge University Press, Cambridge, 1993."},{"key":"5_CR13","unstructured":"David Eisenbud and Bernd Sturmfels. Binomial ideals, June 1994."},{"key":"5_CR14","first-page":"114","volume-title":"Parallelism in random access machines","author":"S. Fortune","year":"1978","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In Proceedings of the 10th Ann. ACM Symposium on Theory of Computing (San Diego, CA), pages 114\u2013118, New York, 1978. ACM, ACM Press."},{"key":"5_CR15","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/BF01200407","volume":"3","author":"M. Giusti","year":"1993","unstructured":"Marc Giusti, Joos Heintz, and Juan Sabia. On the efficiency of effective Nullstellens\u00e4tze. Comput. Complexity, 3:56\u201395, 1993.","journal-title":"Comput. Complexity"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/BF01206635","volume":"95","author":"G. Hermann","year":"1926","unstructured":"Grete Hermann. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Math. Ann., 95:736\u2013788, 1926.","journal-title":"Math. Ann."},{"issue":"1","key":"5_CR17","doi-asserted-by":"crossref","first-page":"109","DOI":"10.2307\/1970486","volume":"79","author":"H. Hironaka","year":"1964","unstructured":"Heisuke Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero: I. Ann. of Math., 79(1):109\u2013203, 1964.","journal-title":"Ann. of Math."},{"issue":"2","key":"5_CR18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.2307\/1970547","volume":"79","author":"H. Hironaka","year":"1964","unstructured":"Heisuke Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero: II. Ann. of Math., 79(2):205\u2013326, 1964.","journal-title":"Ann. of Math."},{"key":"5_CR19","first-page":"405","volume-title":"The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems","author":"D.T. Huynh","year":"1985","unstructured":"D.T. Huynh. The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems. In Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI), pages 405\u2013412, New York, 1985. ACM, ACM Press."},{"issue":"1\u20133","key":"5_CR20","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/S0019-9958(86)80035-3","volume":"68","author":"D.T. Huynh","year":"1986","unstructured":"D.T. Huynh. A superexponential lower bound for Gr\u00f6bner bases and Church-Rosser commutative Thue systems. Inf. Control, 68(1\u20133):196\u2013206, 1986.","journal-title":"Inf. Control"},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"963","DOI":"10.2307\/1990996","volume":"1","author":"J. Koll\u00e1r","year":"1988","unstructured":"J. Koll\u00e1r. Sharp effective Nullstellensatz. J. Amer. Math. Soc., 1:963\u2013975, 1988.","journal-title":"J. Amer. Math. Soc."},{"key":"5_CR22","volume-title":"Technical Report TUM-I9518","author":"U. Koppenhagen","year":"1995","unstructured":"Ulla Koppenhagen and Ernst W. Mayr. The complexity of the boundedness, coverability, and selfcoverability problems for commutative semigroups. Technical Report TUM-I9518, Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, May 1995."},{"key":"5_CR23","unstructured":"Richard Lipton. The reachability problem requires exponential space. Research Report 62, Computer Science Dept., Yale University, January 1976."},{"key":"5_CR24","first-page":"238","volume-title":"An algorithm for the general Petri net reachability problem","author":"E. W. Mayr","year":"1981","unstructured":"Ernst W. Mayr. An algorithm for the general Petri net reachability problem. In Proceedings of the 13th Ann. ACM Symposium on Theory of Computing (Milwaukee, WI), pages 238\u2013246, New York, 1981. ACM, ACM Press."},{"issue":"3","key":"5_CR25","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. W. Mayr","year":"1984","unstructured":"Ernst W. Mayr. An algorithm for the general Petri net reachability problem. SIAM J. Comput., 13(3):441\u2013460, August 1984.","journal-title":"SIAM J. Comput."},{"key":"5_CR26","first-page":"400","volume-title":"volume LNCS 349","author":"E. W. Mayr","year":"1989","unstructured":"Ernst W. Mayr. Membership in polynomial ideals over Q is exponential space complete. In B. Monien and R. Cori, editors, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (Paderborn, FRG, February 1989), volume LNCS 349, pages 400\u2013406, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong, 1989. GI, afcet, Springer-Verlag."},{"issue":"4","key":"5_CR27","first-page":"1207","volume":"XII","author":"E. W. Mayr","year":"1992","unstructured":"Ernst W. Mayr. Polynomial Ideals and Applications. Mitteilungen der Mathematischen Gesellschaft in Hamburg, XII(4):1207\u20131215, 1992. Festschrift zum 300j\u00e4hrigen Bestehen der Gesellschaft.","journal-title":"Mitteilungen der Mathematischen Gesellschaft in Hamburg"},{"issue":"3","key":"5_CR28","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. W. Mayr","year":"1982","unstructured":"Ernst W. Mayr and Albert Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math., 46(3):305\u2013329, December 1982.","journal-title":"Adv. Math."},{"key":"5_CR29","volume-title":"Computation: Finite and infinite machines","author":"M. L. Minsky","year":"1967","unstructured":"Marvin L. Minsky. Computation: Finite and infinite machines. Prentice-Hall, Englewood Cliffs, 1967."},{"issue":"1","key":"5_CR30","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0304-3975(87)90019-3","volume":"54","author":"V. Pan","year":"1987","unstructured":"V. Pan. Complexity of parallel matrix computations. Theor. Comput. Sci., 54(1):65\u201385, September 1987.","journal-title":"Theor. Comput. Sci."},{"key":"5_CR31","volume-title":"Technical Report 2","author":"C.A. Petri","year":"1962","unstructured":"C.A. Petri. Kommunikation mit Automaten. Technical Report 2, Institut f\u00fcr Instrumentelle Mathematik, Bonn, 1962."},{"key":"5_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. Post","year":"1947","unstructured":"E. Post. Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 12:1\u201311, 1947.","journal-title":"J. Symbolic Logic"},{"key":"5_CR33","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1090\/S0002-9939-1974-0416874-9","volume":"44","author":"F. Richman","year":"1974","unstructured":"Fred Richman. Constructive aspects of Noetherian rings. In Proceedings of the American Math. Society, volume 44, pages 436\u2013441, June 1974.","journal-title":"Proceedings of the American Math. Society"},{"key":"5_CR34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1090\/S0002-9947-1974-0349648-2","volume":"197","author":"A. Seidenberg","year":"1974","unstructured":"A. Seidenberg. Constructions in algebra. Trans. Am. Math. Soc., 197:273\u2013313, 1974.","journal-title":"Trans. Am. Math. Soc."},{"key":"5_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0747-7171(08)80138-1","volume":"12","author":"C. K. Yap","year":"1991","unstructured":"Chee K. Yap. A new lower bound construction for commutative Thue systems, with applications. J. Symbolic Comput., 12:1\u201328, 1991.","journal-title":"J. Symbolic Comput."},{"key":"5_CR36","series-title":"The University Series in Higher Mathematics","volume-title":"Commutative algebra. Volume I","author":"O. Zariski","year":"1958","unstructured":"Oscar Zariski and Pierre Samuel. Commutative algebra. Volume I. Van Nostrand Reinhold Company, New York-Cincinnati-Toronto-London-Melbourne, 1958. The University Series in Higher Mathematics."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:16Z","timestamp":1619573656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}