=Paper=
{{Paper
|id=Vol-2026/paper11
|storemode=property
|title=The SDMLib Solution to the TTC 2017 State Elimination Case
|pdfUrl=https://ceur-ws.org/Vol-2026/paper11.pdf
|volume=Vol-2026
|authors=Alexander Weidt,Albert Zündorf
|dblpUrl=https://dblp.org/rec/conf/staf/WeidtZ17
}}
==The SDMLib Solution to the TTC 2017 State Elimination Case==
https://ceur-ws.org/Vol-2026/paper11.pdf
The SDMLib Solution to the
TTC 2017 State Elimination Case
Alexander Weidt Albert Zündorf
Kassel University Kassel University
alexander.weidt@uni-kassel.de zuendorf@uni-kassel.de
1 Introduction
The Transformation Tool Contest 2017 State Elimination Case [SECase] asks for the reduction of a Finite State
Automaton into an equivalent regular expression. Basically, one replaces states with transitions that combine
the regular expressions attached to incomming and outgoing transitions of the removed state. This paper shows
the SDMLib [SDMLib] solution to this case.
2 The rules
At first, the example automaton has to be normalized: The automaton must have exactly one inital state and
exactly one final state.
Figure 1: Adding single intial state
Figure 1 shows in graphical notation the SDMLib transformation rule that adds a new initial state to the
current automaton and connects this new state to all previous initial states with empty transitions.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Garcia-Dominguez, F. Krikava and G. Hinkel (eds.): Proceedings of the 10th Transformation Tool Contest, Marburg, Germany,
21-07-2017, published at http://ceur-ws.org
Transformation uniformInitial() starts by matching the pattern object graph to the TransitionGraph
object passed as parameter. Next, pattern object newI creates a new initial state. Then the sub-pattern rendered
within two stacked boxes is executed. The pattern object oldI searches for old initial State objects attached to
our TransitionGraph via a states link and with an isInital attribute equal to true. The <>
sterotype attached to the sub-pattern shown in Figure 1 causes the sub-pattern to be executed for each match
of oldI. Thus, for each old initial state a new Transition t with empty label is created. The new transition
connects the new initial state newI and the current old initial state. In addition, the isInitial attribute of
oldI is set to false.
We use a similar rule called uniformFinal() to introduce a single final state into the current automaton.
The case description also proposes to add theta transitions between all states that are not yet connected via a
transition. Then the reduction algorithm is save to assume that each pair of states is connected via a transition.
Similarly, multiple transitions between two states are combined into a single transition. This reduces the number
of case distinctions within the algorithm but increases the runtime. Thus, the SDMLib approach does not
perform these normalization steps but deals with these cases in its transformation rules.
Figure 2: Eliminate States
Figure2 shows our eliminateStates() transformation. Again we start with a pattern object graph that
matches the root of our finite automaton, passed as parameter. Next we look up State k, the state that shall be
replaced by transitions. State k shall neither be isFinal nor isInitial. Then, the sub-pattern <> looks up a State p that has a Transition pk going to State k and a State q that is reached from State
k via Transition kq. The sub-pattern <> is iterated, that means it is executed for all possible
matches. For each match, we call the pseudo path expression p.getOrCreatePQ(q). This operation tries to find
an existing Transition pq that connects the States p and q. The path expression creates such a Transition,
otherwise. Operation setLabel(pq, pk, kq, kk) generates a label for transition pq computed as pq.label +
pk.label kk.label* kq.label. The cases that pq.label is empty or that kk is null or that kk.label is empty
are handled, specifically. Once all matches of sub-pattern allmatches 2 are handled, sub-pattern allmatches
3 and allmatches 4 remove all old Transitions leading to or leaving State k, respectively. Finally, State k
itself is destroyed. The whole top level pattern is iterated itself through the stereotype <>. Thus,
transformation eliminateStates eliminates all states except the unique initial and final states introduced at
the beginning. These initial and final states are then connected by exactly one Transition and this Transition
has a regular expression as label that is equivalent to the original finite automaton.
3 Results
Figure 3 shows some measurements for our solution. We have executed the transformation on a laptop with
about 1.6 Ghz. Intel I5 processor giving the Java process 6 GB heap space. We noticed that the evaluation of the
regular expression uses a lot of time, thus we show our results with and without the time used for the evaluation
of the resulting regular expression. We compare our results with the JFLAP algorithm times reported in the
call for solution. We are waiting for the results of the other teams.
SDMlib mit Evaluation SDMlib ohne Evaluation JFLAP
leader3 2 0.0385514360 0.052127528 0.09
leader4 2 0.0866275960 0.081792921 0.14
leader3 3 0.0993657960 0.063173148 0.49
leader5 2 1.1262002710 0.239402017 3.46
leader3 4 0.1605883720 0.098499445 4.37
leader3 5 0.5394560420 0.294551276 58.6
leader4 3 35.3694409170 7.921832035 57.78
leader6 2 24.6645100420 3.029549227 143.12
leader3 6 0.9771501780 0.771568491 461.64
leader4 4 8452.815857866 too big for memory timeout
Figure 3: Execution Times (in seconds)
Overall, the solution was quite straight forward although our state elimination transformation needs quite a
number of sub-pattern and we use some helper methods to handle different cases, uniformly.
References
[SDMLib] SDMLib - Story Driven Modeling Library www.sdmlib.org May, 2017.
[SECase] Sinem Getir, Duc Anh Vu, Francois Peverali, and Timo Kehrer State Elimination as Model Transfor-
mation Problem www.transformation-tool-contest.eu/TTC 2017 paper 4.pdf May, 2017.