Abstract:
We define a new family of languages, called strategy languages.
As opposed to a regular language that is defined by one artefact
(a regular expression or an automaton), a strategy language is defined 
by two artefacts: a class graph and a strategy graph.

We have several motivations for this investigation?

1. Better theoretical understanding of strategies. They play an important role
   in aspect-oriented programming in the role of pointcuts and traversal
   specifications.
2. Faster algorithms for AspectJ and Demeter.

A primitive strategy language L(G) over an alphabet Sigma is a tuple
SL(G) = (Sigma, ClassGraph G = (Sigma, E), StrategyGraph S = (SG,s,t)).
SG is a subgraph of the transitive closure of G.
SL consists of all strings corresponding to node paths from 
s to t in G satisfying S, i.e. they are expansions of (s,t) paths
in S.
We also allow bypassing constraints (class graph
node sets) on the strategy edges.
If G is fixed we write L instead of L(G).

A strategy language (for a given class graph) is defined using union,
concatenation (join point only once), intersection and negation
and repetition (*).

Questions about strategy languages

Can every strategy language be expressed as a primitive strategy language?

Is x in L: in P for L primitive. What about general L?

Is L = empty? in P for L primitive. What about general L?
Is L(G) empty for all class graphs G?

Is L1 = L2? Decidable. Similar to equivalence of regular expressions.
Is L1(G) = L2(G) for all class graphs G.

same for subset

Is L1 \intersect L2 empty? In P if class graph is a dag. What about general
class graphs?

Is L1 \intersect L2 \intersect ... \intersect Ln empty. Conjectured to be NP complete.

Is L1(G) \intersect L2(G) empty for all class graphs?

Is L regular? Always.

Are all regular languages strategy languages?