On Synthesis for Unbounded Bit-vector Arithmetic

We propose to describe computations using QFPAbit, a language of quantifier-free linear arithmetic on unbounded integers with bitvector operations. Given a QFPAbit formula with input and output variables, we describe an algo- rithm that generates an efficient linear-space function from a sequence of inputs to a sequence of outputs, without the causality restriction of reactive synthesis. The starting point for our method is a polynomial-time translation of QFPAbit into sequential circuits that check the correctness of the input/output relation. From such circuits, our synthesis algorithm produces solved circuits from inputs to outputs that are no more than singly exponential in size of the original formula. In addition to the general synthesis algorithm, we present techniques that ensure that, for example, multiplication and division with large constants do not lead to an exponential blowup, addressing a practical problem with a previous approach that used the MONA tool to generate the specification automata.