Either a modification of the simplify method or an extended version / separate:
- If an internal node has both a literal and it's negation, replace it with
true (if an Or) or false (if an And), as appropriate.
- If every child of an
Or node n is either literal L, or of the form And([L, ...]), then remove L from the children and add it to the parent of n. If n is the root, then a new root is created: And([L, n])
The first fixes some degenerate cases, and the second propagates recognized backbones up the structure. It needs to be revised slightly for DAGs instead of trees -- (1) only remove the literal if there's no other incoming edge to the And node child of n; and (2) another simplification to remove redundant literals if they are already implied (all ancestor paths have an And node with the literal as a sibling) -- but it's an important step in being able to assess backbones quickly (useful in other fields like planning with partial observability).
Either a modification of the
simplifymethod or an extended version / separate:true(if anOr) orfalse(if anAnd), as appropriate.Ornodenis either literalL, or of the formAnd([L, ...]), then removeLfrom the children and add it to the parent ofn. Ifnis the root, then a new root is created:And([L, n])The first fixes some degenerate cases, and the second propagates recognized backbones up the structure. It needs to be revised slightly for DAGs instead of trees -- (1) only remove the literal if there's no other incoming edge to the
Andnode child ofn; and (2) another simplification to remove redundant literals if they are already implied (all ancestor paths have anAndnode with the literal as a sibling) -- but it's an important step in being able to assess backbones quickly (useful in other fields like planning with partial observability).