Method and system for rapid evaluation of logical expressions
    11.
    发明授权
    Method and system for rapid evaluation of logical expressions 有权
    逻辑表达式快速评估的方法和系统

    公开(公告)号:US07917455B1

    公开(公告)日:2011-03-29

    申请号:US12622907

    申请日:2009-11-20

    IPC分类号: G06F15/18

    CPC分类号: G06N99/005

    摘要: Methods and systems capable of determining which subset of a set of logical expressions are true with relatively few evaluations of the primitives that together with any standard logical connectives, make up the logical expressions. A plurality of directed acyclic graphs, each graph including at least one root node, at least one leaf node, and at least one non-leaf node associated with a leaf node. Each node is associated with a, possibly empty, subset of presumed to be true logical expressions. Each non-leaf node is associated with one of the primitives mentioned in any of the logical expressions. Edges are defined between two of the nodes, each edge being associated with a possible value, or range of possible values, of the primitive associated with the node at the tail of the edge. Paths are defined through each of the directed acyclic graphs from a root node to a leaf node by recursively following each edge corresponding to the current value of the primitive at a selected non-leaf node. Lastly, subsets of logical expressions associated with the nodes on the defined paths are collated to yield a subset of logical expressions that are true.

    摘要翻译: 方法和系统能够确定一组逻辑表达式的哪个子集是真实的,而对于与任何标准逻辑连接符一起构成逻辑表达式的基元的相对较少的评估。 多个有向无环图,每个图包括至少一个根节点,至少一个叶节点和与叶节点相关联的至少一个非叶节点。 每个节点与假设为真逻辑表达式的可能为空的子集相关联。 每个非叶节点与任何逻辑表达式中提到的原语之一相关联。 在两个节点之间定义边缘,每个边缘与与边缘尾部的节点相关联的基元的可能值或可能值的范围相关联。 通过在选定的非叶节点处递归地跟随对应于原语的当前值的每个边缘,通过从根节点到叶节点的每个有向无环图来定义路径。 最后,与定义的路径上的节点相关联的逻辑表达式的子集进行整理,以产生真实的逻辑表达式的子集。