@TECHREPORT{TR-karl-jeff-ravi:sep-2004,
AUTHOR = "Karl J. Lieberherr and Jeffrey Palm and Ravi Sundaram",
TITLE = "Expressiveness and Complexity of Crosscut Languages",
INSTITUTION = "Northeastern University",
YEAR = 2004,
MONTH = "September",
NUMBER = "NU-CCIS-04-10"
}

Paper .

Errata: p2 = !x1 | x2 in 3.1 in the example that is translated to AspectJ.
In the AspectJ example, the class Target should be renamed to T to be consistent with Figure 1.
There should be a note that !x1 in Figure 1 is represented as Nx1 in the AspectJ program.

Notes by Karl

The next steps will be to explore connections to the XPath work.
Some of the XPath work studies the implication problem (Select-Impl)
without a meta graph. Use the idea of learning the meta graph
from examples to connect to the world where the meta graph is present.
This might unify many of the proofs in the XPath community.

As shown in the paper, some AspectJ pointcuts can be 
expressed in a lower-complexity fragment of SD.
When we translate from a polynomial sublanguage of SD
to SAJ, we end up in an exponential sublanguage of SAJ.
So let's define: A language X with P-time algorithm is more expressive
than a language Y
if there is no translation to Y so that the subset used in 
Y is P-time. SD is more expressive than SAJ because Select-SAT/-/SD
is polynomial but there is no polynomial subset of SAJ
that can express the same. This needs to be polished a bit.

Here is a try:
We have X with polynomial algorithm for some problem PP.
We have Y with a set of sublanguages SS of Y
(based on subsets of operators) and with Y least as expressive as X.
X is better (or "efficiently more expressive for PP" or "more powerful for PP"
or "has an efficient niche for PP with respect to")  than Y, 
if for all operator sublanguages of Y that contain X problem PP is NP-complete.

This sounds best:
X is efficiently more expressive for problem PP than Y,
if X is polynomial for PP and 
if for all operator sublanguages of Y that contain X problem PP is NP-complete.

Note: This is a practically useful notion because tool implementors
have to implement the operators in a general way.

Claim:
-/SD with bypassing is efficiently more expressive for PP than SAJ
where PP ={Select-Sat, Select-First, etc.}.

Proof: To simulate [A,B],| and join, we need n(l), flow, | and & for which 
Select-Sat etc. is NP-complete.

Question:
Is some sublanguage of SAJ efficiently more expressive for Select-Sat than SD?

SD is better than SAJ because there exists 
a sublanguage of SD (-/SD) that is an efficient niche wrt SAJ
while SAJ does not have a sublanguage that is an
efficient niche wrt SD. We assume here that SD has bypassing
and multiple targets as in DJ and DAJ.


We should add a new language SXP that contains the essence
of XPath and see how our results carry over or not.

Could start with:

SD + [A.k.B] + [A,B [S]] where B is source of strategy S.
S must select at least one node.

We should add a datalog-based selector language SDL that uses
a logic program to express the pointcuts. Would have polynomial
time decision procedure. Is datalog powerful enough?

Also analyze:
SR ::= A | any | D1.D2 | D1||D2 | D1&&D2 | (D) | !D
SG ::= strategy graphs | D1 && D2 | (D) | !D