Journal article

HOLÍK, L. and ŠIMÁČEK, J.. Optimizing an LTS-Simulation Algorithm. Computing and Informatics. Bratislava: Slovak Academic Press, 2010, vol. 2010, no. 7, pp. 1337-1348. ISSN 1335-9150. Available from: http://www.cai.sk/ojs/index.php/cai/article/view/147
Publication language:english
Original title:Optimizing an LTS-Simulation Algorithm
Title (cs):Optimalizace algoritmu pro výpočet relace simulace
Pages:1337-1348
Place:SK
Year:2010
URL:http://www.cai.sk/ojs/index.php/cai/article/view/147
Journal:Computing and Informatics, Vol. 2010, No. 7, Bratislava, SK
ISSN:1335-9150
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:
@ARTICLE{
   author = {Lukáš Holík and Jiří Šimáček},
   title = {Optimizing an LTS-Simulation Algorithm},
   pages = {1337--1348},
   journal = {Computing and Informatics},
   volume = {2010},
   number = {7},
   year = {2010},
   ISSN = {1335-9150},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9733}
}

Your IPv4 address: 54.204.94.254
Switch to IPv6 connection

DNSSEC [dnssec]