Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Peyras, Quentin; Brunel, Julien; Chemouil, David http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-113731
URL:

; ;

A Bounded Domain Property for an Expressive Fragment of First-Order Linear Temporal Logic

pdf-format:


Abstract

First-Order Linear Temporal Logic (FOLTL) is well-suited to specify infinite-state systems. However, FOLTL satisfiability is not even semi-decidable, thus preventing automated verification. To address this, a possible track is to constrain specifications to a decidable fragment of FOLTL, but known fragments are too restricted to be usable in practice. In this paper, we exhibit various fragments of increasing scope that provide a pertinent basis for abstract specification of infinite-state systems. We show that these fragments enjoy the Bounded Domain Property (any satisfiable FOLTL formula has a model with a finite, bounded FO domain), which provides a basis for complete, automated verification by reduction to LTL satisfiability. Finally, we present a simple case study illustrating the applicability and limitations of our results.

BibTeX - Entry

@InProceedings{peyras_et_al:LIPIcs:2019:11373,
  author =	{Quentin Peyras and Julien Brunel and David Chemouil},
  title =	{{A Bounded Domain Property for an Expressive Fragment of First-Order Linear Temporal Logic}},
  booktitle =	{26th International Symposium on Temporal Representation and Reasoning (TIME 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-127-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{147},
  editor =	{Johann Gamper and Sophie Pinchinat and Guido Sciavicco},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11373},
  URN =		{urn:nbn:de:0030-drops-113731},
  doi =		{10.4230/LIPIcs.TIME.2019.15},
  annote =	{Keywords: First-Order Linear Temporal Logic, Bounded Domain Property, Finite Domain Property, Decidability}
}

Keywords: First-Order Linear Temporal Logic, Bounded Domain Property, Finite Domain Property, Decidability
Seminar: 26th International Symposium on Temporal Representation and Reasoning (TIME 2019)
Issue date: 2019
Date of publication: 2019


DROPS-Home | Imprint | Privacy Published by LZI