On Decidability of LTL Model Checking for Process Rewrite Systems

BOZZELLI, Laura, Mojmír KŘETÍNSKÝ, Vojtěch ŘEHÁK and Jan STREJČEK. On Decidability of LTL Model Checking for Process Rewrite Systems. Acta informatica. Berlin: Springer-Verlag, 2009, vol. 46, No 1, p. 1-28. ISSN 0001-5903.

Basic information

Original name

On Decidability of LTL Model Checking for Process Rewrite Systems

Name in Czech

O rozhodnutelnosti problému ověřování modelu pro LTL a procesové přepisovací systémy

Authors

BOZZELLI, Laura (380 Italy), Mojmír KŘETÍNSKÝ (203 Czech Republic, guarantor), Vojtěch ŘEHÁK (203 Czech Republic) and Jan STREJČEK (203 Czech Republic)

Edition

Acta informatica, Berlin, Springer-Verlag, 2009, 0001-5903

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 0.923

RIV identification code

RIV/00216224:14330/09:00029078

Organization unit

Faculty of Informatics

UT WoS

000262531800001

Keywords in English

infinite-state systems; linear time logic; decidability; model checking

Tags

decidability, infinite-state systems, linear time logic, Model checking

Tags

International impact, Reviewed

---

Abstract

V originále

We establish a decidability boundary of the model checking problem for infinite-state systems defined by Process Rewrite Systems (PRS) or weakly extended Process Rewrite Systems (wPRS), and properties described by basic fragments of action-based Linear Temporal Logic (LTL) with both future and past operators. It is known that the problem for general LTL properties is decidable for Petri nets and for pushdown processes, while it is undecidable for PA processes. We show that the problem is decidable for wPRS if we consider properties defined by LTL formulae with only modalities strict eventually, strict always, and their past counterparts. Moreover, we show that the problem remains undecidable for PA processes even with respect to the LTL fragment with the only modality until or the fragment with modalities next and infinitely often.

In Czech

Je ustanovena hranice rozhodnutelnosti pro problém ověřování modelu pro fragmenty logiky LTL s budoucími i minulostními operátory a nekonečně stavové systémy generované tzv. procesovými přepisovacími systémy (PRS) nebo slabě rozšířenými procesovými přepisovacími systémy (wPRS). Je známo, že tento problém je pro obecnou LTL rozhodnutelný pro Petriho sítě a zásobníkové procesy, ale nerozhodnutelný pro PA procesy. Ukážeme, že tento problém je rozhodnutelný pro třídu wPRS pokud uvažujeme LTL frament s modalitami "strict always", "strict eventually" a jejich minulostními verzemi. Dále ukážeme, že problém je nerozhodnutelný pro třídu PA procesů a fragment s modalitou "until" resp. fragment s modalitami "next" a "infinitely often".

---

Links

GA201/06/1338, research and development project	Name: Automatizovaná verifikace softwaru Investor: Czech Science Foundation, Automated software verification
GP201/08/P375, research and development project	Name: Formální verifikace: algoritmy, vlastnosti modelovacích formalismů a temporálních logik Investor: Czech Science Foundation, Formal verification: algorithms, properties of modelling formalisms amd temporal logics
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 project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science