The Complexity of Boolean State Separation (Technical Report)

Ronny Tredup, Evgeny Erofeev

For a Boolean type of nets $\tau$, a transition system $A$ is synthesizeable into a $\tau$-net $N$ if and only if distinct states of $A$ correspond to distinct markings of $N$, and $N$ p…