D 2006

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

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

Berlin, FSTTCS 2006: 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings, p. 248-259, 12 pp. 2006

Publisher

Springer-Verlag

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

India

Confidentiality degree

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

RIV identification code

RIV/00216224:14330/06:00015417

Organization unit

Faculty of Informatics

ISBN

978-3-540-49994-7

UT WoS

000244553400024

Keywords in English

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

Tags

Tags

International impact, Reviewed
Změněno: 20/12/2011 18:12, prof. RNDr. Jan Strejček, Ph.D.

Abstract

ORIG CZ

V originále

We establish a decidability boundary of the model checking problem for infinite-state systems defined by Process Rewrite Systems (PRS), possibly extended with a weak finite-state control unit, and properties described by basic fragments of action-based Linear Temporal Logic (LTL). 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. As our main result, we show that the problem is decidable for wPRS if we consider properties defined by formulae with only modalities "strict eventually" and "strict always". 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 a nekonečně stavové systémy generované tzv. procesovými přepisovacími systémy (eventuelně rozšířenými o tzv.slabou konečně stavovou řídicí jednotku). Zejména je ukázáno, že tento problém je rozhodnutelný na celé zmíněné třídě pro LTL frament s modalitami "strict always" a "strict eventually". 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
GD102/05/H050, research and development project
Name: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů
Investor: Czech Science Foundation, Integrated approach to education of PhD students in the area of parallel and distributed 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
1ET408050503, research and development project
Name: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Academy of Sciences of the Czech Republic, Techniques for automatic verification and validation of software nad hardware 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