Decision and optimization problems in the unreliable-circuit logic
João Rasga, Cristina Sernadas, Paulo Mateus, Amı́lcar Sernadas · Logic Journal of IGPL · 2017
The ambition constrained validity and the model witness problems in the logic |$\mathsf{UCL}$|, for reasoning about circuits with unreliable gates are analysed. Moreover, two additional problems, motivated by the applications, are studied. One consists of finding bounds on the reliability rate of the gates that ensure that a given circuit has an intended success rate. The other consists of finding a reliability rate of the gates that maximizes the success rate of a given circuit. Sound and complete algorithms are developed for these problems and their computational complexity is studied.