On the Diophantine problem related to power circuits

Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn function. Power circuits are computational structures that support addition and the operation (x,y) ↦ x · 2ʸ on integers. They also posed the question of decidability of the Diophantine problem over the structure N>0; +, x · 2ʸ, ≤, 1, which is closely related to power circuits. In this paper, we prove that the Diophantine problem over this structure is undecidable. Published in the journal of Groups, Complexity, Cryptology