BENEŠ, Nikola, Jan KŘETÍNSKÝ, Kim G. LARSEN and Jiří SRBA. On Determinism in Modal Transition Systems. Theoretical Computer Science. Elsevier, 2009, 410/2009, No 41, p. 4026-4043. ISSN 0304-3975.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name On Determinism in Modal Transition Systems
Name in Czech O determinismu v modálních přechodových systémech
Authors BENEŠ, Nikola (203 Czech Republic, belonging to the institution), Jan KŘETÍNSKÝ (203 Czech Republic, guarantor, belonging to the institution), Kim G. LARSEN (208 Denmark) and Jiří SRBA (203 Czech Republic, belonging to the institution).
Edition Theoretical Computer Science, Elsevier, 2009, 0304-3975.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
Impact factor Impact factor: 0.943
RIV identification code RIV/00216224:14330/09:00029307
Organization unit Faculty of Informatics
UT WoS 000269865800003
Keywords in English compositional verification; modal transition systems; determinism; refinement; consistency
Tags compositional verification, consistency, determinism, modal transition systems, REFINEMENT
Tags International impact, Reviewed
Changed by Changed by: RNDr. Nikola Beneš, Ph.D., učo 72525. Changed: 24. 10. 2013 16:20.
Abstract
Modal transition systems (MTS) is a formalism which extends the classical notion of labelled transition systems by introducing transitions of two types: must transitions that have to be present in any implementation of the MTS and may transitions that are allowed but not required. The MTS framework has proved to be useful as a specification formalism of component-based systems as it supports compositional verification and stepwise refinement. Nevertheless, there are some limitations of the theory, namely that the naturally defined notions of modal refinement and modal composition are incomplete with respect to the semantic view based on the sets of the implementations of a given MTS specification. Recent work indicates that some of these limitations might be overcome by considering deterministic systems, which seem to be more manageable but still interesting for several application areas. In the present article, we provide a comprehensive account of the MTS framework in the deterministic setting. We study a number of problems previously considered on MTS and point out to what extent we can expect better results under the restriction of determinism.
Abstract (in Czech)
Modální přechodové systémy (MTS) jsou formalismus rozšiřující klasické označkované přechodové systémy zavedením přechodů dvou typů: must přechody, které musí být přítomny v každé implementaci a may přechody, které jsou povolené, ale nikoli vyžadované. Rámec MTS se prokázal být užitečným formalismem pro specifikaci komponentových systémů, protože podporuje kompozicionální verifikaci a postupné zjemňování. Nicméně tato teorie má i své limity: přirozeně definované pojmy modálního zjemnění a modální kompozice jsou neúplné vzhledem k sémantice založené na množinách implementací dané MTS specifikace. Nedávné výsledky však naznačují, že tyto potíže mohou být překonány uvážením deterministických systémů, které se zdají více zvladatelné, ale stále zajímavé pro řadu praktických oblastí. V tomto článku podáváme ucelenou studii MTS v deterministickém rámci. Studujeme řadu problémů dříve uvažovaných na MTS a ukazujeme, do jaké míry můžeme očekávat lepší výsledky při restrikci na determinismus.
Links
GA201/09/1389, research and development projectName: Verifikace a analýza velmi velkých počítačových systémů
Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems
MSM0021622419, plan (intention)Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development projectName: Institut Teoretické Informatiky
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science
PrintDisplayed: 27. 6. 2022 02:42