{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:36Z","timestamp":1760202576055,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,3,19]],"date-time":"2008-03-19T00:00:00Z","timestamp":1205884800000},"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>In this paper, we first introduce a lower bound technique for the state\ncomplexity of transformations of automata. Namely we suggest first considering\nthe class of full automata in lower bound analysis, and later reducing the size\nof the large alphabet via alphabet substitutions. Then we apply such technique\nto the complementation of nondeterministic \\omega-automata, and obtain several\nlower bound results. Particularly, we prove an \\omega((0.76n)^n) lower bound\nfor B\\\"uchi complementation, which also holds for almost every complementation\nor determinization transformation of nondeterministic omega-automata, and prove\nan optimal (\\omega(nk))^n lower bound for the complementation of generalized\nB\\\"uchi automata, which holds for Streett automata as well.<\/jats:p>","DOI":"10.2168\/lmcs-4(1:5)2008","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T13:26:52Z","timestamp":1212499612000},"source":"Crossref","is-referenced-by-count":21,"title":["Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique"],"prefix":"10.46298","volume":"Volume 4, Issue 1","author":[{"given":"Qiqi","family":"Yan","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,3,19]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/992\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/992\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:49Z","timestamp":1681243249000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,19]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(1:5)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0802.1226","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0802.1226","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/978-3-662-44522-8_41","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2008,3,19]]},"article-number":"992"}}