Optimizing an LTS-Simulation Algorithm

Result code in IS VaVaI

RIV/00216305:26230/09:PU86231 - isvavai.cz

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

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

—