Optimizing an LTS-Simulation Algorithm

Authors

  • Lukáš Holík
  • Jiří Šimáček

Keywords:

LTS-Simulation

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 noticeable time and space complexity blow-up proportional to the size of the alphabet of an LTS. In this paper, we present optimizations that suppress this increase of complexity 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 derived from a tree automaton.

Downloads

Download data is not yet available.

Author Biographies

Lukáš Holík

Faculty of Information Technology
Brno University of Technology
Božetechova 2
612 66 Brno, Czech Republic

Jiří Šimáček

Faculty of Information Technology
Brno University of Technology
Božetechova 2
612 66 Brno, Czech Republic

Downloads

Published

2012-01-26

How to Cite

Holík, L., & Šimáček, J. (2012). Optimizing an LTS-Simulation Algorithm. COMPUTING AND INFORMATICS, 29(6+), 1337–1348. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/147