Wyniki wyszukiwania - BazTech

1

An Operational Petri Net Semantics for A2CCS

Gorrieri R., Versari C.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 2

135-160

EN

A2CCS is a conservative extension of CCS, enriched with an operator of strong prefixing, enabling the modeling of atomic sequences and multi-party synchronization (realized as an atomic sequence of binary synchronizations); the classic dining philosophers problem is used to illustrate the approach. A step semantics for A2CCS is also presented directly as a labeled transition system. A safe Petri net semantics for this language is presented, following the approach of Degano, De Nicola, Montanari and Olderog. We prove that a process p and its associated net Net(p) are interleaving bisimilar (Theorem 5.1). Moreover, to support the claim that the intended concurrency is wellrepresented in the net, we also prove that a process p and its associated net Net(p) are step bisimilar (Theorem 5.2).

2

Towards Ambitious Approximation Algorithms in Stubborn Set Optimization

Varpaaniemi K.

Fundamenta Informaticae

|

2003

|

Vol. 54, nr 2,3

279-294

EN

This article continues research on the stubborn set method that constructs on-the-fly a reduced LTS that is CFFD-equivalent to the parallel composition of given LTSs. In particular, minimization of the number of successor states of a given state is reconsidered. The earlier suggested and/or-graph approach requires solving #P-complete counting problems in order to get the weights for the vertices of the and/or-graph. The ``branch-and-bound'' decision problem corresponding to the minimization of the sum of the computed weights is ``only'' NP-complete. Unfortunately, #P-complete counting does not seem easily avoidable in the general case because it is PP-complete to check whether a given stubborn set produces at most as many successor states as another given stubborn set. Instead of solving each of the subproblems, one could think of computing approximate solutions in such a way that the total effect of the approximations is a useful approximation itself.

3

Minimizing the Number of Successor States in the Stubborn Set Method

Varpaaniemi K.

Fundamenta Informaticae

|

2002

|

Vol. 51, nr 1,2

215-234

EN

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 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/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.

4

Comparing Refinements for Failure and Bisimulation Semantics

Eshuis R., Fokkinga M.M.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 4

297-321

EN

Refinement in bisimulation semantics is defined differently from refinement in failure semantics: in bisimulation semantics refinement is based on simulations between labelled transition systems, whereas in failure semantics refinement is based on inclusions between failure systems. There exist however pairs of refinements, for bisimulation and failure semantics respectively, that have almost the same properties. Furthermore, each refinement in bisimulation semantics implies its counterpart in failure semantics, and conversely each refinement in failure semantics implies its counterpart in bisimulation semantics defined on the canonical form of the compared processes.