Files in this item

FilesDescriptionFormat

application/pdf

UIUCDCS-R-2007-2850.pdf (388kB)
(no description provided)PDF

Description

 Title: On Safety Properties and Their Monitoring Author(s): Rosu, Grigore Subject(s): computer science Abstract: Various definitions of safety properties as sets of execution traces have been introduced in the literature, some over finite traces, others over infinite traces, yet others over both finite and infinite traces. By employing cardinality arguments, this paper first shows that these notions of safety are ultimately equivalent, by showing each of them to have the cardinal of the continuum. It is then shown that all safety properties can be characterized as always past'' properties, and then that the problem of monitoring a safety property can be arbitrarily hard. Finally, two decidable specification formalisms for safety properties are discussed, namely extended regular expressions and past time LTL. It is shown that monitoring the former requires non-elementary space. An optimal monitor synthesis algorithm is given for the latter; the generated monitors run in space linear with the number of temporal operators and in time linear with the size of the formula. Issue Date: 2007-02 Genre: Technical Report Type: Text URI: http://hdl.handle.net/2142/11353 Other Identifier(s): UIUCDCS-R-2007-2850 Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s). Date Available in IDEALS: 2009-04-22
﻿