{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:08Z","timestamp":1753894388498,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T00:00:00Z","timestamp":1659052800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["1704883"],"award-info":[{"award-number":["1704883"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The notion of comparison between system runs is fundamental in formal\nverification. This concept is implicitly present in the verification of\nqualitative systems, and is more pronounced in the verification of quantitative\nsystems. In this work, we identify a novel mode of comparison in quantitative\nsystems: the online comparison of the aggregate values of two sequences of\nquantitative weights. This notion is embodied by comparator automata\n(comparators, in short), a new class of automata that read two infinite\nsequences of weights synchronously and relate their aggregate values.\n  We show that aggregate functions that can be represented with B\\\"uchi\nautomaton result in comparators that are finite-state and accept by the B\\\"uchi\ncondition as well. Such $\\omega$-regular comparators further lead to generic\nalgorithms for a number of well-studied problems, including the quantitative\ninclusion and winning strategies in quantitative graph games with incomplete\ninformation, as well as related non-decision problems, such as obtaining a\nfinite representation of all counterexamples in the quantitative inclusion\nproblem.\n  We study comparators for two aggregate functions: discounted-sum and\nlimit-average. We prove that the discounted-sum comparator is $\\omega$-regular\niff the discount-factor is an integer. Not every aggregate function, however,\nhas an $\\omega$-regular comparator. Specifically, we show that the language of\nsequence-pairs for which limit-average aggregates exist is neither\n$\\omega$-regular nor $\\omega$-context-free. Given this result, we introduce the\nnotion of prefix-average as a relaxation of limit-average aggregation, and show\nthat it admits $\\omega$-context-free comparators i.e. comparator automata\nexpressed by B\\\"uchi pushdown automata.<\/jats:p>","DOI":"10.46298\/lmcs-18(3:13)2022","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T13:09:55Z","timestamp":1659100195000},"source":"Crossref","is-referenced-by-count":1,"title":["Comparator automata in quantitative verification"],"prefix":"10.46298","volume":"Volume 18, Issue 3","author":[{"given":"Suguman","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swarat","family":"Chaudhuri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,7,29]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9865\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9865\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:17:13Z","timestamp":1687292233000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/5050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,29]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(3:13)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"1812.06569v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1812.06569v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1812.06569v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1812.06569","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1812.06569","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,7,29]]},"article-number":"5050"}}