About: P-hardness of Equivalence Testing on Finite-State 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)

AttributesValues
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
  • 326-335
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
  • 691045
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
  • [004B11BFA0F5]
http://linked.open...v/mistoKonaniAkce
  • Piešťany, Slovenská republika
http://linked.open...i/riv/mistoVydani
  • Brusel
http://linked.open...i/riv/nazevZdroje
  • Proc. SOFSEM 2001
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
  • Jančar, Petr
  • Sawa, Z.
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
  • Elsevier
https://schema.org/isbn
  • 3-540-42912-3
http://localhost/t...ganizacniJednotka
  • 27240
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
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