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

Stať ve sborníku mimo WoS a Scopus

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

2011

Vydáno

13.11.2009

Nakladatel

Faculty of Informatics MU

Místo

Znojmo

ISBN

978-3-939897-15-6

Kniha

5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

Strany od

93

Strany do

101

Strany počet

9

URL

http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2009-03.pdf

BibTex

@inproceedings{BUT30855,
  author="Lukáš {Holík} and Jiří {Šimáček}",
  title="Optimizing an LTS-Simulation Algorithm",
  booktitle="5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  year="2009",
  pages="93--101",
  publisher="Faculty of Informatics MU",
  address="Znojmo",
  isbn="978-3-939897-15-6",
  url="http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2009-03.pdf"
}