Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Why is Simulation Harder Than Bisimulation?

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F02%3A00006376" target="_blank" >RIV/00216224:14330/02:00006376 - isvavai.cz</a>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Why is Simulation Harder Than Bisimulation?

  • Popis výsledku v původním jazyce

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

  • Název v anglickém jazyce

    Why is Simulation Harder Than Bisimulation?

  • Popis výsledku anglicky

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

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    JC - Počítačový hardware a software

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Nekonečně stavové souběžné systémy - modely a verifikace</a><br>

  • Návaznosti

    Z - Vyzkumny zamer (s odkazem do CEZ)

Ostatní

  • Rok uplatnění

    2002

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)

  • ISBN

    3-540-44043-7

  • ISSN

  • e-ISSN

  • Počet stran výsledku

    16

  • Strana od-do

    594

  • Název nakladatele

    Springer

  • Místo vydání

    Berlin

  • Místo konání akce

    August 20-23, 2002, Brno, Czech Republic

  • Datum konání akce

    1. 1. 2002

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku