{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:07:19Z","timestamp":1759939639527},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664925"},{"type":"electronic","value":"9783540482420"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48242-3_2","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T12:28:09Z","timestamp":1184588889000},"page":"13-32","source":"Crossref","is-referenced-by-count":10,"title":["On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System"],"prefix":"10.1007","author":[{"given":"Miki","family":"Hermann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Juban","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"A. Boudet, E. Contejean, and H. Devie. A new AC unification algorithm with a new algorithm for solving Diophantine equations. In Proceedings 5th LICS, Philadelphia (PA, USA), pages 289\u2013299, June 1990.","DOI":"10.1109\/LICS.1990.113755"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0747-7171(87)80027-5","volume":"3","author":"D. Benanav","year":"1987","unstructured":"D. Benanav, D. Kapur, and P. Narendran. Complexity of matching problems. Journal of Symbolic Computation, 3:203\u2013216, 1987.","journal-title":"Journal of Symbolic Computation"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"F. Baader and T. Nipkow. Term rewriting and all that. Cambridge University Press, 1998.","DOI":"10.1017\/CBO9781139172752"},{"issue":"2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF00881905","volume":"11","author":"A. Boudet","year":"1993","unstructured":"A. Boudet. Competing for the AC-unification race. Journal of Automated Reasoning, 11(2):185\u2013212, 1993.","journal-title":"Journal of Automated Reasoning"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1994.1067","volume":"113","author":"E. Contejean","year":"1994","unstructured":"E. Contejean and H. Devie. An efficient incremental algorithm for solving systems of linear Diophantine equations. Information and Computation, 113(1):143\u2013172, 1994.","journal-title":"Information and Computation"},{"issue":"1\u20132","key":"2_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0747-7171(89)80025-2","volume":"8","author":"M. Clausen","year":"1989","unstructured":"M. Clausen and A. Fortenbacher. Efficient solution of linear Diophantine equations. Journal of Symbolic Computation, 8(1\u20132):201\u2013216, 1989.","journal-title":"Journal of Symbolic Computation"},{"key":"2_CR7","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings 24th MFCS, Szklarska Poreba (Poland)","author":"A. Durand","year":"1999","unstructured":"A. Durand, M. Hermann, and L. Juban. On the complexity of recognizing the Hilbert basis of a linear Diophantine system. In L. Pacholski, editor, Proceedings 24th MFCS, Szklarska Poreba (Poland), LNCS, Springer-Verlag, September 1999."},{"key":"2_CR8","volume-title":"Outils pour la d\u00e9duction automatique dans les th\u00e9ories associative-commutatives","author":"E. Domenjoud","year":"1991","unstructured":"E. Domenjoud. Outils pour la d\u00e9duction automatique dans les th\u00e9ories associative-commutatives. PhD thesis, Universit\u00e9 Henri Poincar\u00e9, Nancy, France, September 1991."},{"key":"2_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/3-540-54345-7_57","volume-title":"Proceedings 16th MFCS, Kazimierz Dolny (Poland)","author":"E. Domenjoud","year":"1991","unstructured":"E. Domenjoud. Solving systems of linear Diophantine equations: An algebraic approach. In A. Tarlecki, editor, Proceedings 16th MFCS, Kazimierz Dolny (Poland), LNCS 520, pages 141\u2013150. Springer-Verlag, September 1991."},{"key":"2_CR10","unstructured":"A. Durand. Personal communication, June 1999."},{"issue":"3","key":"2_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0166-218X(85)90028-9","volume":"12","author":"A. A. Elimam","year":"1985","unstructured":"A. A. Elimam and S. E. Elmaghraby. On the reduction method for integer linear programs II. Discrete Applied Mathematics, 12(3):241\u2013260, 1985.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"2_CR12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0747-7171(87)80004-4","volume":"3","author":"F. Fages","year":"1987","unstructured":"F. Fages. Associative commutative unification. Journal of Symbolic Computation, 3(3):257\u2013275, 1987.","journal-title":"Journal of Symbolic Computation"},{"key":"2_CR13","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co, 1979."},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01442864","volume":"6","author":"P. Gordan","year":"1873","unstructured":"P. Gordan. Ueber die Aufl\u00f6sung linearen Gleichungen mit reellen Coefficienten. Mathematische Annalen, 6:23\u201328, 1873.","journal-title":"Mathematische Annalen"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF01208503","volume":"36","author":"D. Hilbert","year":"1890","unstructured":"D. Hilbert. Ueber die Theorie der algebraischen Formen. Mathematische Annalen, 36:473\u2013534, 1890.","journal-title":"Mathematische Annalen"},{"issue":"3","key":"2_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1006\/jsco.1995.1054","volume":"20","author":"M. Hermann","year":"1995","unstructured":"M. Hermann and P. G. Kolaitis. The complexity of counting problems in equational matching. Journal of Symbolic Computation, 20(3):343\u2013362, 1995.","journal-title":"Journal of Symbolic Computation"},{"key":"2_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/3-540-60246-1_142","volume-title":"Proceedings 20th MFCS, Prague (Czech Republic)","author":"M. Hermann","year":"1995","unstructured":"M. Hermann and P. G. Kolaitis. Computational complexity of simultaneous elementary matching problems. In J. Wiedermann and P. H\u00e1jek, editors, Proceedings 20th MFCS, Prague (Czech Republic), LNCS 969, pages 359\u2013370. Springer-Verlag, August 1995."},{"issue":"3","key":"2_CR18","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF00243791","volume":"3","author":"A. Herold","year":"1987","unstructured":"A. Herold and J. H. Siekmann. Unification in Abelian semigroups. Journal of Automated Reasoning, 3(3):247\u2013283, 1987.","journal-title":"Journal of Automated Reasoning"},{"issue":"3","key":"2_CR19","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/0020-0190(78)90078-9","volume":"7","author":"G. Huet","year":"1978","unstructured":"G. Huet. An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations. Information Processing Letters, 7(3):144\u2013147, 1978.","journal-title":"Information Processing Letters"},{"issue":"1","key":"2_CR20","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L. A. Hemaspaandra","year":"1995","unstructured":"L. A. Hemaspaandra and H. Vollmer. The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News, 26(1):2\u201313, March 1995.","journal-title":"SIGACT News"},{"key":"2_CR21","first-page":"257","volume-title":"Computational Logic. Essays in honor of Alan Robinson","author":"J.-P. Jouannaud","year":"1991","unstructured":"J.-P. Jouannaud and C. Kirchner. Solving equations in abstract algebras: A rule-based survey of unification. In J.-L. Lassez and G. Plotkin, editors, Computational Logic. Essays in honor of Alan Robinson, chapter 8, pages 257\u2013321. MIT Press, Cambridge (MA, USA), 1991."},{"key":"2_CR22","first-page":"67","volume-title":"Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity","author":"D. S. Johnson","year":"1990","unstructured":"D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, chapter 2, pages 67\u2013161. North-Holland, Amsterdam, 1990."},{"key":"2_CR23","unstructured":"L. Juban. Comptage de l\u2019ensemble des \u00e9l\u00e9ments de la base de Hilbert d\u2019un syst\u00e8me d\u2019\u00e9quations diophantiennes lin\u00e9aires. Technical Report 98-R-066, LORIA, 1998."},{"issue":"1","key":"2_CR24","first-page":"39","volume":"305","author":"J.-L. Lambert","year":"1987","unstructured":"J.-L. Lambert. Une borne pour les g\u00e9n\u00e9rateurs des solutions enti\u00e8res positives d\u2019une \u00e9quation diophantienne lin\u00e9aire. Compte-rendus de l\u2019Acad\u00e9mie des Sciences de Paris, 305(1):39\u201340, 1987.","journal-title":"Compte-rendus de l\u2019Acad\u00e9mie des Sciences de Paris"},{"issue":"1","key":"2_CR25","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF00245019","volume":"5","author":"D. Lankford","year":"1989","unstructured":"D. Lankford. Non-negative integer basis algorithms for linear equations with integer coefficients. Journal of Automated Reasoning, 5(1):25\u201335, 1989.","journal-title":"Journal of Automated Reasoning"},{"issue":"1\u20132","key":"2_CR26","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0747-7171(89)80026-4","volume":"8","author":"P. Lincoln","year":"1989","unstructured":"P. Lincoln and J. Christian. Adventures in associative-commutative unification. Journal of Symbolic Computation, 8(1\u20132):217\u2013240, 1989.","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"2_CR27","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"C. H. Papadimitriou","year":"1981","unstructured":"C. H. Papadimitriou. On the complexity of integer programming. Journal of the Association for Computing Machinery, 28(4):765\u2013768, 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR28","unstructured":"C. H. Papadimitriou. Computational complexity. Addison-Wesley, 1994."},{"key":"2_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-53904-2_94","volume-title":"Proceedings 4th RTA, Como (Italy)","author":"L. Pottier","year":"1991","unstructured":"L. Pottier. Minimal solutions of linear Diophantine systems: bounds and algorithms. In R.V. Book, editor, Proceedings 4th RTA, Como (Italy), LNCS 488, pages 162\u2013173. Springer-Verlag, April 1991."},{"key":"2_CR30","unstructured":"A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1986."},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"M. Stickel. A complete unification algorithm for associative-commutative functions. In Proceedings 4th IJCAI, Tbilisi (USSR), pages 71\u201382, 1975.","DOI":"10.21236\/ADA015846"},{"issue":"3","key":"2_CR32","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1145\/322261.322262","volume":"28","author":"M. Stickel","year":"1981","unstructured":"M. Stickel. A unification algorithm for associative-commutative functions. Journal of the Association for Computing Machinery, 28(3):423\u2013434, 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"S. Toda. On the computational power of PP and \u2295P. In Proceedings 30th FOCS, Research Triangle Park (NC, USA), pages 514\u2013519, 1989.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"2_CR34","volume-title":"Computational complexity of counting complexity classes","author":"S. Toda","year":"1991","unstructured":"S. Toda. Computational complexity of counting complexity classes. PhD thesis, Tokyo Institute of Technology, Department of Computer Science, Tokyo, Japan, 1991."},{"issue":"1","key":"2_CR35","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"S. Toda and O. Watanabe. Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science, 100(1):205\u2013221, 1992.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"2_CR36","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2_CR37","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"2_CR38","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1142\/S0129054191000066","volume":"2","author":"V. Zank\u00f3","year":"1991","unstructured":"V. Zank\u00f3. #P-completeness via many-one reductions. International Journal of Foundations of Computer Science, 2(1):77\u201382, 1991.","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming and Automated Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48242-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T20:50:27Z","timestamp":1550436627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48242-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664925","9783540482420"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-48242-3_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}