Publication 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

conference paper

Language

en

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

RIV year

2009

Released

13.11.2009

Publisher

Faculty of Informatics MU

Location

Znojmo

ISBN

978-3-939897-15-6

Book

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

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

93

Pages to

101

Pages count

9

URL

Documents

BibTex


@inproceedings{BUT30855,
  author="Lukáš {Holík} and Jiří {Šimáček}",
  title="Optimizing an LTS-Simulation Algorithm",
  annote="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.",
  address="Faculty of Informatics MU",
  booktitle="5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  chapter="30855",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Faculty of Informatics MU",
  year="2009",
  month="november",
  pages="93--101",
  publisher="Faculty of Informatics MU",
  type="conference paper"
}