This HTML5 document contains 43 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/
n10http://localhost/temp/predkladatel/
n19http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n13http://linked.opendata.cz/resource/domain/vavai/projekt/
n9http://linked.opendata.cz/ontology/domain/vavai/
n7http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n14http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216305%3A26230%2F10%3APU96135%21RIV12-MSM-26230___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n16http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n12http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216305%3A26230%2F10%3APU96135%21RIV12-MSM-26230___
rdf:type
skos:Concept n9:Vysledek
dcterms:description
When comparing the fastest algorithm for computing the largest simulation preorder over Kripke structures with the one for labeled transition systems (LTS), there is a notable time and space complexity blow-up proportional to the size of the alphabet of an LTS.  In this paper, we present optimizations that lower this blow-up and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speed-ups and memory savings. Moreover, the optimized algorithm allows one to improve asymptotic complexity of procedures for computing simulations over tree automata using recently proposed algorithms based on computing simulation over certain special LTS. When comparing the fastest algorithm for computing the largest simulation preorder over Kripke structures with the one for labeled transition systems (LTS), there is a notable time and space complexity blow-up proportional to the size of the alphabet of an LTS.  In this paper, we present optimizations that lower this blow-up and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speed-ups and memory savings. Moreover, the optimized algorithm allows one to improve asymptotic complexity of procedures for computing simulations over tree automata using recently proposed algorithms based on computing simulation over certain special LTS.
dcterms:title
Optimizing an LTS-Simulation Algorithm Optimizing an LTS-Simulation Algorithm
skos:prefLabel
Optimizing an LTS-Simulation Algorithm Optimizing an LTS-Simulation Algorithm
skos:notation
RIV/00216305:26230/10:PU96135!RIV12-MSM-26230___
n3:aktivita
n15:P n15:Z
n3:aktivity
P(GD102/09/H042), P(GP201/09/P531), Z(MSM0021630528)
n3:cisloPeriodika
7
n3:dodaniDat
n12:2012
n3:domaciTvurceVysledku
n19:7182430 n19:1258486
n3:druhVysledku
n17:J
n3:duvernostUdaju
n18:S
n3:entitaPredkladatele
n14:predkladatel
n3:idSjednocenehoVysledku
277426
n3:idVysledku
RIV/00216305:26230/10:PU96135
n3:jazykVysledku
n4:eng
n3:klicovaSlova
simulation, labeled transition system, finite automata, tree automata
n3:klicoveSlovo
n16:tree%20automata n16:finite%20automata n16:simulation n16:labeled%20transition%20system
n3:kodStatuVydavatele
SK - Slovenská republika
n3:kontrolniKodProRIV
[D731015FC510]
n3:nazevZdroje
Computing and Informatics
n3:obor
n5:IN
n3:pocetDomacichTvurcuVysledku
2
n3:pocetTvurcuVysledku
2
n3:projekt
n13:GP201%2F09%2FP531 n13:GD102%2F09%2FH042
n3:rokUplatneniVysledku
n12:2010
n3:svazekPeriodika
2010
n3:tvurceVysledku
Šimáček, Jiří Holík, Lukáš
n3:zamer
n7:MSM0021630528
s:issn
1335-9150
s:numberOfPages
12
n10:organizacniJednotka
26230