About: On Decidability of LTL Model Checking for Process Rewrite Systems

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On Decidability of LTL Model Checking for Process Rewrite Systems Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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". 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". (en) 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". (cs)
Title	On Decidability of LTL Model Checking for Process Rewrite Systems On Decidability of LTL Model Checking for Process Rewrite Systems (en) O rozhodnutelnosti problému ověřování modelu pro LTL a procesové přepisovací systémy (cs)
skos:prefLabel	On Decidability of LTL Model Checking for Process Rewrite Systems On Decidability of LTL Model Checking for Process Rewrite Systems (en) O rozhodnutelnosti problému ověřování modelu pro LTL a procesové přepisovací systémy (cs)
skos:notation	RIV/00216224:14330/06:00015417!RIV07-AV0-14330___
http://linked.open.../vavai/riv/strany	248-259
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1ET408050503), P(1M0545), P(GA201/06/1338), P(GD102/05/H050), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	Vol. 4337
http://linked.open...vai/riv/dodaniDat	2007
http://linked.open...aciTvurceVysledku	Řehák, Vojtěch Strejček, Jan Křetínský, Mojmír
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	490295
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/06:00015417
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	infinite-state systems; linear time logic; decidability; model checking (en)
http://linked.open.../riv/klicoveSlovo	linear time logic decidability model checking infinite-state systems
http://linked.open...odStatuVydavatele	IN - Indická republika
http://linked.open...ontrolniKodProRIV	[5603B3B9F9D8]
http://linked.open...i/riv/nazevZdroje	Lectute Notes in Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Automated software verification Institute for Theoretical Computer Science Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems Techniques for automatic verification and validation of software and hardware systems
http://linked.open...UplatneniVysledku	2006
http://linked.open...v/svazekPeriodika	2006
http://linked.open...iv/tvurceVysledku	Řehák, Vojtěch Strejček, Jan Křetínský, Mojmír Bozzelli, Laura
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	0302-9743
number of pages	12 (xsd:int)
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software