Constraint and Consequence
 
   
  Craig Holman   Research   Jabberwocky   Quotations   Contact
 
  Home > Jabberwocky           Previous      Next
 
 
 

Jabberwocky for June 9, 2008
 
 

Elegant Normal Form

          First in thread      Previous in thread      Next in thread

This work is derived from my doctoral dissertation and was written in 2001.

This is the first of at least four related posts and deals with the definition of Elegant Normal Form.

The second post will contain a proof that the set of eight constraint-tree transformations for the reduction of constraint trees to ENF are a complete set of reductions.

The third post will present the Reduce to Elegance algorithm.

The fourth post will present some examples of reduction to elegance.

Introduction

Each of the models of a Boolean expression must conform to at least one of the consistent selection sets that are produced by the Traverse-Graph algorithm during a partial application of the constraint calculus to the expression. We are free to modify the constraint tree in any way that does not alter the model-generability of the set of selection sets produced by traversal. For example, we may apply transformations to the constraint tree that have the effect of deleting inconsistent selection sets, deleting subsumable selection sets, or replacing a group of selection sets by one that subsumes each of them but that generates no new interpretations.

Elegant Normal Form (ENF), a new normal form for Boolean expressions, is defined in terms of structural constraints on the constraint tree that is derived from an expression.

Eight constraint-tree transformations for the reduction of constraint trees to ENF are presented and are proved to be a complete set of reductions.

An algorithm for reducing a constraint tree to ENF is presented.

Expressions having several levels (those having a compact structure, not in Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF)) can be reduced to ENF without first being reduced to CNF or DNF. If reduction results in the deletion of the entire constraint tree, then the expression is a contradiction. If a reduction results in a single And node with an empty set of constraints, the expression is a tautology.

Experimental results of the application of the Reduce-to-Elegance algorithm to a large number of expressions will be presented in later posts. Here are a few highlights from those results:

  • 99 % of the expressions (100 to 500 literals each) required fewer than 10,000 set operations for reduction to elegance and retained fewer than 2% of their original literals
  • None of the elegant equivalents of these expressions retained more than 9% of their literals from the original expression
  • 100 % of the contradictions were discovered to be contradictions during their reduction to elegance
  • 99.99 % of the tautologies were discovered to be tautologies during their reduction to elegance
  • 84 % of the original expressions did not require backtracking during the final stage of the Satisfiability Determination algorithm
  • 99 % of the elegant expressions did not require backtracking during the final stage of the Satisfiability Determination algorithm

In addition to providing a useful tool for facilitating the determination of the satisfiability of difficult expressions, the reduction of constraint trees to ENF is an effective method of simplifying multilevel Boolean expressions.

Elegant Normal Form

A constraint tree is in Elegant Normal Form (ENF) if the following conditions hold:

  1. All branch sets are consistent
  2. All terminal And nodes have non-empty guard sets
  3. All Or nodes have at least two children
  4. All non-terminal And nodes that are not the Root node and that have empty guard sets have at least two children
  5. For each Or node, the intersection of the guard sets of the children of the node is empty
  6. For each And node, the intersection of its guard set and its dominant set is empty
  7. For each And node, the intersection of its guard set and its command set is empty

A constraint tree that is in ENF will be referred to as an elegant constraint tree. A constraint graph that results from the application of the Make Graph algorithm to an elegant constraint tree is an elegant constraint graph. An expression is an elegant expression if its primary constraint tree is elegant. For every constraint tree, there exists a canonical elegant constraint tree that has the same model-generability as the original tree.

Transformations for the reduction of constraint trees to Elegant Normal Form

There are eight transformations that will be used to reduce constraint trees to ENF. For each transformation, a definition will be given that presents the follwoing information:

Transformation Name

Goal: What is the intent of the transformation?

Point of application: Where can the transformation be applied?

Preconditions: What conditions must hold before the transformation can be applied at the POA?

Action:" What steps must be taken to accomplish the transformation?

Postconditions:" What conditions either must hold after the transformation after the transformation has been applied to the POA?

Justification: What is the justification for the transformation? What supports the claim that it preserves the model-generability of the constraint trees to which it may be applied?

Critical set: What is the set of nodes that, if modified or released by another transformation, could affect the subsequent applicability of this transformation to the POA, or could alter the effect that the application of this transformation to the POA would have?

Modification set: What is the set of nodes that could be either modified or released by the application of this transformation to the POA? A node has been modified if a change has been made to either the node's guard set or its list of children.

Selection set modifications: Characterize the way in which this transformation will modify the selection sets of a constraint tree when it is applied.

Obviation criteria: Under what conditions is this transformation rendered unnecessary?

Abbreviation: What abbreviation will be used through out the rest of this document?

Example: A simple example of an application of the transformation. A single arrow will indicate the POA.

Delete Inconsistent Handle

Goal: To remove from a constraint set all selections containing the center of a broom whose handle is inconsistent.

Point of application: Any And Node.

Preconditions: The handle set of the broom centered at the POA is inconsistent.

Action: Delete the POA.

Postconditions:

  • The inconsistent broom centered at the POA has been deleted.
  • No constraints have been raised.
  • The parent of the POA's deletion-separation node may now have only one child, and thus may be a site for OrCut
  • The entire constraint tree may have been deleted, indicating that the constraint tree represents a contradiction.

Justification: All selections that contain the POA possess selection sets that conform to the POA's handle set. Since the POA's handle set is consistent, all selections that contain the POA are inconsistent and may be removed from the constraint tree without altering its model-generability.

Critical set: All And nodes in the handle of the POA.

Modification set: The parent of the DSN and all of the nodes in the subtree rooted at the DSN.

Selection set modifications: None.

Obviation criteria: The POA has been released, or the POA's handle set has become consistent.

Abbreviation: InconHandle

Example:

Promote Common Constraints

Goal: To promote constraints that are common to all children of an Or node to the parent of that Or node.

Point of application: Any Or node.

Preconditions: The intersection of the guard sets of the children of the POA is not empty.

Action: Let S be the intersection of the guard sets of the children of the POA. Add the constraints in S to the guard set of the parent of the POA. Subtract the constraints in S from the guard set of each of the children in the POA.

Postconditions: The children of the POA may have guard sets that have been reduced to zero or one constraints, making the POA a possible site for 0Subsume or one or more of the POA's children a possible site for 1Subsume.

Justification: Every selection that contains the POA's parent necessarily contains the POA and one of the POA's children. The selection sets associated with each of these selections necessarily contain each of the contraints that are in the intersection set S. By adding the constraints in S to the guard set of the POA's parent, which all of these selections have in common, and subtracting the constraints in S from the guard sets of each of the POA's children, we are able to reduce the weight of the tree without changing either the number of the composition of any of the selection sets of the tree.

Critical set: The POA and its children

Modification set: The parent of the POA and the children of the POA.

Selection set modifications: None.

Obviation criteria: The POA has been released or the intersection of the guard sets of the POA's children has become empty

Abbreviation: Promote

Example:

Subtract Redundant Constraints

Goal: To subtract the dominant set of an And node from its guard set, thereby eliminating redundant constraints.

Point of application: Any non-root And node.

Preconditions: The intersection of the POA's dominant set and the POA's guard set is not empty.

Action: Subtract the POA's dominant set from the POA's guard set.

Postconditions: The guard set of the POA may have been reduced to zero or one constarints, making the POA a possible site for 1Subsume, 1CCConstraint, and AndCut, and making the POA's parent a possible site for 1Subsume.

Justification: No change is made to any of the selection sets, even though the weight of the tree is reduced.

Critical set: The POA and all And nodes that dominate the POA.

Modification set: The POA.

Selection set modifications: None.

Obviation criteria: The POA has been released, or the intersection of the POA's dominant set and the POA's guard set has become empty.

Abbreviation: Redundant

Example:

Cut Unnecessary Or

Goal: To remove an unnecessary Or node and its child.

Point of application: An Or node.

Preconditions: The POA has only one child.

Action: Add the constraints in the POA's child's guard set to the guard set of the POA's parent. Add the POA's grandchildren to the POA's parent list of children. Remove the POA from the POA's parent's list of children. Release the POA and the POA's child.

Postconditions: If the guard set of the parent of the POA has been changed, at least one constraint has been raised, and that constraint will have greater scope if the POA has one or more siblings. Thus, it may be necessary to check the applicability of InconHandle, Redundant, and Promote to local sites.

Justification: No change is made to any of the selection sets even though the weight of the tree is reduced.

Critical set: The POA.

Modification set: The POA, its parent, and its child.

Selection set modifications: None.

Obviation criteria: The POA has been released, or the POA has become the parent of more than one child

Abbreviation: OrCut

Example:

Cut Unnecessary And

Goal: To remove an unnecessary And node and its child.

Point of application: Any non-terminal And node.

Preconditions: The POA has an empty guard set and one child.

Action: Add the POA's grandchildren to the POA's parent's list of children. Remove the POA from the POA's parent's list of children. Release the POA and the POA's child.

Postconditions: The scope of the commanding constraints in the POA's former grandchildren has increased, and the POA's parent is a possible site for 0Subsume.

Justification: No change has been made to any of the selection sets in the constraint tree, even though the weight of the tree has been reduced.

Critical set: The POA.

Modification set: The POA, its parent, and its child.

Selection set modifications: None

Obviation criteria: The POA has been released, the POA's guard set has become non-empty, or the POA has become the parent of more than one child.

Abbreviation: AndCut

Example:

0-Constraint Subsumption

Goal: To disconnect trivially tautological subtrees from the constraint tree.

Point of application: Any Or node.

Preconditions: The POA has a child that has an empty guard set and no children.

Action: Disconnect the POA by removing the POA from its parent's list of children and releasing the subtree rooted at the POA.

Postconditions: A trivially-tautological subtree has been disconnected. The POA's grandparent may be a site for 0Subsume.

Justification: All of the selection sets that are removed are subsumed by one or more of the selection sets associated with selections containing the POA. Since the POA's parent will always then be a site for OrCut, the two steps may be combined together by disconnecting the parent of the POA.

Critical set: The POA.

Modification set: The POA's grandparent, the POA's parent, and all nodes dominated by the POA's parent.

Selection set modifications: At least one selection and one selection set is removed due to the subsumption.

Obviation criteria: The POA has been released.

Abbreviation: 0Subsume

Example:

1-Constraint Subsumption

Goal: To remove some subsumable selections from the constraint tree.

Point of application: Any non-root And node.

Preconditions: The POA's guard set contains contraint X and the POA is commanded by a terminal AND node COM whose guard set consists of the constarint X.

Action: Delete the POA.

Postconditions: The POA has been deleted. If it exists, the parent of the deletion-separation node may have only one child and may be a site for OrCut.

Justification: Every selection that contains COM's parent, does not contain COM, and whose selection set contains X is associated with a selection set that is subsumable by a selection set associated with a selection containing COM.

Critical set: The POA and COM.

Modification set: All nodes in the subtree rooted at the DSN.

Selection set modifications: At least one selection and one selection set is removed due to subsumption.

Obviation criteria: The POA has been released, X has been subtracted from the guard set of COM, or X has been subtracted form the guard set of the POA.

Abbreviation: 1Subsume

Example:

1-Constraint-Complement Subtraction

Goal: To remove a constraint that is not needed because it is commanded by its negated form.

Point of application: Any non-root And node.

Preconditions: The POA's guard set contains constraint X and the POA is commanded by a terminal And node COM whose guard set consists of the constraint that is the opposite of X.

Action: Subtract the constraint X from the guard set of the POA.

Postconditions: The size of the guard set of the POA has been reduced by one, the POA may command other nodes, and the POA's parent may be a site for 0Subsume.

Justification: This transformation is justified by exhaustive distribution as follows:

X Ú ( ¬ X Ù Y )  ≡   ( X Ú ¬ X ) Ù ( X Ú Y )  ≡  ( X Ú Y )

Every selection that contains the POA also contains COM's parent. Every interpretation that contains the opposite of X and that conforms to the selection set of a selection that contains COM's parent can be subsumed by an interpretation that conforms to the selection set of a selection that contains COM. By subtracting X from POA's guard set, we are only 'introducing' interpretations that must be subsumable. In this way, a constraint can be subtracted without altering the model-generability of the constraint tree.

Critical set: The POA and COM.

Modification set: The POA.

Selection set modifications: At least one constraint is subtracted from at least one selection set.

Obviation criteria: The POA has been released, X has been subtracted from the guard set of COM, or the negation of X has been subtracted from the guard set of the POA.

Abbreviation: 1CCSubtract

Example:

          First in thread      Previous in thread      Next in thread

 
 
 
  Home > Jabberwocky           Previous      Next
 
  Craig Holman   Research   Jabberwocky   Quotations   Contact  
 
 
 
  Patterncraft™ and Constraint and Consequence™
are trademarks of Craig Stewart Holman

Copyright © 2008 Craig Stewart Holman

Copyright and Legal Notices

All Rights Reserved.

 
   
 
  Patterncraft logo