Fighting State Space Explosion: Review and Evaluation

PELÁNEK, Radek. Fighting State Space Explosion: Review and Evaluation. Online. In Formal Methods for Industrial Critical Systems. Německo: Springer, 2008. 15 pp. ISBN 3-642-03239-7. [citováno 2024-04-24]

Basic information

• Original name: Fighting State Space Explosion: Review and Evaluation
• Name in Czech: Boj se stavovou explozí: přehled a zhodnocení
• Authors: PELÁNEK, Radek (203 Czech Republic, guarantor)
• Edition: Německo, Formal Methods for Industrial Critical Systems, 15 pp. 2008.
• Publisher: Springer

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• RIV identification code: RIV/00216224:14330/08:00025026
• Organization unit: Faculty of Informatics
• ISBN: 3-642-03239-7
• UT WoS: 000270704100003
• Keywords in English: model checking; state space explosion; review; evaluation; experience report
• Tags: evaluation, experience report, Model checking, Review, state space explosion
• Tags: International impact, Reviewed

Abstract

In order to apply formal methods in practice, the practitioner has to comprehend a vast amount of research literature and realistically evaluate practical merits of different approaches. In this paper we focus on explicit finite state model checking and study this area from practitioner's point of view. We provide a systematic overview of techniques for fighting state space explosion and we analyse trends in the research. We also report on our own experience with practical performance of techniques. Our main conclusion and recommendation for practitioner is the following: be critical to claims of dramatic improvement brought by a single sophisticated technique, rather use many different simple techniques and combine them.

Abstract (in Czech)

Aby bylo možné v současnosti aplikovat formální metody v praxi, musí být uživatelé schopni uchopit velké množství odborné literatury a realisticky vyhodnotit praktický přínos jednotlivých přístupů. V této práci se zaměřujeme na metodu explicitního ověřování modelu a studujeme tuto metodu z pohledu uživatele z praxe. Nabízíme systematický přehled různých technik pro boj se stavovou explozí a analyzujeme trendy ve výzkumu. Popisujeme také několik vlastních praktických zkušeností. Náš hlavní závěr a doporučení pro uživatele je následující: buďte kritičtí k tvrzením o drastickém zlepšení, kterého dosahuje jedna sofistikovaná technika, raději používejte velké množství jednoduchých technik.

Links

• GP201/07/P035, research and development project: Name: Automatická analýza modelů pomocí procházení stavového prostoru

Investor: Czech Science Foundation, Automatic model analysis by state space exploration

• 1M0545, research and development project: Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science