About: Complexity of checking bisimilarity between sequential and parallel processes

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Complexity of checking bisimilarity between sequential and parallel processes Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://link.springer.com/chapter/10.1007%2F978-3-642-40313-2_28
Description	Decidability of bisimilarity for Process Algebra (PA) processes, arising by mixing sequential and parallel composition, is a long-standing open problem. The known results for subclasses contain the decidability of bisimilarity between basic sequential (i.e. BPA) processes and basic parallel processes (BPP). Here we revisit this subcase and derive an exponential-time upper bound. Moreover, we show that the problem if a given basic parallel process is inherently sequential, i.e. bisimilar with an unspecified BPA process, is PSPACE-complete. We also introduce a model of one-counter automata, with no zero tests but with counter resets, that capture the behaviour of processes in the intersection of BPA and BPP. Decidability of bisimilarity for Process Algebra (PA) processes, arising by mixing sequential and parallel composition, is a long-standing open problem. The known results for subclasses contain the decidability of bisimilarity between basic sequential (i.e. BPA) processes and basic parallel processes (BPP). Here we revisit this subcase and derive an exponential-time upper bound. Moreover, we show that the problem if a given basic parallel process is inherently sequential, i.e. bisimilar with an unspecified BPA process, is PSPACE-complete. We also introduce a model of one-counter automata, with no zero tests but with counter resets, that capture the behaviour of processes in the intersection of BPA and BPP. (en)
Title	Complexity of checking bisimilarity between sequential and parallel processes Complexity of checking bisimilarity between sequential and parallel processes (en)
skos:prefLabel	Complexity of checking bisimilarity between sequential and parallel processes Complexity of checking bisimilarity between sequential and parallel processes (en)
skos:notation	RIV/61989100:27240/13:86088843!RIV14-GA0-27240___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GAP202/11/0340)
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Sawa, Zdeněk Kot, Martin Jančar, Petr
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky
http://linked.open...dnocenehoVysledku	66484
http://linked.open...ai/riv/idVysledku	RIV/61989100:27240/13:86088843
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Upper Bound; PSPACE-complete; Process algebras; Parallel process; Parallel composition; BPA-processes; Bisimilarity; Basic parallel process (en)
http://linked.open.../riv/klicoveSlovo	BPA-processes Basic parallel process Bisimilarity PSPACE-complete Parallel composition Parallel process Process algebras Upper Bound
http://linked.open...ontrolniKodProRIV	[5D0E5FD8B270]
http://linked.open...v/mistoKonaniAkce	Klosterneuburg
http://linked.open...i/riv/mistoVydani	London
http://linked.open...i/riv/nazevZdroje	Lecture Notes in Computer Science. Volume 8087
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Modelling and verification of parallel systems
http://linked.open...UplatneniVysledku	2013
http://linked.open...iv/tvurceVysledku	Kot, Martin Jančar, Petr Czerwiński, Wojciech Sawa, Zdeněk
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2013-08-26 (xsd:date)
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-40313-2_28
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-40312-5
http://localhost/t...ganizacniJednotka	27240

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software