This HTML5 document contains 46 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n18http://localhost/temp/predkladatel/
n13http://linked.opendata.cz/resource/domain/vavai/projekt/
n5http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n16http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n15http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F61989100%3A27240%2F05%3A00012189%21RIV06-GA0-27240___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n10http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n11http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F61989100%3A27240%2F05%3A00012189%21RIV06-GA0-27240___
rdf:type
skos:Concept n16:Vysledek
dcterms:description
The paper shows a LOGSPACE-reduction from the boolean circuit value problem which demonstrates that any relation subsuming bisimilarity and being subsumed by trace preorder (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balcázar, Gabarró and Sántha (1992) for bisimilarity. The paper shows a LOGSPACE-reduction from the boolean circuit value problem which demonstrates that any relation subsuming bisimilarity and being subsumed by trace preorder (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balcázar, Gabarró and Sántha (1992) for bisimilarity. The paper shows a LOGSPACE-reduction from the boolean circuit value problem which demonstrates that any relation subsuming bisimilarity and being subsumed by trace preorder (i.e., language inclusion) is PTIME-hard, even for finite acyclic labelled transition systems. This reproves and substantially extends the result of Balcázar, Gabarró and Sántha (1992) for bisimilarity.
dcterms:title
Behavioural Equivalences on Finite-State Systems are PTIME-hard Behavioural Equivalences on Finite-State Systems are PTIME-hard Behavioural Equivalences on Finite-State Systems are PTIME-hard
skos:prefLabel
Behavioural Equivalences on Finite-State Systems are PTIME-hard Behavioural Equivalences on Finite-State Systems are PTIME-hard Behavioural Equivalences on Finite-State Systems are PTIME-hard
skos:notation
RIV/61989100:27240/05:00012189!RIV06-GA0-27240___
n3:strany
513-528
n3:aktivita
n12:P
n3:aktivity
P(GA201/03/1161)
n3:cisloPeriodika
5
n3:dodaniDat
n11:2006
n3:domaciTvurceVysledku
n5:6026508 n5:2066041
n3:druhVysledku
n14:J
n3:duvernostUdaju
n9:S
n3:entitaPredkladatele
n15:predkladatel
n3:idSjednocenehoVysledku
513638
n3:idVysledku
RIV/61989100:27240/05:00012189
n3:jazykVysledku
n17:eng
n3:klicovaSlova
verification; finite transition systems; bisimulation equivalence; trace equivalence; computational complexity; PTIME-hardness
n3:klicoveSlovo
n4:bisimulation%20equivalence n4:finite%20transition%20systems n4:PTIME-hardness n4:trace%20equivalence n4:verification n4:computational%20complexity
n3:kodStatuVydavatele
SK - Slovenská republika
n3:kontrolniKodProRIV
[FC36788DADCC]
n3:nazevZdroje
Computing and Informatics
n3:obor
n10:IN
n3:pocetDomacichTvurcuVysledku
2
n3:pocetTvurcuVysledku
2
n3:projekt
n13:GA201%2F03%2F1161
n3:rokUplatneniVysledku
n11:2005
n3:svazekPeriodika
24
n3:tvurceVysledku
Jančar, Petr Sawa, Zdeněk
s:issn
1335-9150
s:numberOfPages
15
n18:organizacniJednotka
27240