{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T02:38:38Z","timestamp":1789699118824,"version":"4.0.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319341705","type":"print"},{"value":"9783319341712","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-34171-2_7","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T06:34:18Z","timestamp":1464590058000},"page":"88-101","source":"Crossref","is-referenced-by-count":1,"title":["Max-Closed Semilinear Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcello","family":"Mamino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"issue":"1","key":"7_CR1","first-page":"43","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), 43 (2012). 125001","journal-title":"Int. Algebra Comput."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Atserias, A., Maneva, E.: Mean-payoff games and propositional proofs. Inf. Comput. 209(4), 664\u2013691 (2011). In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol. 6198, pp. 102\u2013113. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14165-2_10"},{"issue":"1:07","key":"7_CR3","first-page":"1","volume":"8","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":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-540-89439-1_4","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M Bezem","year":"2008","unstructured":"Bezem, M., Nieuwenhuis, R., Rodr\u00edguez-Carbonell, E.: The max-atom problem and its relevance. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS, vol. 5330, pp. 47\u201361. Springer, Heidelberg (2008)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-642-02930-1_7","volume-title":"Automata, Languages and Programming","author":"M Bodirsky","year":"2009","unstructured":"Bodirsky, M., Jonsson, P., von Oertzen, T.: Semilinear program feasibility. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 79\u201390. Springer, Heidelberg (2009)"},{"issue":"4","key":"7_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-8(4:5)2012","volume":"8","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., Jonsson, P., von Oertzen, T.: Essential convexity and complexity of semi-algebraic constraints. Logical Methods Comput. Sci. 8(4), 1\u201325 (2012). An extended abstract about a subset of the results has been published under the title Semilinear Program Feasibility at ICALP 2010","journal-title":"Logical Methods Comput. Sci."},{"key":"7_CR7","unstructured":"Bodirsky, M., Mamino, M.: Max-closed semilinear constraint satisfaction (2015). arXiv:1506.04184"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-662-47672-7_21","volume-title":"Automata, Languages, and Programming","author":"M Bodirsky","year":"2015","unstructured":"Bodirsky, M., Martin, B., Mottet, A.: Constraint satisfaction problems over the integers with successor. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part I. LNCS, vol. 9134, pp. 256\u2013267. Springer, Heidelberg (2015)"},{"key":"7_CR9","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: Every stochastic game with perfect information admits a canonical form. RRR-09-2009, RUTCOR, Rutgers University (2009)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-642-13036-6_26","volume-title":"Integer Programming and Combinatorial Optimization","author":"E Boros","year":"2010","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 341\u2013354. Springer, Heidelberg (2010)"},{"key":"7_CR11","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":"7_CR12","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":"7_CR13","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":"7_CR14","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":"7_CR15","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":"7_CR16","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":"7_CR17","first-page":"179","volume":"3","author":"D Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero probabilities. Contrib. Theor. Games 3, 179\u2013187 (1957)","journal-title":"Contrib. Theor. Games"},{"key":"7_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, Garching, Germany, 4\u20137 March 2015, pp. 379\u2013391 (2015)"},{"key":"7_CR19","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":"7_CR20","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":"7_CR21","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":"7_CR22","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":"7_CR23","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."},{"key":"7_CR24","unstructured":"Jonsson, P., Thapper, J.: Constraint satisfaction and semilinear expansions of addition over the rationals and the reals (2015). arXiv:1506.00479"},{"key":"7_CR25","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":"7_CR26","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":"7_CR27","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":"7_CR28","unstructured":"P\u00f6schel, R.: A general galois theory for operations and relations and concrete characterization of related algebraic structures. Technical report of Akademie der Wissenschaften der DDR (1980)"},{"issue":"2\u20133","key":"7_CR29","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."},{"issue":"1&2","key":"7_CR30","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":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T17:33:57Z","timestamp":1692380037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}