Attributes | Values |
---|
rdf:type
| |
Description
| - The paper shows a simple LOGSPACE-reduction from the boolean circuit value problem which demonstrates that, on finite labelled transition systems, deciding an arbitrary relation which subsumes bisimulation equivalence and is subsumed by trace preorder isa polynomial-time-hard problem (and thus can not be expected to be efficiently parallelizable). By this, the result of Balcazar, Gabarro and Santha (1992) for bisimilarity is substantially extended.
- The paper shows a simple LOGSPACE-reduction from the boolean circuit value problem which demonstrates that, on finite labelled transition systems, deciding an arbitrary relation which subsumes bisimulation equivalence and is subsumed by trace preorder isa polynomial-time-hard problem (and thus can not be expected to be efficiently parallelizable). By this, the result of Balcazar, Gabarro and Santha (1992) for bisimilarity is substantially extended. (en)
|
Title
| - P-hardness of Equivalence Testing on Finite-State Processes
- P-hardness of Equivalence Testing on Finite-State Processes (en)
|
skos:prefLabel
| - P-hardness of Equivalence Testing on Finite-State Processes
- P-hardness of Equivalence Testing on Finite-State Processes (en)
|
skos:notation
| - RIV/61989100:27240/01:00001049!RIV/2002/GA0/272402/N
|
http://linked.open.../vavai/riv/strany
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(GA201/97/0456), Z(MSM 272400013)
|
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/01:00001049
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - verification; finite-state systems; complexity (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| - Piešťany, Slovenská republika
|
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| |
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...ocetUcastnikuAkce
| |
http://linked.open...nichUcastnikuAkce
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| |
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
http://linked.open...n/vavai/riv/zamer
| |
number of pages
| |
http://purl.org/ne...btex#hasPublisher
| |
https://schema.org/isbn
| |
http://localhost/t...ganizacniJednotka
| |