TCS / Research / Publications / Minimizing the Number of Successor States in the Stubborn Set Method
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Minimizing the Number of Successor States in the Stubborn Set Method

Reference:

Kimmo Varpaaniemi. Minimizing the number of successor states in the stubborn set method. In Ludwik Czaja, editor, Concurrency, Specification and Programming: Proceedings of the CS&P'2001 Workshop, Warsaw, Poland, 3–5 October 2001, pages 279–290. Zakład Graficzny UW, zam. 583/2001, Warsaw, Poland, 2001.

Abstract:

Combinatorial explosion which occurs in parallel compositions of LTSs can be alleviated by letting the stubborn set method construct on-the-fly a reduced LTS that is CFFD- or CSP-equivalent to the actual parallel composition. This paper 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/or-graph 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/or-graph can be constructed in low-degree 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, CFFD-equivalence, CSP-equivalence, stubborn sets, and/or-graphs

Suggested BibTeX entry:

@inproceedings{VarpaaniemiKimmo-Vrp01b,
    author = {Kimmo Varpaaniemi},
    booktitle = {{C}oncurrency, Specification and Programming: Proceedings of the {C}{S}\&{P}'2001 Workshop, {W}arsaw, {P}oland, 3--5 {O}ctober 2001},
    editor = {Ludwik Czaja},
    pages = {279--290},
    publisher = {Zak{\l}ad Graficzny UW, zam. 583/2001, Warsaw, Poland},
    title = {{M}inimizing the Number of Successor States in the Stubborn Set Method},
    year = {2001},
}

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.