Publication result detail

Optimizing an LTS-Simulation Algorithm

HOLÍK, L.; ŠIMÁČEK, J.

Original Title

Optimizing an LTS-Simulation Algorithm

English Title

Optimizing an LTS-Simulation Algorithm

Type

WoS Article

Original 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.

English 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.

Keywords

simulation, labeled transition system, finite automata, tree automata

Key words in English

simulation, labeled transition system, finite automata, tree automata

Authors

HOLÍK, L.; ŠIMÁČEK, J.

RIV year

2012

Released

20.12.2010

ISBN

1335-9150

Periodical

COMPUTING AND INFORMATICS

Volume

2010

Number

7

State

Slovak Republic

Pages from

1337

Pages to

1348

Pages count

12

URL

http://www.cai.sk/ojs/index.php/cai/article/view/147

BibTex

@article{BUT76431,
  author="Lukáš {Holík} and Jiří {Šimáček}",
  title="Optimizing an LTS-Simulation Algorithm",
  journal="COMPUTING AND INFORMATICS",
  year="2010",
  volume="2010",
  number="7",
  pages="1337--1348",
  issn="1335-9150",
  url="http://www.cai.sk/ojs/index.php/cai/article/view/147"
}