Decision and optimization problems in the unreliable-circuit logic

DOI10.1093/JIGPAL/JZX005zbMATH Open1405.03072arXiv1608.00533OpenAlexW2963449265WikidataQ59196610 ScholiaQ59196610MaRDI QIDQ4644487FDOQ4644487

Authors: Paulo Mateus, João Rasga, Cristina Sernadas, Amílcar Sernadas 

Publication date: 8 January 2019

Published in: Logic Journal of the IGPL (Search for Journal in Brave)

Abstract: The ambition constrained validity and the model witness problems in the logic UCL, for reasoning about circuits with unreliable gates, are analyzed. 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.

Full work available at URL: https://arxiv.org/abs/1608.00533

Recommendations

• Approximate reasoning about logic circuits with single-fan-out unreliable gates
• scientific article; zbMATH DE number 5906481
• scientific article; zbMATH DE number 2123418
• On asymptotically optimal circuits in the basis \(\{\&,\neg\}\) in the case of inverse faults at the outputs of elements
• On the circuits reliability in ``anticonjunction basis with constant faults at gate inputs

zbMATH Keywords

computational complexityprobabilistic logicalgorithms in logicunreliable circuits

Mathematics Subject Classification ID

Probability and inductive logic (03B48) Other nonclassical logic (03B60) Logic in computer science (03B70)

Cited In (5)

• Approximate reasoning about logic circuits with single-fan-out unreliable gates
• Title not available (Why is that?)
• Optimization of the operation of an unreliable multiple-state device
• About the choice of the variable to unassign in a decision repair algorithm
• An unexpected Boolean connective

This page was built for publication: Decision and optimization problems in the unreliable-circuit logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4644487)