{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:21Z","timestamp":1760202681806,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,3,4]],"date-time":"2013-03-04T00:00:00Z","timestamp":1362355200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This paper is concerned with the computational complexity of equivalence and\nminimisation for automata with transition weights in the field Q of rational\nnumbers. We use polynomial identity testing and the Isolation Lemma to obtain\ncomplexity bounds, focussing on the class NC of problems within P solvable in\npolylogarithmic parallel time. For finite Q-weighted automata, we give a\nrandomised NC procedure that either outputs that two automata are equivalent or\nreturns a word on which they differ. We also give an NC procedure for deciding\nwhether a given automaton is minimal, as well as a randomised NC procedure that\nminimises an automaton. We consider probabilistic automata with rewards,\nsimilar to Markov Decision Processes. For these automata we consider two\nnotions of equivalence: expectation equivalence and distribution equivalence.\nThe former requires that two automata have the same expected reward on each\ninput word, while the latter requires that each input word induce the same\ndistribution on rewards in each automaton. For both notions we give algorithms\nfor deciding equivalence by reduction to equivalence of Q-weighted automata.\nFinally we show that the equivalence problem for Q-weighted visibly pushdown\nautomata is logspace equivalent to the polynomial identity testing problem.<\/jats:p>","DOI":"10.2168\/lmcs-9(1:8)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:36:16Z","timestamp":1385732176000},"source":"Crossref","is-referenced-by-count":15,"title":["On the Complexity of Equivalence and Minimisation for Q-weighted Automata"],"prefix":"10.46298","volume":"Volume 9, Issue 1","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[]},{"given":"Andrzej","family":"Murawski","sequence":"additional","affiliation":[]},{"given":"Joel","family":"Ouaknine","sequence":"additional","affiliation":[]},{"given":"Bjoern","family":"Wachter","sequence":"additional","affiliation":[]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2013,3,4]]},"reference":[{"key":"775:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/908\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/908\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:58:55Z","timestamp":1681243135000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,4]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(1:8)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1302.2818","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1302.2818","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2013,3,4]]},"article-number":"908"}}