Decision and optimization problems in the unreliable-circuit logic. (1st April 2017)

• Record Type: Journal Article
• Authors: Rasga, J.; Sernadas, C.; Mateus, P.; Sernadas, A.
• Is Part Of: Logic journal of the IGPL. Volume 25:Number 3(2017:Jun.)
• Page Start: 283
• Page End: 308
• Publication Date: 2017-04-01
• Subjects: Probabilistic logic -- unreliable circuits -- algorithms in logic -- computational complexity; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1093/jigpal/jzx005
• Languages: English
• ISSNs: 1367-0751

Abstract

Abstract: 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.