June 16, 2004

Ravi is in the process of termining the computational complexity
of strategy minimization.

To explore the space around strategies, Ravi has proposed 
new concepts and algorithms.

Ravi has proposed to name explicit traversals "elemental strategies".
An elemental strategy is a subgraph of the class graph.
A complex strategy is a strategy that is not elemental. It is
a subgraph of the transitive closure of the class graph.

For now we assume that the class graph is a DAG.

Elemental strategies have the following desirable properties:
Negation of an elemental strategy is small: it is the union
of a small number of elemental strategies (chains and antichains
play a role here. See an explanation of Dilworth's theorem).
Intersection is also simple: intersection of graphs.

A complex strategy that is compositionally consistent with the class
graph can be expanded into an elemental
strategy by adding more edges. 10 years ago we called
this graph the propagation graph.
For this elemental graph, we can apply the basic
operations efficiently.

Ravi has counting arguments that show that both with
elemental and complex strategies we can not represent all
path sets even when we allow expressions of 
polynomial size.

Ravi also has an argument that shows that 
complex strategies are exponentially more powerful
than elemental strategies.

If we don't have compositional consistency for the complex
strategy and  the class graph we might be able to represent
the complex strategy using a small number of elemental strategies.

Another interesting topic (related to Jeff's interests)
is the satisfiability question for strategies:

We consider strategies (elemental or complex) with union and negation.
For elemental strategies, satisfiability seems polynomial.
What about complex strategies with negation and union?

-- Karl