Part of issue567, and to some extent follow-up of issue851.

Pull request: https://github.com/aibasel/downward/pull/11

Possible follow-up issue:
- rework EquivalenceRelation which can be the bottleneck of the merge-and-shrink computation in certain tasks

Merged.

We decided to go with v24. I merged the latest changes from main and re-ran experiments, also using sbMIASM as merge strategy combined with SCCs.

https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20-eval/issue927-v20-issue927-base-v4-issue927-v20-compare.html

The results are still very positive, although not as much any more as with v20, which was before we did some refactoring and changed the algorithm for applying label reductions: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20-eval/issue927-v20-issue927-base-v4-issue927-v20-compare.html

With that, we need to write a commit message and are ready to commit the changes of this issue.

How do we proceed? Merge v24?

There is probably more to be done here, but also it doesn't all have to be done in one commit.

In v25, we hoped to remedy the slowdown of v24 by only sorting label groups on demand, i.e., before removing labels from groups due to label reduction. Unfortunately, things only got a lot worse: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v25-eval/issue927-v25-issue927-v24-issue927-v25-compare.html

v22: Move the constructor of LocalLabelInfo to header again.
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v22-to-v24-eval/issue927-v22-to-v24-issue927-v21-issue927-v22-compare.html
restores (some of) the runtime performance

v23: I noticed that with the removal of LocalEquivalenceRelation, I (accidentally?) also removed the iterator for TransitionSystem, which resulted in *not* skipping inactive local labels (which do not represent any label anymore). v23 fixes this.
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v22-to-v24-eval/issue927-v22-to-v24-issue927-v22-issue927-v23-compare.html
slight decrease of M&S construction time

v24: Always have label groups sorted and when applying label reductions, remove reduced labels in batches instead of individually
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v22-to-v24-eval/issue927-v22-to-v24-issue927-v23-issue927-v24-compare.html
Qquite a notable increase of M&S construction time (and thus total time), also slight increase of memory. It seems that sorting is more expensive than what we save by repeated resizing of vectors.

Malte and I discussed the results and looked a bit at the code. The change that not only fixed the constructor using "move", but also moved it to the implementation file, should be partially reverted by moving the fixed version of it to the header file again. Otherwise, we continue with evaluating more changes.

After addressing all minor comments, refactoring the iterator class for TransitionSystem to use STL-based iterators and getting rid of a friend declaration in LocalLabelInfo, I tagged version v21 but stumbled over some performance changes: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v21-eval/issue927-v21-issue927-v20-issue927-v21-compare.html

Note that the constant increase in memory is due to a difference in compilation, probably the inclusion of CPLEX. I re-compiled v20 under the same conditions in the meantime and there is no such increase.

To track the difference in M&S construction time, I tagged more versions:
v20a: after minor refactoring: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20-to-v21-eval/issue927-v20-to-v21-issue927-v20-issue927-v20a-compare.html#summary - no differences
v20b: refactoring the iterator class: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20-to-v21-eval/issue927-v20-to-v21-issue927-v20a-issue927-v20b-compare.html - beneficial changes
v20c: getting rid of friend declaration: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20b-v20c-v21-eval/issue927-v20b-v20c-v21-issue927-v20b-issue927-v20c-compare.html
- slowed down computation. I really don't know why.
v21: using move in the move constructor https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20b-v20c-v21-eval/issue927-v20b-v20c-v21-issue927-v20c-issue927-v21-compare.html - another slowdown; no clue why

From my side, feel free to merge.

The debug experiments finished without errors: https://ai.dmi.unibas.ch/_experiments/ai/downward/issue927/data/issue927-v20-debug-eval/issue927-v20-debug-issue927-base-v4-issue927-v20-compare.html

Thanks a lot for the comments! I fixed all minor things where no discussion was necessary and replied to a few other comments where we should discuss. 

Regarding EquivalenceRelation, I fixed 1 and 3 (the removal of the latter was an oversight). I'm fine with not dealing with that class in more detail in this issue. I think that we simplified (and thereby improved) it already quite a bit now.

Regarding EquivalenceRelation:

1. It seems that the system #include can (and hence should) be moved from the header to the implementation file.
2. There are parts of the design that I find weird, but it looks like this weirdness was already previously present.
3. It seems that the refine method used to include a comment about its algorithmic complexity, and now this comment is gone. Is there a good reason for this? As a user of such a class, I'd generally like to know such things when they are not obvious.

More generally, I think the class looks in need of revision and also better documentation, especially as we want to keep treating it as a general tool (i.e., have it inside the algorithms directory). But this doesn't necessarily have to be part of this issue.

I cannot really review the class fully at the moment, but if you're happy to proceed without such a review, then we can proceed.

The experiments look good, and I'm done looking at the pull request except that I still need to look at equivalence_relation.{cc,h}.

I left mostly polishing comments that you can ignore for the most part if you prefer, apart from things like the typo and changelog entry. I'll have a look at the equivalence relation class later.

Interpretation of results: the computation of merge-and-shrink now is significantly faster and requires less memory, with very few exceptions only. This allows the atomic FTS to be computed in 34 more tasks than before. Total runtime is also reduced and a few more tasks can be solved.

For completeness, experiments comparing main against the latest version: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v20-issue927-base-v4-issue927-v20-compare.html

This issue is now ready for a final code review.

The main change was to replace LabelEquivalenceRelation, which stored locally equivalent labels in a list<int> and additionally stored an iterator into that list for fast removal during label reduction, by a simple vector<int> without storing an additional iterator. That greatly simplified the code and also made everything use less memory and run faster, except for label reductions in cases where the local label equivalence classes are huge. For example, in agricola-opt18, runtime of label reduction increases significantly because looking for just a few reduced labels in a large local label equivalence class takes very long time.

I re-ran the latest experiments (after merging from main; which is base-v4), using *no* time limit for the M&S computation, as this made it harder to see the impact of the change. Indeed, the results are a lot clearer now, clearly positive in almost all cases.

v15 (all local labels are made contiguous always): https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-base-v4-issue927-v15-compare.html
v16 (local labels are not contiguous and we reserve memory for the maximum number of possible labels): https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-base-v4-issue927-v16-compare.html
v17 (as v16, but without reserving memory): https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-base-v4-issue927-v17-compare.html

v15 vs v17: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-v15-issue927-v17-compare.html

As stated below, I think we should stick with v17 because making local labels contiguous doesn't have benefits and reserving very large amounts of memory has a clear negative impact.

v18 (store the number of active aka. non-reduced labels rather than computing them on demand): https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-v17-issue927-v18-compare.html
I'm still surprised that this has a slightly negative impact on time rather than on memory (for storing one additional int). 

v19 (use vector plus sort and unique rather than set into vector for computing transitions of reduced labels): https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-up-to-v19-issue927-v18-issue927-v19-compare.html

In v19, we use a vector to collect all transitions of a reduced labels and then use sort and unique. Previously, we used a set and turned this into a vector at the end. Definitely a positive impact: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v19-issue927-v18-issue927-v19-compare.html

v18 keeps track of the number of active (aka. non-reduced) labels in the Labels class rather than computing that number over and over again for each label reduction.

https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v18-issue927-v17-issue927-v18-compare.html

Results look somewhat mixed w.r.t.  Inspecting a few instances where the construction time of merge-and-shrink increases, this seems to be due to our insufficiently fine-grained time limit feature. Sometimes, the previous configuration would just finish a merge/label reduction slightly after 900s (the time limit for M&S), and the new configuration, being slightly faster, continues with the next iteration where label reduction takes a few minutes before the time limit is checked again and M&S computation is terminated. There are also cases where the M&S computation gets slightly slower - this can only be due to fluctuations on the grid. Overall, coverage is not affected and the changes in runtime scores are small so that we can keep the change.

I merged the latest main branch into this issue and re-ran experiments: base-v4 vs v15

https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-v15-v16-v17-issue927-base-v4-issue927-v15-compare.html

Everything looks good.

Further, I re-evaluated the difference of making all local labels contiguous (v15; introduced in v3) vs. possibly adding a new local label when applying label reduction. In version v16, the code was moved back to not making local labels contiguous, however, reserving memory for the maximum number of labels which is also the (theoretical) maximum number of local labels a transition system could have. This significantly lowers the number of cases where the construction of the atomic FTS succeeds: 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-v15-v16-v17-issue927-base-v4-issue927-v16-compare.html

In v17, I therefore evaluated the middle ground of not making local labels contiguous, but neither reserving memory, thus accepting a few reallocations when creating new local labels. This version is comparable with v15, slightly faster (expected), but no clear drawbacks: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-basev4-v15-v16-v17-issue927-base-v4-issue927-v17-compare.html

Since I don't see any direct benefits for making local labels contiguous, I would opt for the latest version which doesn't do this but which also doesn't (unnecessarily) large amounts of memory.

I need to double-check but if I remember correctly, then I discussed with Florian and Salomé that we wanted to try using bitsets for storing global labels and see if this helps reducing the bottle neck that label reduction can be in some domains. That would mean that the issue is waiting for me and not for you :)

Hi all, what's the status? Silvan, is this waiting for code review? If yes, can you find a reviewer? I'd also like to have a quick look before merging, but things will move much faster if I know someone else approved it already.

The experimental results look fine to me.

I'd err on the side of readable code.

In v14, I implemented a change suggested by Florian: before, TransitionSystem had three vectors to store information about local labels: local_label_to_global_labels, mapping each local label to the group of locally equivalent global labels it represents; local_label_to_cost, mapping each local label to the minimum cost of the represented global labels; local_label_to_transitions, mapping each local label to the set of transitions of the represented global labels. Now, there is a class LocalLabelInfo holding the group of represented global labels, the cost and the transitions, and TransitionSystem has a single vector storing LocalLabelInfo for each local label.

The results suggest that this refactoring is beneficial for the construction time of the heuristic, possibly due to improved cache efficiency (for a local label, its information is now stored together), however at the cost of an increase in memory consumption (I assume because of the custom class which serves as an intermediate wrapper):
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v14-issue927-v13-issue927-v14-compare.html

I'm not sure if we like this trade-off. The code, however, was improved through this refactoring because it avoids repetitive pieces of code when accessing different information for a given local label. Any thoughts on the results/the refactoring?

Results after some refactoring; no performance changes: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v13-issue927-v12e-issue927-v13-compare.html

> Apparently, the overhead of that method, which creates a HashState and calls
> feed, is too large when hashing plain data types like int. I think we should
> check if the planner uses HashMap/HashSet with int or similar data types at
> other places. Also, we should document that using the stl data structures
> directly is preferred in such cases.

I think this is not the first time we discover this. These hash functions are designed with container objects in mind and with an emphasis on distributing as uniformly as possible. They are certainly not cryptographic hash functions, but in the spectrum of "cheap computation vs. uniform distribution", they emphasize uniform distribution more than the typical library implementations.

What makes this even more complicated is that trivial hash functions like
    [](int i) { return i; }
that can be very problematic for distribution (for mod-based hash tables) can be excellent for cache locality in typical scenarios where we see many keys clustered close to each other.

We also have the dedicated IntHashSet type that can be useful in certain contexts, but I think it is primarily designed to be memory-efficient for very large hash tables, not to be fast for small ones. (It is used only by the state registry.)

The question is how best to document things like these. If we just mention this in hash.h, I am not sure we will see it when we need to.

It turns out that the culprit of the performance loss in v12e was not the simplification of EquivalenceRelation, but the switch from std::unordered_map to utils::HashMap. I got skeptical when "std::uint64_t get_hash64(const T &value)" showed up in a profile. Indeed, reverting this change in v12e fixes the performance loss:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12e-issue927-v12d-issue927-v12e-compare.html
and also mildly improves over 12c, although the scale of changes could be in the range of noise:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12e-issue927-v12c-issue927-v12e-compare.html

Apparently, the overhead of that method, which creates a HashState and calls feed, is too large when hashing plain data types like int. I think we should check if the planner uses HashMap/HashSet with int or similar data types at other places. Also, we should document that using the stl data structures directly is preferred in such cases.

Furthermore, when looking at a profile of the first task of parking-opt14-strips, we noticed that EquivalenceRelation::refine is responsible for 87% of the run-time of the first three merge-and-shrink iterations. It might be worth looking into completely reworking EquivalenceRelation in another issue. I added an item to the summary.

v12: only refactoring in comparison to v9-fix (reported in the previous comment):
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12-issue927-base-v3-issue927-v12-compare.html
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12-issue927-v9-fix-issue927-v12-compare.html
By now, I assume that changes in runtime scores of up to 2 can just be attributed to noise in the sense of code changes that should not impact the performance, but might affect memory layout or whatever else.

v12b: removes the class GlobalLabel (which only contained an int standing for the cost of the label) and GlobalLabels stores vector<int> label_costs directly instead of unique pointer to GlobalLabel:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12-issue927-v12-issue927-v12b-compare.html
If anything, I expected a positive impact because of one less layer of indirection and not using unique pointers. But the effect is "negative", in the same amount as v12 compared to v9-fix was positive even though this was pure refactoring.

v12c: add iterators for GlobalLabels which allows iterating over "valid" labels, which, however, is only used during the construction of the atomic FTS:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12-issue927-v12b-issue927-v12c-compare.html#summary
Basically no effect, was expected.

v12d: Florian and I greatly simplified the class EquivelanceRelation (in algorithms). It only works with ints now, only can be constructed as the universal equivalence relation, and no longer supports "unspecified elements". This allows using it with only valid labels, which should avoid having reduced labels as "unspecified elements" in the equivalence relation. 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v12-issue927-v12c-issue927-v12d-compare.html#summary
The results are bad and I don't know (yet) why. We moved previously templated methods to the cc file, maybe this has an effect. We'll need to investigate this further.

I noticed that the loop that erases old labels from transition systems when applying label reductions unnecessarily considered all labels of a label group instead of stopping after erasing the label. This significantly improves the performance:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v9-fix-issue927-base-v3-issue927-v9-fix-compare.html
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v9-fix-issue927-v9-issue927-v9-fix-compare.html

After merging the latest changes from main (v9), the changes in this issue compare less favourably to main (base-v3) than previously, although overall still positively: 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v9-issue927-base-v3-issue927-v9-compare.html
(successful constructions for more tasks, less memory consumption, often faster, sometimes significantly slower, however).

Compared to the previous version (v8), the merge-and-shrink construction slows down a bit (ms_construction_time, score_ms_construction_time): 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v9-vs-v8-issue927-v8-issue927-v9-compare.html
I don't really understand why, as all changes between v8 and v9 are due to changes in main. 

I therefore also compared the two main revisions against each other: 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-base-v2-vs-v3-issue927-base-v2-issue927-base-v3-compare.html
The results of this comparison are very surprising to me because I don't know what could cause this difference. The diff between the two versions only makes cosmetic changes in M&S. The major things we changed in Fast Downward, like the state representation, shouldn't affect the construction of M&S heuristics.

Since the latest version still uses much less memory and only becomes significantly slower in a few domains, I think we can accept that strange performance change. (We cannot do something about the weird change due to main anyway.) Instead, when discussing this issue with Florian and Salomé, we thought it would be a good idea to look at the problematic domains, in particular, agricola, where construction time can be doubled compared to main. 

I did that and found that applying label reductions to transition systems is the culprit: where we previously stored , for each label, the id of its "local label group" and an iterator into that group (a list), we now only store the group id and need to search for the label in its group (now a vector) for removing it. I attempted to improve the situation using set (v10) or HashSet (v11). While this helped in the previously problematic case agricola (to some extent, only), it significantly slowed down the computation in other domains: 
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v10-v11-issue927-base-v3-issue927-v10-compare.html
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v10-v11-issue927-base-v3-issue927-v11-compare.html
So I think using vectors (v9) is the right direction and we should discuss if we can live with slower construction times in a few domains. Alternatively, we could (again) store an iterator into a label group for each label, but I didn't like that previous part of the code too much, so I would rather try to avoid it.

Florian, Salomé and I also discussed if reverting the change that all "local label ids" (i.e., the label groups) are stored contiguously (added in v3). This might trade some memory usage for runtime, although back then we didn't observe too much penalty for enforcing the contiguous storing of label groups.

Sounds good to me. The cost partitioning thing is not a blocker or an overriding concern, just a thing I suggest we keep in mind. It is a goal to open these things up a bit more given how much the BDE project focuses on this aspect.

The new implementation would make implementing optimal cost partitioning easier. For SCP, it would probably not help but could make it more complicated as we need to compute the remaining costs of the actual labels, not some labels "local" to a transition system.

Nevertheless, I'm not sure if this consideration (regarding cost partitioning) should be a central concern in this issue because I think that the change in this issue makes the code related to transition systems easier in general. But of course, getting someone else to review this first would be good. I hoped Alvaro could have a look into this since he also would like to see this change, I think, but he might be too busy in Denmark now. I'll ask Florian/Thomas if they can find some time.

Hi Silvan, to move this forward, it would be good if someone else could look at the  code first.

This is currently an implementation detail of merge-and-shrink, but it may become more visible when we add more cost partitioning or operator-counting constraint features. Does the new representation help with that, hinder that, or is it neutral? Would it make sense to get someone else who was included in cost partitioning and merge-and-shrink to review?

I evaluated the current implementation (with all improvements together) after merging from default:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v8-issue927-base-v2-issue927-v8-compare.html

I looked into this again today but couldn't actually find anything else I would like to do in this issue. So now, with an unnecessary delay of 8 months :-), I'd like to ask for a review. Or, as a first step, for ideas of how to simplify reviewing in this case. The pull request list the following changes:

+0 -59
M src/search/algorithms/equivalence_relation.cc
+64 -1
M src/search/algorithms/equivalence_relation.h
+3 -7
M src/search/merge_and_shrink/distances.cc
+8 -9
M src/search/merge_and_shrink/factored_transition_system.cc
+5 -5
M src/search/merge_and_shrink/factored_transition_system.h
+69 -47
M src/search/merge_and_shrink/fts_factory.cc
+72 -0
A src/search/merge_and_shrink/global_labels.cc
+47 -0
A src/search/merge_and_shrink/global_labels.h
+0 -134
D src/search/merge_and_shrink/label_equivalence_relation.cc
+0 -122
D src/search/merge_and_shrink/label_equivalence_relation.h
+3 -4
M src/search/merge_and_shrink/label_reduction.cc
+0 -62
D src/search/merge_and_shrink/labels.cc
+0 -46
D src/search/merge_and_shrink/labels.h
+4 -1
M src/search/merge_and_shrink/merge_and_shrink_algorithm.cc
+1 -2
M src/search/merge_and_shrink/merge_scoring_function_dfp.cc
+1 -3
M src/search/merge_and_shrink/shrink_bisimulation.cc
+270 -129
M src/search/merge_and_shrink/transition_system.cc
+50 -52
M src/search/merge_and_shrink/transition_system.h 

The files labels.* and global_labels.* should be reviewed next to each other (the new class is a bit simpler) and some of the logic of what used to be in label_equivalence_relation is now part of transition_system (and fts_factory, which creates transition systems), however also modified as described below. The change to equivalence_relation is due to making refine being a templated method (therefore in the header). The rest are only small changes required to adapt to the changed interface of transition systems.

Added link to meta issue567.

I just found that issue851 can be seen as a predecessor of this issue. To quote its summary: 
Possible further improvements: do not store information for all labels in each
transition system, but only for the relevant ones. This requires either a
concept of local label numbers and a mapping between global and local labels,
or using hash maps instead of vectors whenever storing information per label,
leaving out irrelevant labels.

I'll you know, yes.

In step 3, after reducing labels and shrinking, we always make sure that there are no gaps in vector<vector<Transition>>, i.e., we have a contiguous "numbering" of "local labels". 

The effect can be both negative or positive, especially in large instances, sometimes reducing memory and speed, sometimes trading the former for the latter: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v3-issue927-v2-issue927-v3-compare.html

Hi Silvan, I'm curious, but lack the time, so I'll stay quiet for the time being.  But sounds exciting! Let us know when something needs to be done in terms of reviewing etc.

In a small second step, I did some more minor refactoring to avoid having a global label mapping from global to local labels, but instead having it individually for each transition system. No large changes: https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v2-issue927-v1-issue927-v2-compare.html

The results of the first step are in. The only change is to replace LabelEquivalenceRelation (which uses a hash map to map global labels to local label group ids and a list for said groups) by a combination of global to local and local to global label mappings in each transition system, only using vectors.

https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue927-v1-issue927-base-issue927-v1-compare.html

There is a clear positive performance trend and we can finish the computation of atomic FTS and the whole heuristic in more cases than before. (The attributes ms_out_of_memory and ms_out_of_time were not correctly parsed as of this writing; the report will be updated tomorrow.)

Here's a pull request if someone is already curious: https://bitbucket.org/SilvanS/fd-dev/pull-requests/54/issue927/diff

In a recent discussion with Álvaro, we came to the conclusion that it would be worth trying to change the representation of transition systems. In particular, getting rid of LabelEquivalenceRelation and its underlying data structure of using a hash map from labels to local label group ids, and using lists for label groups. Using the notion of "local labels" and vector<int> to store both a mapping from "global" to local labels and vice versa could not only help simplify the code greatly, but also potentially improve performance.

In a first step, we will replace LabelEquivalenceRelation by appropriate mappings (vector<int>) as just described. Later, we could also try to always keep local and/or global label numbers contiguous and thereby get rid of the need for testing if a global label number is valid or not (because it has been reduced). In principle, we could also attempt the same thing for transition systems in factored transition systems. Finally, what is up for debate is whether we want to not store transitions of irrelevant labels, like it was the case years ago before the introduction of generalized label reduction.