Here is a summary of what we have been discussing with Ravi.
It is also a preparation for the proposal.

The focus is on a small library of algorithms useful for the 
implementation of AOSD systems. This is especially important 
in a world of multiple concern-specific aspect languages
where a project-specific set of aspect languages will be invented
and implemented (See Sergei's Thesis Proposal).

For our theory of incremental design, we need to study incremental
algorithms.

My view of incremental design is as follows:
Given a design problem P, identify a set of concerns and develop
a set of collaborating aspect-languages for those concerns.
Analyze the interactions and tradeoffs between the aspect languages
and implement them using a standard library, called the CCIS selector library. 

The question is: does the traversal graph algorithm survive?
What is a minimal set of algorithms we need to generate 
code for selector languages efficiently?

Theo: let us know when you have the formalization of REV and TMV.

-- Karl

What is the connection between NFA/regex and strategy graphs
for the purpose of defining paths in graphs?

Goals: 

1. We want to offer a set of standard algorithms that are useful for processing
selector expressions in aspect-oriented programming/design languages. 
Implementors of selector languages can come here and pick their algorithms.
(I envision an extension of the AP Library to a Selector Library)

2. we want to bring order to the landscape of selector languages
and confirm that regular expressions and their variants are the foundation for the various 
selector language mechanisms.


We distinguish between strategy graphs with 
  the identity name map (SG)
  a general name map    (SGG)

We distinguish between strategy graphs with 
  with complex edges (SG)
  with complex and simple edges (SGS)
  with intersection (SGI)

We distinguish between 
  standard regular expressions (RE)
  extended regular expressions (with negation and intersection) (ERE)
  regular expressions with variables (REV)

We consider the satisfiability problem SAT(PR):
Given a graph G and a selector expression s in PR, is there a path satisfying s?

We consider the satisfiability problem SAT-DFS(PR):
Given a graph G and a selector expression s in PR, is there a DFS-path satisfying s?
(Motivation: execution histories)
Ravi has a constraction that shows:
SAT(PR) is in P iff SAT-DFS(PR) is in P.

For REV:
We consider the satisfiability problem SAT(REV):
Given a graph G and a selector expression s with variables v (in REV), 
is there a path p and an assignment to the variables v satisfying s?

Then we have the two-phase selector language mechanism (like tracematch)
where we define symbols using regexp and then we define a regexp
in terms of those symbols. We distinguish between tracematch (TM)
and tracematch with variables (TMV).


Polynomial cases:
=================

SAT(SG), SAT(SGG), SAT(SGS), SAT(RE), SAT(TM)

NP-complete cases:
==================

SAT(ERE), SAT(ERV), SAT(SGI), SAT(TMV)?
What is the connection between REV and TMV?

FPT cases:
==========

SAT(ERE) is solvable in G * 2**|s|: 

Solution 1:
Translate the ERE into an exponentially
larger RE and do the cross product with G.

Solution Pengcheng(?):
Translate the ERE into an exponentially
larger SG and do the cross product with G (Traversal Graph).

Is there an advantage to Pengcheng's translation?

SAT(SGI) is solvable in G * 2**|s|: 
Translate the SGI into an exponentially
larger SG and do the cross product with G.

Polynomial Reductions:
======================

SG to NFA (?)
G to NFA

NFA to RE
RE to NFA

RE to SG
SG to R

Open issues:
What can be done if the metagraph is only partially known?