Invention Grant
- Patent Title: Program synthesis with existentially and universally quantified belief propagation using probabilistic inference
- Patent Title (中): 使用概率推理的存在和普遍量化的信念传播的程序综合
-
Application No.: US13018643Application Date: 2011-02-01
-
Publication No.: US08825572B2Publication Date: 2014-09-02
- Inventor: Aditya Nori , Sriram Rajamani , Rahul Srinivasan , Sumit Gulwani
- Applicant: Aditya Nori , Sriram Rajamani , Rahul Srinivasan , Sumit Gulwani
- Applicant Address: US WA Redmond
- Assignee: Microsoft Corporation
- Current Assignee: Microsoft Corporation
- Current Assignee Address: US WA Redmond
- Agent Steve Wight; Carole Boelitz; Micky Minhas
- Main IPC: G06F19/28
- IPC: G06F19/28 ; G06N7/00
Abstract:
A quantified belief propagation (QBP) algorithm receives as input an existentially quantified boolean formula (QBF) of existentially quantified boolean variables, universally quantified variables, and boolean operators. A tripartite graph is constructed, and includes (i) there-exists nodes that correspond to and represent the existentially quantified variables, (ii) for-all nodes that correspond to and represent the universally quantified variables, and (iii) sub-formula nodes that correspond to and represent sub-formulas of the QBF. A set of boolean values of the existentially quantified variables is found by (i) passing a first message from an arbitrary sub-formula node to an arbitrary for-all node, and (ii) in response, passing a second message from the arbitrary for-all node to the arbitrary sub-formula node.
Public/Granted literature
- US20120197829A1 QUANTIFIED BELIEF PROPAGATION Public/Granted day:2012-08-02
Information query
