Optimizing an LTS-Simulation Algorithm

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU86231" target="_blank" >RIV/00216305:26230/09:PU86231 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Optimizing an LTS-Simulation Algorithm

Original language description

When comparing the fastest algorithm for computing the largest simulation preorder over<br>Kripke structures with the one for labeled transition systems (LTS), there is<br>a notable time and space complexity blow-up proportional to the size of the<br>alphabet of an LTS.&nbsp; In this paper, we present optimizations that lower this<br>blow-up and may turn a large alphabet of an LTS to an advantage. Our<br>experimental results show significant speed-ups and memory savings. Moreover,<br>the optimized algorithm allows one to improve asymptotic complexity of<br>procedures for computing simulations over tree automata using recently proposed<br>algorithms based on computing simulation over certain special LTS. <br>

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2009

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

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

ISBN

978-80-87342-04-6

ISSN

—

e-ISSN

—

Number of pages

9

Pages from-to

—

Publisher name

Faculty of Informatics MU

Place of publication

Znojmo

Event location

Znojmo

Event date

Nov 13, 2009

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—