Closing this one; please refer to the continuation in meta issue567 if interested.

I have closed issue520 and changed the title of issue561 to reflect that it is
now mainly about splitting TransitionSystem into multiple parts.

> So, do you want to have a new issue, with issue520 (or better: taking apart
> TransitionSystem) and the two other comments being tackled there? I am quite
> indifferent regarding this question.

Yes, I think it would be good to add a new issue. I expect that the current code
review will lead to a number of additional changes, and it would be nice if this
one didn't become unmanageable long. Can you take care of the new issue? (It's
of course enough to do this tomorrow or later.)

As soon as we decided on how to handle issue520 (original issue for splitting
off TransitionSystem into several parts), there is only issue415 and issue561
open. There are two more comments on how to further improve things, mentioned in
msg4230. I think that also without the last two comments being addressed, this
meta issue could well be closed, on the other hand, the original list of action
items also includes issue520. But, thinking that there may be more issues coming
up from further code review, we could also use a fresh meta issue. So, do you
want to have a new issue, with issue520 (or better: taking apart
TransitionSystem) and the two other comments being tackled there? I am quite
indifferent regarding this question.

Most of the items here have been done, and I find it difficult to keep track of
what is still *not* done due to the lengthy discussions etc. How about we close
this one and open a new meta issue "M&S refactoring part 2: meta issue" (or
similar) so that we have a clean slate w.r.t. comments?

See also issue561.

Ok, so let's leave issue415 (memory management) open until you find the time for
a code review (maybe at the next sprint?). I think that Florian was also
interested in issue415.

I'll try to address the other two items soon, i.e. improving the complexity of
compuation of local equivalence relations and adding a max time parameter.

Your choice! My recommendation is to do the memory management at the same time
as a general code review, because good memory management generally requires
rethinking all data structures and requires a good global overview of
everything. (This may mean that it could be preferable to do the other things
first, but please decide this based on your own preferences.)

Item 8 has been resolved with issue531.

We now have finished the "refactoring" part of this meta issue, but there are
other efficiency improvements on our list, such as memory management (issue415),
improving the method "compute_locally_equivalent_labels" by sorting (not sure if
transitions are not sorted anyway already or if, with the grouped
labels/transitions, sorting all transitions is possible at all), and adding a
max_time parameter similar as in iPDB.

(I left out some ideas on how to improve label reduction or include another
shrink strategy as these could be subject of future research.)

How do we proceed next? Do we want to tackle the memory management and try the
other two improvements also as part of this meta issue?

Item 9 has been resolved with issue530.

I'd also like to call item 3 resolved, because I don't see the need for
rearranging the main merge-and-shrink loop anymore, since we have transition
systems in a valid state always (no need to compute distances or normalize).
Label reduction still happens "manually", and even at different steps of the
computation, but issue522 has shown that this is useful.

item 7 has been resolved with issue522.

With item 10 being deferred, the remaining action items are:
3, although with valid states of transition systems, not a lot should be done there
7, 8, 9

Álvaro, as you suggested to separate out abstractions from transition systems
(msg388), I wonder if you had a specific design in mind. I recently created
issue520 for this task, but I am not quite sure what the goal of this separation
would be, because only a few things could be factored out of the current
TransitionSystem class from my point of view (i.e. only the lookup tables, but
then again, we would need to keep a distances table for the final abstraction).
I would be happy if you could elaborate a bit what you have thought of (please
do so in issue502).

item2 has been addressed in some of the earlier issues already.

issue492 has been resolved, and so item1 is fully finished now.

Remaining actions items:
2, 3, 7, 8, 9, 10

Results for the latest version (V7):
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-12-14-issue432-v7-abs.html

issue500 changed the way normalize works; it now treats every label separately.
Performance increased a lot.

Item 5 can be extended to the following (also from the "other" list with "TODOs
for later"):

5. LabelReducer: the caching of local equivalence relations of labels could be
  stored in the abstractions rather than the label reducer
  - To reduce memory, we might combine the representation of the
  transitions of locally equivalent labels. That is, if label1 and
  label2 have the same transitions, don't store "label1: transition1,
  ...; label2: transition1, ...", but instead store "{label1, label2}:
  transition1, ...".
  - Labels: split method reduce into several parts.

Note that item 5 and the "maybe" part of item 1 are handled in issue492.

This is on my list indeed, but we put it as "after the refactoring, efficiency
improvements". There is also another item which should belong to the refactoring:

9. Replace all the estimated memory stuff with actual memory
  measurements (or maybe better for now: add actual memory
  measurements)?
  The "peak_memory" stuff should probably be revised, maybe using actual memory
  usage now that we have this facility. (That measures *globally* used memory of
  course, but if we compute the delta before and after M&S construction, this
  should give us the information we want, I think.)

10. Split the representation of the abstraction function and
  heuristic from the transition systems so that we can throw away the
  transition systems after constructing them?

Hi Álvaro, I agree, and I thought this was already on the list, but it doesn't
seem to be. Silvan, do you remember discussing this? I wonder why we didn't
include it in the list.

Just a suggestion. Instead of just renaming "abstraction" into 
"transition_system", you could keep two different classes:
Abstraction represents the mapping from states to abstract states.
TransitionSystem represents a Labeled Transition System.

The distinction makes sense: one can define an abstraction without generating 
the corresponding LTS (like when the LTS is deleted after finishing the M&S 
process) and it should be possible to apply algorithms like bfs, dijkstra or 
bisimulation for any explicitly represented transition system, no matter 
whether it represents a M&S abstraction or not.

In general, the separation is quite easy. All the methods in the current class 
can be easily assigned to just one of those classes.

Item 6 has been resolved with issue490.

This is the current baseline:
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-10-16-issue432-v6-abs.html

Item 1 is done (without the maybe part) with issue477.

Item 4 has been resolved with issue 487.

Item 1 is currently (partly) tackled in issue477 (without the "maybe" part).

Action items:

1. Reconsider what we understand by "normalized", e.g. define the notion of a
  "valid state" of an abstraction as:
  - Transitions are sorted (by labels, by states) and there are no
    duplicates.
  - All labels are incorporated
  - Distances are computed and stored
  - Maybe: locally equivalent labels are computed and stored (we then could
    store the transitions for locally equivalent labels only once. We could
    even consider dropping '(ir)relevant labels' and making self loops
    explicit in this case.

2. Get rid of unused labels rather than having a tree-like structure for the set
  of all labels. This should be possible under the assumption that abstractions
  are always in a valid state.

3. Some thoughts on the order in which things could be done in the merge-and-
  shrink main loop:
  - build atomic abstractions
  - compute distances
  - apply label reduction
  - main loop:
    - choose two abstractions
    - shrink (make sure state is valid!)
    - merge
    - compute distances
    - apply label reduction

  where apply label reduction means to determine combinable labels, to combine
  labels and to apply the label mapping in all abstractions (valid state!)

4. Abstraction::apply_abstraction: possibly consider the special case that
  nothing is actually being shrunk and then leave the method.

5. LabelReducer: the caching of local equivalence relations of labels could be
  stored in the abstractions rather than the label reducer

6. LabelReducer could be integrated (back) into Labels after we got rid of the
  old label reduction method. There is a strong inter depedence between both
  classes, as the label reducer creates new labels and Labels should handle
  such operations.

7. Shrink classes:
  - Does ShrinkStrategy::shrink_before_merge need to check if the new
    target size of an abstraction differs from the current size? check
    if this test is performed via "must_shrink" in all implementations
    of shrink strategies. If yes, then the method does not differ
    from ShrinkBisimulation:shrink_before_merge.
    As a consequence of having only one shrink_before_merge in the base
    class, we could make "compute shrink sizes" private. It should be
    clear however that every shrink strategy is responsible to decide
    on their own if they need/want to shrink or not.
  - shrink(): why is the parameter called threshold and not target?
    bisimulation renames threshold to target and uses its own threshold
    parameter, which has a different meaning.
  - Die Option threshold gibt es nur für shrink_bisimulation:
    Ah, OK. Das könnte man evtl. später mal ändern, weil das gar nicht so
    viel mit der Shrink-Strategie zu tun hat und mehr damit, wann und mit
    welchen Parametern die Shrink-Strategie aufgerufen wird. Aber das ist
    jetzt erst mal wurscht.

8. Meta-point: Go through M&S code comments to find TODOs, HACKs etc.

issue474 (renaming) and issue483 (pruning of irrelevant states does not use
shrinking strategy) have been merged.

Finally, we have new "baseline" results after merging the previously mentioned
issues.

http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-26-issue432-v2-abs.html

(We lose one coverage and gain one compared to the baseline results; so
everything is as expected.)

Issue477 is the next step (and will use those results as a reference).

issue475 and issue473 have been merged.

Yes, they do. Okay, I'll add the tag.

Thanks! Can we add a tag for "ee5a344e887b" for future experiments, e.g.
issue432-base? Do the baseline results look comparable to what we would expect
from the AAAI 2014 paper?

I'll comment on the other experiments in the respective issues.

Baseline results:
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue432-baseline-abs.html

Results for issue475:
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-23-issue475-baseline-v1-cggl-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-23-issue475-baseline-v1-dfp-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-23-issue475-baseline-v1-rl-comp.html

In some cases, shrinking all atomic transition systems with a perfect
bisimulation seems to be reasonable (increased initial h-value).

issue473-v1: Here we moved the computation of is_unit_cost from Heuristic to
TransitionSystem. It is being computed in the constructor of TransitionSystem,
and hence for every transition system ever generated.
Results
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v1-cggl-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v1-dfp-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v1-rl-comp.html

Memory is changing a lot, as usual with even small changes in the m&s framework,
but for the rest, the values seem fine to me.

issue473-v2: Computation of is_unit_cost even further "down" to computation of
distances, hence being computed again many times. I just realized I did not
restrict the computation to relevant labels. Will do so in a third version.
Results:
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v2-cggl-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v2-dfp-comp.html
http://ai.cs.unibas.ch/_tmp_files/sieverss/2014-09-24-issue473-baseline-v2-rl-comp.html

The picture is the same as for v1, some memory fluctuations, but the rest seems ok.

We discussed a few small changes that will be dealt with in separate issues:
- remove old label reduction (issue473)
- rename classes, variables etc in the code to fit papers (issue474)
- remove the "shrink_atomic" block before the m&s main loop (issue475)

For improving and evaluating the construction time of merge and shrink
heuristics, satellite could be a good domain, due to previously observed large
differences in construction times.

This issue is intended as a meta issue, containing general discussion about a
large set of changes we intend to pursue after the new label-reduction of the
paper "Generalized Label Reduction for Merge-and-Shrink Heuristics" has been
integrated.