Generalized Satisfiability Problem (GSP)

• Theory
• GSP Demonstration Program
• Starting:
• on CS cluster : % ~artas/GSP/GSP&
• Running the program:
• Getting a formula to work on
• Load formula from a file
• Type in new formula (syntax)
• Generate formula
• Computing Weighted Depth or Channel Width Tree
• Algorithm
• Adjusting max depth
• Computed values (Depth, Time, Space, Cost)
• Drawing a tree (Contracted/Expanded Tree, Tree nodes)
• Evaluating formula using Weighted Depth or Channel width trees
• General Algorithm
• Does solution exist ?
• Is formula Valid ?
• Count Number of solutions
• Minimum Weighted Sum
• Maximum Weighted Sum
• Maximum number of satisfied predicates
• Parity of number of solutions
• Is solution unique ?
• Program Implementation (maitanace information for a programmer).

June, 1997
Arthur Chtcherba
E-Mail: