Choice Calculus Recovery

Problem Description

General problem: Recover choice calculus expressions from given variation instances.

Input:

1. Abstract version of the program
2. Table of variables with their possible values

Desired Output: A choice calculus expression which is sound with respect to the given variation instances.

Example Input

Abstract program: [[#x]] + [[#y]] + [[#z]]

Table of possible values:

x	y	z
1	3	5
1	4	5
2	3	6
2	4	6

Graph representation

The variational structure can be represented by a graph by creating one node per possible variable-value combination and adding edges for each common occurance in one variation.

The graph can be further compacted by representing complete subgraphs with just one edge between the clusters:

Another possible representation is the inverse graph: just add the edges, that are not allowed.

Desired Output

A<1,2> + B<3,4> + A<5,6>

Other Examples

Fully synchronized variables

Input:

x	y
1	3
2	4

Graph:

Desired Output: A<1,2> + A<3,4>

Partially synchronized variables

Input:

x	y
1	3
2	3
2	4

Graph:

Desired Output: A<1,2> + A<3,B<3,4>>

Independent variables

Input:

x	y
1	3
2	3
1	4
2	4

Graph:

Desired Output: A<1,2> + B<3,4>

Dependent choices

Input:

x	y	z
1	4	6
2	4	7
3	5	6
3	5	7

Graph:

Desired Output: A<B<1,2>,3> + A<4,5> + B<6,7>