### Skapa referens, olika format (klipp och klistra)

**Harvard**

Furia, C. och Spoletini, P. (2017) *Bounded variability of metric temporal logic*.

** BibTeX **

@article{

Furia2017,

author={Furia, Carlo A. and Spoletini, P.},

title={Bounded variability of metric temporal logic},

journal={Annals of Mathematics and Artificial Intelligence},

issn={1012-2443},

volume={80},

issue={3-4},

pages={283-316},

abstract={Deciding validity of Metric Temporal Logic (MTL) formulas is generally very complex and even undecidable over dense time domains; bounded variability is one of the several restrictions that have been proposed to bring decidability back. A temporal model has bounded variability if no more than v events occur over any time interval of length V, for constant parameters v and V. Previous work has shown that MTL validity over models with bounded variability is less complex—and often decidable—than MTL validity over unconstrained models. This paper studies the related problem of deciding whether an MTL formula has intrinsic bounded variability, that is whether it is satisfied only by models with bounded variability. The results of the paper are mainly negative: over dense time domains, the problem is mostly undecidable (even if with an undecidability degree that is typically lower than deciding validity); over discrete time domains, it is decidable with the same complexity as deciding validity. As a partial complement to these negative results, the paper also identifies MTL fragments where deciding bounded variability is simpler than validity, which may provide for a reduction in complexity in some practical cases.},

year={2017},

keywords={Bounded variability, Decidability and complexity, Metric temporal logic},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 247116

A1 Furia, Carlo A.

A1 Spoletini, P.

T1 Bounded variability of metric temporal logic

YR 2017

JF Annals of Mathematics and Artificial Intelligence

SN 1012-2443

VO 80

IS 3-4

SP 283

OP 316

AB Deciding validity of Metric Temporal Logic (MTL) formulas is generally very complex and even undecidable over dense time domains; bounded variability is one of the several restrictions that have been proposed to bring decidability back. A temporal model has bounded variability if no more than v events occur over any time interval of length V, for constant parameters v and V. Previous work has shown that MTL validity over models with bounded variability is less complex—and often decidable—than MTL validity over unconstrained models. This paper studies the related problem of deciding whether an MTL formula has intrinsic bounded variability, that is whether it is satisfied only by models with bounded variability. The results of the paper are mainly negative: over dense time domains, the problem is mostly undecidable (even if with an undecidability degree that is typically lower than deciding validity); over discrete time domains, it is decidable with the same complexity as deciding validity. As a partial complement to these negative results, the paper also identifies MTL fragments where deciding bounded variability is simpler than validity, which may provide for a reduction in complexity in some practical cases.

LA eng

DO 10.1007/s10472-016-9532-8

LK http://dx.doi.org/10.1007/s10472-016-9532-8

OL 30