Technická zpráva

HOLÍK Lukáš a ŠIMÁČEK Jiří. Optimizing an LTS-Simulation Algorithm. FIT-TR-2009-03, Brno, 2009.
Jazyk publikace:angličtina
Název publikace:Optimizing an LTS-Simulation Algorithm
Název (cs):Optimalizace algoritmu pro výpočet relace simulace
Strany:17
Místo vydání:FIT-TR-2009-03, Brno, CZ
Rok:2009
URL:http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2009-03.pdf [PDF]
Klíčová slova
simulation, labeled transition system, finite automata, tree automata
Anotace
Optimalizace algoritmu pro výpočet relací simulace nad přechodovými systémy s návěštími (PSsN). 
Abstrakt
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.
BibTeX:
@TECHREPORT{
   author = {Luk{\'{a}}{\v{s}} Hol{\'{i}}k and Ji{\v{r}}{\'{i}}
	{\v{S}}im{\'{a}}{\v{c}}ek},
   title = {Optimizing an LTS-Simulation Algorithm},
   pages = {17},
   year = {2009},
   location = {FIT-TR-2009-03, Brno, CZ},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9085}
}

Vaše IPv4 adresa: 54.224.18.114
Přepnout na IPv6 spojení

DNSSEC [dnssec]