Detail výsledku

Optimizing an LTS-Simulation Algorithm

HOLÍK, L.; ŠIMÁČEK, J. Optimizing an LTS-Simulation Algorithm. FIT-TR-2009-03, Brno: 2009. 17 p.
Typ
zpráva odborná
Jazyk
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D., UITS (FIT)
Šimáček Jiří, Ing., Ph.D., UITS (FIT)
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

URL
Rok
2009
Strany
17
Místo
FIT-TR-2009-03, Brno
BibTeX 
@misc{BUT192697,
  author="Lukáš {Holík} and Jiří {Šimáček}",
  title="Optimizing an LTS-Simulation Algorithm",
  year="2009",
  pages="17",
  address="FIT-TR-2009-03, Brno",
  url="http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2009-03.pdf"
}
Projekty
Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů, GAČR, Doktorské granty, GD102/09/H042, zahájení: 2009-01-30, ukončení: 2012-12-31, ukončen
Pokročilé formální přístupy v návrhu a automatické verifikaci počítačových systémů, GAČR, Standardní projekty, GA102/07/0322, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
Rozvoj technik pro automatické verifikace programů s dynamickými datovými strukturami, GAČR, Postdoktorandské granty, GP201/09/P531, zahájení: 2009-01-01, ukončení: 2011-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina automatizované analýzy a verifikace - VeriFIT (VZ VERIFIT)
Pracoviště
Ústav inteligentních systémů (UITS)
Nahoru