Decision and optimization problems in the unreliable-circuit logic. (1st April 2017) - Rasga, J.; Sernadas, C.; Mateus, P.; Sernadas, A.
Abstract: The ambition constrained validity and the model witness problems in the logic 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.