Reference:
Kimmo Varpaaniemi. Minimizing the number of successor states in the stubborn set method. Fundamenta Informaticae (Annales Societatis Mathematicae Polonae, Series IV), 51(1–2):215–234, May 2002. IOS Press, Amsterdam, The Netherlands.
Abstract:
Combinatorial explosion which occurs in parallel compositions of LTSs can be alleviated by letting the stubborn set method construct onthefly a reduced LTS that is CFFD or CSPequivalent to the actual parallel composition. This article considers the problem of minimizing the number of successor states of a given state in the reduced LTS. The problem can be solved by constructing an and/orgraph with weighted vertices and by finding a set of vertices that satisfies a certain constraint such that no set of vertices satisfying the constraint has a smaller sum of weights. Without weights, the and/orgraph can be constructed in lowdegree polynomial time w.r.t. the length of the input of the problem. However, since actions can be nondeterministic and transitions can share target states, it is not known whether the weights are generally computable in polynomial time. Consequently, it is an open problem whether minimizing the number of successor states is as ``easy'' as minimizing the number of successor transitions.
Keywords:
LTSs, CFFDequivalence, CSPequivalence, stubborn sets, and/orgraphs
Suggested BibTeX entry:
@article{VarpaaniemiKimmoVrpFI2,
author = {Kimmo Varpaaniemi},
journal = {Fundamenta Informaticae (Annales Societatis Mathematicae Polonae, Series IV)},
month = {May},
note = {IOS Press, Amsterdam, The Netherlands},
number = {12},
pages = {215234},
title = {{M}inimizing the Number of Successor States in the Stubborn Set Method},
volume = {51},
year = {2002},
}
