-
Notifications
You must be signed in to change notification settings - Fork 0
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
State Elimination as a Model Transformation Problem #36
Comments
This one looks pretty promising to me (rather simple but still not useless). As far as I understand, it is just a very basic and simple algorithm to be implemented with help of some GTR.
or
|
changed to search for 'wildcard' labels. // gtr for adding new calculated labels
PatternGraph gtrEliminate = new PatternGraph("eliminate state");
PatternNode p = new PatternNode();
PatternNode k = new PatternNode("!(#{newFinal} == 1 || #{newInitial} == 1)");
PatternNode q = new PatternNode();
gtrEliminate.addPatternNode(p, k, q);
/* CASE 1: there's just pk and kq */
p.addPatternEdge("==", "#{pk}", k);
k.addPatternEdge("==", "#{kq}", q);
p.addPatternEdge("+", "'(' + #{pk} + ')(' + #{kq} + ')'", q);
// /* CASE 2: there's just pq, pk and kq */
// p.addPatternEdge("==", "#{pk}", k);
// k.addPatternEdge("==", "#{kq}", q);
// p.addPatternEdge("-", "#{pq}", q);
// p.addPatternEdge("+", "'(' + #{pq} + ')+(' + #{pk} + ')(' + #{kq} + ')'", q);
//
// /* CASE 3: there's just pk, kk and kq */
// p.addPatternEdge("==", "#{pk}", k);
// k.addPatternEdge("==", "#{kq}", q);
// k.addPatternEdge("==", "#{kk}", k);
// p.addPatternEdge("+", "'(' + #{pk} + ')(' + #{kk} + ')*(' + #{kq} + ')'", q);
//
// /* CASE 4: there's pq, pk, kk and kq */
// p.addPatternEdge("==", "#{pk}", k);
// k.addPatternEdge("==", "#{kq}", q);
// k.addPatternEdge("==", "#{kk}", k);
// p.addPatternEdge("-", "#{pq}", q);
// p.addPatternEdge("+", "'(' + #{pq} + ')+(' + #{pk} + ')(' + #{kk} + ')*(' + #{kq} + ')'", q); So now you can look for an edge with label "#{a}". This will match any edge and store the actual label that was found in an expression evaluator in the match. When an edge is created those variables can be adressed, so a new label could then be "#{a} + ' ' + #{b}" for example (if the GTR actually specified to find matches on "#{a}" and "#{b}"). The evaluator has access to all wildcard edge labels and nothing else. A nice feature would be, to have access to all node's attributes and all edge-labels (wildcard or not), effectively just using a single evaluator with all data includes within the whole GTR. Though some syntax has to be established for that and a few other issues have to be worked out. For now (this TTC case), this is ok like it is, though. |
Now I also added a feature, where you can put multiple variable-binding into a single PatternEdge that's to be found. This will then search for multiple 'wildcard' edges between those nodes and set each bound variable to one of the edges that are found. If that PatternEdge is to be removed, then it will remove exactly the edges that were matched. So if you look for two 'wildcard' edges and they shall be removed, then any two edges will found and removed, but if there were like 5 edges between the nodes, then those 3 that weren't matched will stay and won't be removed. This solves the problem of YAGE not being able to find and merge multiple 'wildcard' edges between the same nodes. Here's an example: // gtr for merging multiple edges between the same two nodes:
PatternGraph gtrMerge = new PatternGraph("merge multiple labels between the same two nodes");
PatternNode a = new PatternNode();
PatternNode b = new PatternNode();
gtrMerge.addPatternNode(a, b);
a.addPatternEdge("-", "#{x}, #{y}", b);
a.addPatternEdge("+", "#{x} + '+' + #{y}", b); |
Yesterday, I added missing features fo this case. Today I'm trying to actually implement the case. I also adapted my algorithm a whole lot:
Step 2.3. will also consist of several GTR, covering all cases:
These are a lot of steps for something that surely could be done with many steps less, but this will solve the problem with nothing but using GTR - no single bit of additional code (except maybe for handling the looping through multiple nested lists of gtr - but that could be implemented as a standard feature, too). |
So I'm now using a crazy amount of 19 GTR - and I'm convinced, that it should work if the GTR are correct. For the first test file ( But my current result is that: Many of the parentheses are unnecessary, sure - but that's ok. The problem is, that the Either some of the GTR are faulty, or I need even more of them... |
I hope we can work out this issue today, so the little time that's left could be used to also implement those few changes for the probabilistic variant and finish the whole task. Time's running, though. Let's hope for the best. |
|
Running tests (with no further changes) in proper order
|
though the version that's using the Algorithm object doesn't work, yet
That's more like it!
For some reason I did totally unnecessary isomorphism checks in the previous version, where nothing but pattern matching should ever happen. Now it scales a whole lot better. Also I'm trying to implement an Algorithm entity that handles the steps and loops of GTR used in such an algorithm. This then could be serialized into a nice little file that's basically the solution to the whole case - and it could also potentially be edited graphically in the upcoming graphical editor. This would look like Scratch code or something - would be awesome, I think. |
runtime
|
@eicke123: Do we know SDMLib's runtime for the state elimination case? |
doesn't seem right though. this expression library ain't made for this either (gotta parse probabilities out of edge labels -> can't even parse to number and calculate within the expression library; could just extract the probability as a string or calculate with numbers -> no way to extract a string and parse it into a number without changing the expression library). on the other hand the paper doesn't describe quite right, how the probabilities are calculated, and it's somehow open to interpretation. as far as i understand you can always look at everything except star as an unary or binary concatenation and put a constant rate as probability to it. and with star you can just take the old value. so it then would be possible (but) pointless, to do it with just string operations. i was trying to do this. but the expression library keeps throwing some errors. i don't know if it's worth the hastle
State Elimination as a Model Transformation Problem
Resources:
Other cases:
YAGE branch for the case:
ttc-state
The text was updated successfully, but these errors were encountered: