乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T06:07:07Z","timestamp":1672553227959},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T00:00:00Z","timestamp":1505433600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["P 23499-N23"]},{"name":"Microsoft faculty fellows award, the Israeli Centers of Research Excellence (I-CORE) program","award":["4\/11"]},{"name":"FWF NFN","award":["S11407-N23 (RiSE\/SHiNE)"]},{"name":"ERC","award":["279307"]},{"name":"RICH Model Toolkit"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives\u2014such as reachability and \u03c9-regular objectives\u2014in this work, we study for the first time such games with the most well-studied quantitative objective, the mean-payoff objective. In pushdown games, two types of strategies are relevant: (1) global strategies, which depend on the entire global history; and (2) modular strategies, which have only local memory and thus do not depend on the context of invocation but rather only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity by showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games and memoryless modular strategies are sufficient in two-player pushdown games. Finally, we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.<\/jats:p>","DOI":"10.1145\/3121408","type":"journal-article","created":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T12:20:54Z","timestamp":1505478054000},"page":"1-49","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Mean-Payoff Pushdown Games"],"prefix":"10.1145","volume":"64","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}]},{"given":"Yaron","family":"Velner","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University, Israel, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2017,9,15]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"482","volume-title":"ATVA","author":"Almagor S.","unstructured":"S. Almagor , U. Boker , and O. Kupferman . 2011. What\u2019s decidable about weighted automata ? In ATVA , pages 482 -- 491 . S. Almagor, U. Boker, and O. Kupferman. 2011. What\u2019s decidable about weighted automata? In ATVA, pages 482--491."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2875421"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_2_1_5_1","first-page":"207","volume-title":"CAV","author":"Alur R.","unstructured":"R. Alur , K. Etessami , and M. Yannakakis . 2001. Analysis of recursive state machines . In CAV , pages 207 -- 220 . R. Alur, K. Etessami, and M. Yannakakis. 2001. Analysis of recursive state machines. In CAV, pages 207--220."},{"key":"e_1_2_1_6_1","first-page":"67","volume-title":"CAV","author":"Alur R.","unstructured":"R. Alur , S. La Torre , and P. Madhusudan . 2003. Modular strategies for infinite games on recursive graphs . In CAV , pages 67 -- 79 . R. Alur, S. La Torre, and P. Madhusudan. 2003. Modular strategies for infinite games on recursive graphs. In CAV, pages 67--79."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-013-0191-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.33"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.09.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.02.002"},{"issue":"3","key":"e_1_2_1_13_1","first-page":"91","article-title":"Regular canonical systems","volume":"6","author":"B\u00fcchi J. R.","year":"1964","unstructured":"J. R. B\u00fcchi . 1964 . Regular canonical systems . Archive for Mathematical Logic 6 ( 3 ), pp. 91 -- 111 . J. R. B\u00fcchi. 1964. Regular canonical systems. Archive for Mathematical Logic 6(3), pp. 91--111.","journal-title":"Archive for Mathematical Logic"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0280205-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676968"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699430"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/586110.586142"},{"key":"e_1_2_1_19_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms. The MIT Press Cambridge MA. T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms. The MIT Press Cambridge MA."},{"key":"e_1_2_1_20_1","first-page":"148","volume-title":"LNCS","volume":"2211","author":"de Alfaro L.","unstructured":"L. de Alfaro and T. A. Henzinger . 2001. Interface theories for component-based design. In EMSOFT , LNCS , Vol. 2211 , pages 148 -- 165 . Springer. L. de Alfaro and T. A. Henzinger. 2001. Interface theories for component-based design. In EMSOFT, LNCS, Vol. 2211, pages 148--165. Springer."},{"key":"e_1_2_1_21_1","first-page":"537","volume-title":"MFCS","author":"Droste M.","unstructured":"M. Droste and I. Meinecke . 2010. Describing average- and longtime-behavior by weighted MSO logics . In MFCS , pages 537 -- 548 . M. Droste and I. Meinecke. 2010. Describing average- and longtime-behavior by weighted MSO logics. In MFCS, pages 537--548."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21949"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699431"},{"key":"e_1_2_1_27_1","volume-title":"LNCS","volume":"2500","author":"Gr\u00e4del E.","unstructured":"E. Gr\u00e4del , W. Thomas , and T. Wilke , editors. 2002. Automata, Logics, and Infinite Games: A Guide to Current Research , LNCS , Vol. 2500 . Springer. E. Gr\u00e4del, W. Thomas, and T. Wilke, editors. 2002. Automata, Logics, and Infinite Games: A Guide to Current Research, LNCS, Vol. 2500. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802177"},{"key":"e_1_2_1_29_1","first-page":"526","volume-title":"CAV\u201902","author":"Henzinger T. A.","unstructured":"T. A. Henzinger , R. Jhala , R. Majumdar , G. C. Necula , G. Sutre , and W. Weimer . 2002. Temporal-safety proofs for systems code . In CAV\u201902 , pages 526 -- 538 . T. A. Henzinger, R. Jhala, R. Majumdar, G. C. Necula, G. Sutre, and W. Weimer. 2002. Temporal-safety proofs for systems code. In CAV\u201902, pages 526--538."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3085"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/646246.684713"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1011093"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0325013"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_39_1","first-page":"389","volume-title":"Handbook of Formal Languages","author":"Thomas W.","unstructured":"W. Thomas . 1997. Languages , automata, and logic . In Handbook of Formal Languages , Vol. 3 , Beyond Words, Chapter 7, pages 389 -- 455 . Springer , New York, NY. W. Thomas. 1997. Languages, automata, and logic. In Handbook of Formal Languages, Vol. 3, Beyond Words, Chapter 7, pages 389--455. Springer, New York, NY."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646838.708632"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2894"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00009-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3121408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T06:47:00Z","timestamp":1672469220000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3121408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,15]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3121408"],"URL":"https:\/\/doi.org\/10.1145\/3121408","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,15]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}