{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:06Z","timestamp":1753894386503,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T00:00:00Z","timestamp":1647302400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Given two weighted automata, we consider the problem of whether one is big-O\nof the other, i.e., if the weight of every finite word in the first is not\ngreater than some constant multiple of the weight in the second.\n  We show that the problem is undecidable, even for the instantiation of\nweighted automata as labelled Markov chains. Moreover, even when it is known\nthat one weighted automaton is big-O of another, the problem of finding or\napproximating the associated constant is also undecidable.\n  Our positive results show that the big-O problem is polynomial-time solvable\nfor unambiguous automata, coNP-complete for unlabelled weighted automata (i.e.,\nwhen the alphabet is a single character) and decidable, subject to Schanuel's\nconjecture, when the language is bounded (i.e., a subset of $w_1^*\\dots w_m^*$\nfor some finite words $w_1,\\dots,w_m$) or when the automaton has finite\nambiguity.\n  On labelled Markov chains, the problem can be restated as a ratio total\nvariation distance, which, instead of finding the maximum difference between\nthe probabilities of any two events, finds the maximum ratio between the\nprobabilities of any two events. The problem is related to\n$\\varepsilon$-differential privacy, for which the optimal constant of the big-O\nnotation is exactly $\\exp(\\varepsilon)$.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:40)2022","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T21:35:10Z","timestamp":1647552910000},"source":"Crossref","is-referenced-by-count":2,"title":["The Big-O Problem"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kiefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej S.","family":"Murawski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Purser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,3,15]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9217\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9217\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:47Z","timestamp":1687292387000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,15]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:40)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2007.07694v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2007.07694v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2007.07694","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2007.07694","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,3,15]]},"article-number":"7343"}}