Jump to: navigation, search



State coders

The reason for state coders

One of the challenges of design space exploration is to identify previously explored model states. Ignoring this challenge can lead the exploration to an infinite loop as it is trying to explore states already traversed, making it unable to find any (new) solution.

One way to address this problem is to create a state code (a string, an identifier) from the model, after every transformation rule application. In this way, the algorithm is able to check equality between the freshly explored state and the previously explored states, by simply comparing their state codes.

However, not only model states can be encoded but also the rule activations, which is necessary for certain exploration techniques. For example, a depth first search exploration strategy executes a rule activation a1 from state s1 and then backtracks (e.g. a global constraint was unsatisfied in the new state s2 or it was already traversed). When it checks the rule activations from s1 and it finds two activations, the strategy should know somehow which activation was tried previously, namely which activation is the a1 activation. Encoding the activations enables the algorithm to compare the activations and decide which was fired already.


To create custom state coder in VIATRA-DSE, you should implement the following interfaces (and methods):

  • IStateCoder
    • void init(Notifier): initializes the state coder on the given model.
    • Object createStateCode(): encodes the actual model state. The return value is an Object as only its .equals() and .hashCode() methods are used, but usually it is a String.
    • Object createActivationCode(IPatternMatch): encodes the given activation.
  • IStateCoderFactory (factory design pattern)
    • IStateCoder createStateCoder(): creates a state encoder.

An example implementation (BPMN example) can be found here:

VIATRA-DSE has a built-in domain independent state coder (to configure it, see this link), but is usually beneficial to create a custom domian specific implementation both for performance and debugging reasons.

Best practices for implementing a domain specific state coder

State encoding

  • Not every aspect of the model should be encoded, only the parts which will be modified by the transformation rules.
  • Use separators for different elements and brackets for relations, for example: host1{app1,app2},host2{app3}
  • Sort collections, as the state code should be independent from the order of the elements in a collection.
  • Use a StringBuilder.

Activation encoding

  • Activation codes don't have to be globally unique, but it should be unique for the actual state.
  • Use the String.intern() method before returning the activation code, it will reduce memory footprint.