Improving the Generation of Random Modal Formulae
for Testing Decision Procedures

by
Peter F. Patel-Schneider & Roberto Sebastiani

Abstract

The recent emergence of heavily-optimised modal decision procedures has lead to a number of generation methods for modal formulae. However, the generation methods developed so far are not satisfactory. To cope with this fact, we propose a much improved version of one of the best-known methods, the random CNF[]m test. The new method drastically reduces the influence of a major flaw of the previous method, and allows us to generate a wider variety of problems covering much more of the input space. This produces more interesting test sets for the current generation of modal decision procedures.

Talk presented at IJCAR-2001 Workshop on Issues in the Design and Experimental Evaluation of Systems for Modal and Temporal Logics, Sienna, Italy, June 2001.

Empirical Testing of Modal Decision Procedures

Why:
to see how a decision procedure performs
How:
try the procedure on lots of formulae
Problem:
generating a reasonable test set

Desirable Features for Good Test Sets

Significance
Difficulty
Valid vs. non-valid balance
Reproducibility

Achieving Desirable Features

Parameterisation
Control
Modal vs. Propositional Balance
Data organisation

Problems with Test Sets

Redundancy
Triviality
Artificiality
Over-size

Using Randomly-generated Modal Formulae

Why:
easy to generate lots of formulae
How:
generate formulae according to some recipe, typically
Parameters:

Using Randomly-generated Modal Formulae

Problem:
repeated propositional variables in a clause
Solution:
don't repeat

Problem:
complementary literals in a clause
Solution:
don't repeat

Using Randomly-generated Modal Formulae

Problem:
small collection of clauses may be propositionally inconsistent
Solution:
eliminate propositional variables (except at maximum depth)
Problem:
makes the formulae unnatural and very hard
Solution:
new generation methodology

First Change

Old Method, Depth 2, Prop. Prob. 0.5

??
Median difficulty for DLP (version 4.1).

Old Method, Depth 2, Prop. Prob. 0.5

??
Median difficulty for *SAT (version 1.3).

Old Method, Depth 2, Prop. Prob. 0.5

??
Fraction of formulae that can be determined unsatifiable (or satisfiable) by purely propositional means.

New Method, Depth 2, Prop. Prob. 0.5

??
Median difficulty for DLP (version 4.1).

New Method, Depth 2, Prop. Prob. 0.5

??
Median difficulty for *SAT (version 1.3).

New Method, Depth 2, Prop. Prob. 0.5

??
Fraction of formulae that can be determined unsatifiable (or satisfiable) by purely propositional means.

Second Change

New Method, Depth 2, Prop. Prob. 0.5, 2.5 Clauses

??
Median difficulty for DLP (version 4.1).

New Method, Depth 2, Prop. Prob. 0.5, 2.5 Clauses

??
Fraction of formulae that can be determined unsatifiable (or satisfiable) by purely propositional means.

Third Change

C=[[1,8,1]]; p=[[[1,0],[0,3,0],[0,3,3,0]]]; N=3,4; d=3,4

??
Median difficulty for DLP (version 4.1).

C=[[1,8,1]]; p=[[[1,0],[0,3,0],[0,3,3,0]]]; N=3,4; d=3,4

??
Fraction of formulae that can be determined unsatifiable (or satisfiable) by purely propositional means.

Using the New Generator

Basic Usage
Settings
Effect
Characteristics
Advanced Usage
Settings
Effect
Characteristics

Improvements

Summary