| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:seeAlso
| |
| Description
| - Distributed bisimilarity is one of non-interleaving equivalences studied on concurrent systems; it refines the classical bisimilarity by taking also the spatial distribution of (sub)components into account. In the area of verification of infinite-state systems, one of the simplest (most basic) classes in the class of Basic Parallel Processes (BPP); here distributed is known to coincide with many other non-interleaving equivalences. While the classical (interleaving) bisimilarity on BPP is known to be PSPACE-complete, for distributed bisimilarity a polynomial time algorithm was shown by Lasota (2003). Lasota's algorithm is technically a bit complicated, and uses the algorithm by Hirshfeld, Jerrum, Moller (1996) for deciding bisimilarity on normed BPP as a subroutine. Lasota has not estimated the degree of the polynomial for his algorithm, and it is not an easy task to do. In this paper we show a direct and conceptually simpler algorithm, which allows to bound the complexity by O(n^3) (when startin
- Distributed bisimilarity is one of non-interleaving equivalences studied on concurrent systems; it refines the classical bisimilarity by taking also the spatial distribution of (sub)components into account. In the area of verification of infinite-state systems, one of the simplest (most basic) classes in the class of Basic Parallel Processes (BPP); here distributed is known to coincide with many other non-interleaving equivalences. While the classical (interleaving) bisimilarity on BPP is known to be PSPACE-complete, for distributed bisimilarity a polynomial time algorithm was shown by Lasota (2003). Lasota's algorithm is technically a bit complicated, and uses the algorithm by Hirshfeld, Jerrum, Moller (1996) for deciding bisimilarity on normed BPP as a subroutine. Lasota has not estimated the degree of the polynomial for his algorithm, and it is not an easy task to do. In this paper we show a direct and conceptually simpler algorithm, which allows to bound the complexity by O(n^3) (when startin (en)
- Distributed bisimilarity is one of non-interleaving equivalences studied on concurrent systems; it refines the classical bisimilarity by taking also the spatial distribution of (sub)components into account. In the area of verification of infinite-state systems, one of the simplest (most basic) classes in the class of Basic Parallel Processes (BPP); here distributed is known to coincide with many other non-interleaving equivalences. While the classical (interleaving) bisimilarity on BPP is known to be PSPACE-complete, for distributed bisimilarity a polynomial time algorithm was shown by Lasota (2003). Lasota's algorithm is technically a bit complicated, and uses the algorithm by Hirshfeld, Jerrum, Moller (1996) for deciding bisimilarity on normed BPP as a subroutine. Lasota has not estimated the degree of the polynomial for his algorithm, and it is not an easy task to do. In this paper we show a direct and conceptually simpler algorithm, which allows to bound the complexity by O(n^3) (when startin (cs)
|
| Title
| - On distributed bisimilarity over Basic Parallel Processes
- On distributed bisimilarity over Basic Parallel Processes (en)
- On distributed bisimilarity over Basic Parallel Processes (cs)
|
| skos:prefLabel
| - On distributed bisimilarity over Basic Parallel Processes
- On distributed bisimilarity over Basic Parallel Processes (en)
- On distributed bisimilarity over Basic Parallel Processes (cs)
|
| skos:notation
| - RIV/61989100:27240/05:00012177!RIV06-GA0-27240___
|
| http://linked.open...avai/riv/aktivita
| |
| http://linked.open...avai/riv/aktivity
| |
| http://linked.open...vai/riv/dodaniDat
| |
| http://linked.open...aciTvurceVysledku
| |
| http://linked.open.../riv/druhVysledku
| |
| http://linked.open...iv/duvernostUdaju
| |
| http://linked.open...titaPredkladatele
| |
| http://linked.open...dnocenehoVysledku
| |
| http://linked.open...ai/riv/idVysledku
| - RIV/61989100:27240/05:00012177
|
| http://linked.open...riv/jazykVysledku
| |
| http://linked.open.../riv/klicovaSlova
| - verification; equivalence checking; distributed bisimilarity; basic parallel processesverification; equivalence checking; distributed bisimilarity; basic parallel processesverification; equivalence checking; distributed bisimilarity; basic parallel ver (en)
|
| http://linked.open.../riv/klicoveSlovo
| |
| http://linked.open...i/riv/kodPristupu
| |
| http://linked.open...ontrolniKodProRIV
| |
| http://linked.open...i/riv/mistoVydani
| |
| http://linked.open...telVyzkumneZpravy
| |
| http://linked.open...in/vavai/riv/obor
| |
| http://linked.open...ichTvurcuVysledku
| |
| http://linked.open...cetTvurcuVysledku
| |
| http://linked.open...vavai/riv/projekt
| |
| http://linked.open...UplatneniVysledku
| |
| http://linked.open...iv/tvurceVysledku
| - Jančar, Petr
- Sawa, Zdeněk
|
| http://localhost/t...ganizacniJednotka
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)