Detail publikačního výsledku

Optimizing an LTS-Simulation Algorithm

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

Originální název

Optimizing an LTS-Simulation Algorithm

Anglický název

Optimizing an LTS-Simulation Algorithm

Druh

Článek WoS

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

simulation, labeled transition system, finite automata, tree automata

Klíčová slova v angličtině

simulation, labeled transition system, finite automata, tree automata

Autoři

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

Rok RIV

2012

Vydáno

20.12.2010

ISSN

1335-9150

Periodikum

COMPUTING AND INFORMATICS

Svazek

2010

Číslo

7

Stát

Slovenská republika

Strany od

1337

Strany do

1348

Strany počet

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"
}