{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:50:07Z","timestamp":1787496607468,"version":"build-2736575974"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,4,17]],"date-time":"2017-04-17T00:00:00Z","timestamp":1492387200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["257039"],"award-info":[{"award-number":["257039"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["681988"],"award-info":[{"award-number":["681988"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["622397"],"award-info":[{"award-number":["622397"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00224-017-9762-0","type":"journal-article","created":{"date-parts":[[2017,4,16]],"date-time":"2017-04-16T23:40:56Z","timestamp":1492386056000},"page":"481-509","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Tropically Convex Constraint Satisfaction"],"prefix":"10.1007","volume":"62","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9037-5903","authenticated-orcid":false,"given":"Marcello","family":"Mamino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,17]]},"reference":[{"issue":"1","key":"9762_CR1","first-page":"125001","volume":"22","author":"M Akian","year":"2012","unstructured":"Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. Algebra Comput. 22(1), 125001 (2012). (43 pages)","journal-title":"Int. Algebra Comput."},{"key":"9762_CR2","doi-asserted-by":"crossref","unstructured":"Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, pages 112\u2013121 (2009)","DOI":"10.1007\/978-3-642-10631-6_13"},{"issue":"4","key":"9762_CR3","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1016\/j.ic.2011.01.003","volume":"209","author":"A Atserias","year":"2011","unstructured":"Atserias, A., Maneva, E.: Mean-payoff games and propositional proofs. Inf. Comput. 209(4), 664\u2013691 (2011). A preliminary version appeared in the Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science, Springer-Verlag, pages 102\u2013113, 2010","journal-title":"Inf. Comput."},{"issue":"07","key":"9762_CR4","first-page":"1","volume":"8\/1","author":"L Barto","year":"2012","unstructured":"Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods Comput. Sci. 8\/1(07), 1\u201326 (2012)","journal-title":"Logical Methods Comput. Sci."},{"key":"9762_CR5","doi-asserted-by":"crossref","unstructured":"Bezem, M., Nieuwenhuis, R., Rodr\u00edguez-Carbonell, E.: The max-atom problem and its relevance. In LPAR, pages 47\u201361 (2008)","DOI":"10.1007\/978-3-540-89439-1_4"},{"key":"9762_CR6","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Jonsson, P., von Oertzen, T.: Semilinear program feasibility. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pp 79\u201390. Springer Verlag (2009)","DOI":"10.1007\/978-3-642-02930-1_7"},{"key":"9762_CR7","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Jonsson, P., von Oertzen, T.: Essential convexity and complexity of semi-algebraic constraints. Logical Methods Comput. Sci. 8(4) (2012). An extended abstract about a subset of the results has been published under the titleSemilinear Program Feasibility at ICALP\u201910","DOI":"10.2168\/LMCS-8(4:5)2012"},{"key":"9762_CR8","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Martin, B., Antoine, M.: Constraint satisfaction problems over the integers with successor. In Proceedings of ICALP, arXiv: 1503.08572 (2015)","DOI":"10.1007\/978-3-662-47672-7_21"},{"key":"9762_CR9","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Kazuhisa M.: Every Stochastic Game with Perfect Information Admits a Canonical form. RRR-09-2009, RUTCOR, Rutgers University (2009)"},{"key":"9762_CR10","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"9762_CR11","unstructured":"Andradas, C., Rubio, R., V\u00e9lez, M.P.: An algorithm for convexity of semilinear sets over ordered fields. Real Algebraic and Analytic Geometry Preprint Server, No.12"},{"key":"9762_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4171\/dm\/154","volume":"9","author":"M Develin","year":"2004","unstructured":"Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1\u201327 (2004)","journal-title":"Doc. Math."},{"key":"9762_CR13","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP, and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9762_CR14","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1137\/0204006","volume":"4","author":"J Ferrante","year":"1975","unstructured":"Ferrante, J., Rackoff, C.: A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4(1), 69\u201376 (1975)","journal-title":"SIAM J. Comput."},{"key":"9762_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4054-9","volume-title":"Competitive Markov Decision Processes","author":"J Filar","year":"1996","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, New York (1996)"},{"key":"9762_CR16","volume-title":"A guide NP-completeness","author":"M Garey","year":"1978","unstructured":"Garey, M., Johnson, D.: A guide NP-completeness. CSLI Press, Stanford (1978)"},{"key":"9762_CR17","first-page":"179","volume":"3","author":"D Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero probabilities. Contrib. Theory Games 3, 179\u2013187 (1957)","journal-title":"Contrib. Theory Games"},{"key":"9762_CR18","unstructured":"Grigoriev, D., Podolskii, V.V.: Tropical effective primary and dual nullstellens\u00e4tze. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 379\u2013391 (2015)"},{"issue":"1","key":"9762_CR19","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-008-0240-y","volume":"122","author":"JW Helton","year":"2010","unstructured":"Helton, J.W., Nie, J.: Semidefinite representation of convex sets. Math Program 122(1), 21\u201364 (2010)","journal-title":"Math Program"},{"key":"9762_CR20","volume-title":"A shorter model theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"9762_CR21","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"PG Jeavons","year":"1995","unstructured":"Jeavons, P.G., Cooper, M.C.: Tractable constraints on ordered domains. Artif. Intell. 79(2), 327\u2013339 (1995)","journal-title":"Artif. Intell."},{"issue":"4","key":"9762_CR22","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"issue":"1","key":"9762_CR23","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0004-3702(98)00031-9","volume":"102","author":"P Jonsson","year":"1998","unstructured":"Jonsson, P., B\u00e4ckstr\u00f6m, C.: A unifying approach to temporal constraint reasoning. Artif. Intell. 102(1), 143\u2013155 (1998)","journal-title":"Artif. Intell."},{"key":"9762_CR24","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.artint.2012.10.001","volume":"195","author":"P Jonsson","year":"2013","unstructured":"Jonsson, P., L\u00f6\u00f6w, T.: Computation complexity of linear constraints over the integers. Artif. Intell. 195, 44\u201362 (2013)","journal-title":"Artif. Intell."},{"issue":"5","key":"9762_CR25","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1016\/j.jcss.2016.03.002","volume":"82","author":"P Jonsson","year":"2016","unstructured":"Jonsson, P., Thapper, J.: Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. J. Comput. Syst. Sci. 82(5), 912\u2013928 (2016)","journal-title":"J. Comput. Syst. Sci."},{"key":"9762_CR26","first-page":"1093","volume":"244","author":"L Khachiyan","year":"1979","unstructured":"Khachiyan, L.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244, 1093\u20131097 (1979)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"4","key":"9762_CR27","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1137\/1011093","volume":"11","author":"TM Liggett","year":"1969","unstructured":"Liggett, T.M., Lippman, S.A.: Stochastic games with perfect information and time average payoff. SIAM Rev. 11(4), 604\u2013607 (1969)","journal-title":"SIAM Rev."},{"issue":"2","key":"9762_CR28","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/S009753970037727X","volume":"33","author":"RH M\u00f6hring","year":"2004","unstructured":"M\u00f6hring, R.H., Skutella, M., Stork, F.: Scheduling with and\/or precedence constraints. SIAM J. Comput. 33(2), 393\u2013415 (2004)","journal-title":"SIAM J. Comput."},{"key":"9762_CR29","unstructured":"P\u00f6schel, R.: A general galois theory for operations and relations and concrete characterization of related algebraic structures. Tech Report of Akademie der Wissenschaften der DDR (1980)"},{"issue":"2\u20133","key":"9762_CR30","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00012-010-0056-5","volume":"62","author":"P Scowcroft","year":"2009","unstructured":"Scowcroft, P.: A representation of convex semilinear sets. Algebra Univers. 62(2\u20133), 289\u2013327 (2009)","journal-title":"Algebra Univers."},{"key":"9762_CR31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511525919","volume-title":"Tame topology and o-minimal structures, volume 248 of London Mathematical Society Lecture Note Series","author":"L Dries van den","year":"1998","unstructured":"van den Dries, L.: Tame topology and o-minimal structures, volume 248 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (1998)"},{"issue":"1&2","key":"9762_CR32","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1&2), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9762-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9762-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9762-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T00:18:15Z","timestamp":1692749895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9762-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,17]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9762"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9762-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,17]]}}}