About: Why is Simulation Harder Than Bisimulation?

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

About: Why is Simulation Harder Than Bisimulation? 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	Why is deciding simulation preorder (and simulation equivalence) computationally harder than deciding bisimulation equivalence on almost all known classes of processes? We try to answer this question by describing two general methods that can be used to construct direct one-to-one polynomial-time reductions from bisimulation equivalence to simulation preorder (and simulation equivalence). These methods can be applied to many classes of finitely generated transition systems, provided that they satisfy certain abstractly formulated conditions. Roughly speaking, our first method works for all classes of systems that can test for `non-enabledness' of actions, while our second method works for all classes of systems that are closed under synchronization. Why is deciding simulation preorder (and simulation equivalence) computationally harder than deciding bisimulation equivalence on almost all known classes of processes? We try to answer this question by describing two general methods that can be used to construct direct one-to-one polynomial-time reductions from bisimulation equivalence to simulation preorder (and simulation equivalence). These methods can be applied to many classes of finitely generated transition systems, provided that they satisfy certain abstractly formulated conditions. Roughly speaking, our first method works for all classes of systems that can test for `non-enabledness' of actions, while our second method works for all classes of systems that are closed under synchronization. (en) Why is deciding simulation preorder (and simulation equivalence) computationally harder than deciding bisimulation equivalence on almost all known classes of processes? We try to answer this question by describing two general methods that can be used to construct direct one-to-one polynomial-time reductions from bisimulation equivalence to simulation preorder (and simulation equivalence). These methods can be applied to many classes of finitely generated transition systems, provided that they satisfy certain abstractly formulated conditions. Roughly speaking, our first method works for all classes of systems that can test for `non-enabledness' of actions, while our second method works for all classes of systems that are closed under synchronization. (cs)
Title	Why is Simulation Harder Than Bisimulation? Why is Simulation Harder Than Bisimulation? (en) Why is Simulation Harder Than Bisimulation? (cs)
skos:prefLabel	Why is Simulation Harder Than Bisimulation? Why is Simulation Harder Than Bisimulation? (en) Why is Simulation Harder Than Bisimulation? (cs)
skos:notation	RIV/00216224:14330/02:00006376!RIV08-MSM-14330___
http://linked.open.../vavai/riv/strany	594
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/00/0400), Z(MSM 143300001)
http://linked.open...vai/riv/dodaniDat	2008
http://linked.open...aciTvurceVysledku	Kučera, Antonín
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	670765
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/02:00006376
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	verification; concurrency; weak bisimilarity; infinite-state systems (en)
http://linked.open.../riv/klicoveSlovo	verification concurrency infinite-state systems weak bisimilarity
http://linked.open...ontrolniKodProRIV	[81C6EC98D2B8]
http://linked.open...v/mistoKonaniAkce	August 20-23, 2002, Brno, Czech Republic
http://linked.open...i/riv/mistoVydani	Berlin
http://linked.open...i/riv/nazevZdroje	Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)
http://linked.open...in/vavai/riv/obor	JC
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Infinite state concurrent systems - models and verification
http://linked.open...UplatneniVysledku	2002
http://linked.open...iv/tvurceVysledku	Kučera, Antonín Mayr, Richard
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2002-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	http://linked.opendata.cz/resource/domain/vavai/zamer/MSM%20143300001
number of pages	16 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	3-540-44043-7
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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software