About: Refining Undecidability Border of Weak Bisimilarity.

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

About: Refining Undecidability Border of Weak Bisimilarity. 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
Description	Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question for basic process algebras (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system. Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question for basic process algebras (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system. (en)
Title	Refining Undecidability Border of Weak Bisimilarity. Refining Undecidability Border of Weak Bisimilarity. (en)
skos:prefLabel	Refining Undecidability Border of Weak Bisimilarity. Refining Undecidability Border of Weak Bisimilarity. (en)
skos:notation	RIV/00216224:14330/06:00015292!RIV10-GA0-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1ET408050503), P(1M0545), P(GD102/05/H050), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Řehák, Vojtěch Strejček, Jan Křetínský, Mojmír
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	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	496824
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/06:00015292
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	process rewrite systems; state extension; infinite-state; decidability; weak bisimilarity (en)
http://linked.open.../riv/klicoveSlovo	infinite-state process rewrite systems decidability weak bisimilarity state extension
http://linked.open...ontrolniKodProRIV	[C9BCAED1B586]
http://linked.open...v/mistoKonaniAkce	San Francisco, USA
http://linked.open...i/riv/mistoVydani	Amsterdam, The Netherlands
http://linked.open...i/riv/nazevZdroje	Proceedings of the 7th International Workshop on Verification of Infinite-State Systems (INFINITY'05)
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems Techniques for automatic verification and validation of software and hardware systems
http://linked.open...UplatneniVysledku	2006
http://linked.open...iv/tvurceVysledku	Řehák, Vojtěch Strejček, Jan Křetínský, Mojmír
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2005-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	1571-0661
number of pages	20 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Elsevier Science
http://localhost/t...ganizacniJednotka	14330

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, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software