Consider series-parallel graphs
D : [A,B] | D1+D2 | D1*D2 | !D | D1.D2

To define negation, Pengcheng proposes an automata theoretic
approach: We turn the NFA corresponding to 
a series-parallel expression into a DFA and apply
the standard automata-theoretic construction
of producing the complement automaton
by using the complement of the acceptance states.

This resolves the difficulty of having an algebraic
expression for defining !(D1.D2).

Of course this definition is exponential in nature (the
NFA to DFA transition) and the question is whether
there is a polynomial algorithm for:

Given a strategy S, class graph G, object tree T conforming to G,
compute the subtree T' of T that is selected by S.
The size of the input is the sum of the sizes of
S, G and T.

-- Karl


Do negation by algebraic rules:

Pengcheng claims this is not consistent with the above
definition of negation:
![A,B] = ([!A,B] + [A,!B] + [!A,!B])

Why? Please can you explain?

!(D1+D2) = !D1 * !D2
!D1*D2 = !D1 + !D2

===========??
!(D1.D2) = !D1 . D2 + D1 . !D2 // not correct

The following not correct either:
!(D1.D2) = !D1 . D2 + D1 . !D2 + [Source(D1),!Target(D1)].[!Target(D1),Target(D2)]

Need an operation:

ChangeTarget(D) : follows D except that target is deleted
ChangeSource(D) : follows D except that it starts at complement of source of D
??

!([A,B].[B,C]) = ![A,B].[B,C] + [A,B].![B,C] + ...
= ([!A,B] + [A,!B] + [!A,!B]).[B,C] + [A,B].([!B,C] + [B,!C] + [!B,!C]) 

= [!A,B].[B,C] + [A,B].[B,!C] + [A,!B].[!B,C]

Check:
!![A,B] = !((([!A,B] + [A,!B]) + [!A,!B]))
= !([!A,B] + [A,!B]) * ! [!A,!B]
= ![!A,B] * ![A,!B] * ! [!A,!B]
= ([A,B] +[!A,!B] [A,!B]) * ([!A,!B]+[A,B]+[!A,B])*([A,!B]+[!A,B]+[A,B])
= (... + [A,B] + ...) * (... + [A,B] + ...) * (... + [A,B] + ...)
= [A,B]


Complexity:

moving negation inside might lead to exponential increase
in size of formula.