{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T09:49:25Z","timestamp":1790675365248,"version":"4.1.0"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2014,6,26]],"date-time":"2014-06-26T00:00:00Z","timestamp":1403740800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["259454"],"award-info":[{"award-number":["259454"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["239850"],"award-info":[{"award-number":["239850"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We consider two-player games played on finite graphs equipped with costs on\nedges and introduce two winning conditions, cost-parity and cost-Streett, which\nrequire bounds on the cost between requests and their responses. Both\nconditions generalize the corresponding classical omega-regular conditions and\nthe corresponding finitary conditions. For parity games with costs we show that\nthe first player has positional winning strategies and that determining the\nwinner lies in NP and coNP. For Streett games with costs we show that the first\nplayer has finite-state winning strategies and that determining the winner is\nEXPTIME-complete. The second player might need infinite memory in both games.\nBoth types of games with costs can be solved by solving linearly many instances\nof their classical variants.<\/jats:p>","DOI":"10.2168\/lmcs-10(2:14)2014","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T09:40:42Z","timestamp":1415958042000},"source":"Crossref","is-referenced-by-count":17,"title":["Parity and Streett Games with Costs"],"prefix":"10.46298","volume":"Volume 10, Issue 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6576-4680","authenticated-orcid":false,"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8038-2453","authenticated-orcid":false,"given":"Martin","family":"Zimmermann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2014,6,26]]},"reference":[{"key":"896:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/794\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/794\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:56:16Z","timestamp":1681242976000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,26]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-10(2:14)2014","relation":{"is-same-as":[{"id-type":"arxiv","id":"1207.0663","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1207.0663","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1709.04854","asserted-by":"subject"},{"id-type":"doi","id":"10.1007\/s00236-019-00345-7","asserted-by":"subject"},{"id-type":"doi","id":"10.4230\/lipics.csl.2018.34","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1709.04854","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,26]]},"article-number":"794"}}