Conference paper

HOLÍK Lukáš and ŠIMÁČEK Jiří. Optimizing an LTS-Simulation Algorithm. In: 5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Znojmo: Faculty of Informatics MU, 2009, pp. 93-101. ISBN 978-3-939897-15-6.
Publication language:english
Original title:Optimizing an LTS-Simulation Algorithm
Title (cs):Optimalizace algoritmu pro výpočet relace simulace
Pages:93-101
Proceedings:5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference:MEMICS'09 -- 5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Place:Znojmo, CZ
Year:2009
ISBN:978-3-939897-15-6
Publisher:Faculty of Informatics MU
URL:http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2009-03.pdf [PDF]
Keywords
simulation, labeled transition system, finite automata, tree automata
Annotation
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.
Abstract
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:
@INPROCEEDINGS{
   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 = {93--101},
   booktitle = {5th Doctoral Workshop on Mathematical and Engineering
	Methods in Computer Science},
   year = {2009},
   location = {Znojmo, CZ},
   publisher = {Faculty of Informatics MU},
   ISBN = {978-3-939897-15-6},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9119}
}

Your IPv4 address: 54.158.55.5
Switch to IPv6 connection

DNSSEC [dnssec]