Collaborating Authors

AMIA: an environment for knowledge-based discrete-time systems simulation Michel Page J rSme Gensel Mahfoud Boudis

AAAI Conferences

AMIA is original in two respects. First it uses an algebraic modeling language for combining discrete-time models (difference equations) and symbolic knowledge. Second, it uses a new simulation algorithm able to exploit this combination of numerical and symbolic knowledge. AMIA also includes a model management system for supporting the modeling and simulation process.

Counting Models using Connected Components

AAAI Conferences

Recent work by Birnbaum & Lozinskii [1999] demonstrated that a clever yet simple extension of the well-known Davis-Putnam procedure for solving instances of propositional satisfiability yields an efficient scheme for counting the number of satisfying assignments (models). We present a new extension, based on recursively identifying connected constraint-graph components, that substantially improves counting performance on random 3-SAT instances as well as benchmark instances from the SATLIB and Beijing suites. In addition, from a structure-based perspective of worst-case complexity, while polynomial time satisfiability checking is known to require only a backtrack search algorithm enhanced with nogood learning, we show that polynomial time counting using backtrack search requires an additional enhancement: good learning.

A Rearrangement Search Strategy for Determining Propositional Satisfiability

AAAI Conferences

We present a simple algorithm for determining the satisfiability of propositional formulas in Conjunctive Normal Form. As the procedure searches for a satisfying truth assignment it dynamically rearranges the order in which variables are considered. The choice of which variable to assign a truth value next is guided by an upper bound on the size of the search remaining; the procedure makes the choice which yields the smallest upper bound on the size of the remaining search. We describe several upper bound functions and discuss the tradeoff between accurate upper bound functions and the overhead required to compute the upper bounds. Experimental data shows that for one easily computed upper bound the reduction in the size of the search spa,ce more than compensates for the 0verhea.d

Generating Models of a Matched Formula With a Polynomial Delay

Journal of Artificial Intelligence Research

A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. Such a formula is always satisfiable. Matched formulas are used, for example, in the area of parametrized complexity. We prove that the problem of counting the number of the models (satisfying assignments) of a matched formula is #P-complete. On the other hand, we define a class of formulas generalizing the matched formulas and prove that for a formula in this class one can choose in polynomial time a variable suitable for splitting the tree for the search of the models of the formula. As a consequence, the models of a formula from this class, in particular of any matched formula, can be generated sequentially with a delay polynomial in the size of the input. On the other hand, we prove that this task cannot be performed efficiently for linearly satisfiable formulas, which is a generalization of matched formulas containing the class considered above.