Publication Details

Optimizing an LTS-Simulation Algorithm

HOLÍK Lukáš and ŠIMÁČEK Jiří. Optimizing an LTS-Simulation Algorithm. Computing and Informatics, vol. 2010, no. 7, pp. 1337-1348. ISSN 1335-9150. Available from: http://www.cai.sk/ojs/index.php/cai/article/view/147
Czech title
Optimalizace algoritmu pro výpočet relace simulace
Type
journal article
Language
english
Authors
URL
Keywords

simulation, labeled transition system, finite automata, tree automata

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.

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.

Published
2010
Pages
1337-1348
Journal
Computing and Informatics, vol. 2010, no. 7, ISSN 1335-9150
Publisher
Slovak Academic Press
UT WoS
000287768300018
BibTeX
@ARTICLE{FITPUB9733,
   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 = "1337--1348",
   journal = "Computing and Informatics",
   volume = 2010,
   number = 7,
   year = 2010,
   ISSN = "1335-9150",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9733"
}
Back to top