{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T13:29:52Z","timestamp":1748611792572},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Bit-precise reasoning is important for many practical applications of<\/jats:p><jats:p>Satisfiability Modulo Theories (SMT). In recent years efficient approaches<\/jats:p><jats:p>for solving fixed-size bit-vector formulas have been developed. From<\/jats:p><jats:p>the theoretical point of view, only few results on the complexity of<\/jats:p><jats:p>fixed-size bit-vector logics have been published. In this paper we show<\/jats:p><jats:p>that some of these results only hold if unary encoding on the bit-width of<\/jats:p><jats:p>bit-vectors is used.  We then consider fixed-size bit-vector logics with<\/jats:p><jats:p>binary encoded bit-width and establish new complexity results. Our proofs<\/jats:p><jats:p>show that binary encoding adds more expressiveness to bit-vector logics,<\/jats:p><jats:p>e.g. it makes fixed-size bit-vector logic even without uninterpreted<\/jats:p><jats:p>functions nor quantication NExpTime-complete. We also show that under<\/jats:p><jats:p>certain restrictions the increase of complexity when using binary encoding<\/jats:p><jats:p>can be avoided.<\/jats:p>","DOI":"10.29007\/cvnz","type":"proceedings-article","created":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T17:59:11Z","timestamp":1516730351000},"page":"44-30","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Fixed-Size Bit-Vector Logics with Binary Encoded Bit-Width"],"prefix":"10.29007","volume":"20","author":[{"given":"Gergely","family":"Kov\u00e1sznai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Fr\u00f6hlich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Biere","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"11545","event":{"name":"SMT 2012. 10th International Workshop on Satisfiability Modulo Theories"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T17:59:14Z","timestamp":1516730354000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/SF7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/cvnz","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}