HOLÍK Lukáš and ŠIMÁČEK Jiří. Optimizing an LTSSimulation Algorithm. In: 5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Znojmo: Faculty of Informatics MU, 2009, pp. 93101. ISBN 9783939897156. 
Publication language:  english 

Original title:  Optimizing an LTSSimulation Algorithm 

Title (cs):  Optimalizace algoritmu pro výpočet relace simulace 

Pages:  93101 

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:  9783939897156 

Publisher:  Faculty of Informatics MU 

URL:  http://www.fit.vutbr.cz/~holik/pub/FITTR200903.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 blowup proportional to the size of the alphabet of an LTS. In this paper, we present optimizations that lower this blowup and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speedups 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 blowup proportional to the size of the alphabet of an LTS. In this paper, we present optimizations that lower this blowup and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speedups 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 LTSSimulation Algorithm},
pages = {93101},
booktitle = {5th Doctoral Workshop on Mathematical and Engineering
Methods in Computer Science},
year = 2009,
location = {Znojmo, CZ},
publisher = {Faculty of Informatics MU},
ISBN = {9783939897156},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9119}
} 