License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.380
URN: urn:nbn:de:0030-drops-56563
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5656/
Almagor, Shaull ;
Kuperberg, Denis ;
Kupferman, Orna
The Sensing Cost of Monitoring and Synthesis
Abstract
In FSTTCS 2014, we introduced sensing as a new complexity measure for the complexity of regular languages. Intuitively, the sensing cost quantifies the detail in which a random input word has to be read by a deterministic automaton in order to decide its membership in the language. In this paper, we consider sensing in two principal applications of deterministic automata. The first is monitoring: we are given a computation in an on-line manner, and we have to decide whether it satisfies the specification. The second is synthesis: we are given a sequence of inputs in an on-line manner and we have to generate a sequence of outputs so that the resulting computation satisfies the specification. In the first, our goal is to design a monitor that handles all computations and minimizes the expected average number of sensors used in the monitoring process. In the second, our goal is to design a transducer that realizes the specification for all input sequences and minimizes the expected average number of sensors used for reading the inputs.
We argue that the two applications require new and different frameworks for reasoning about sensing, and develop such frameworks. We focus on safety languages. We show that for monitoring, minimal sensing is attained by a monitor
based on the minimal deterministic automaton for the language. For synthesis, however, the setting is
more challenging: minimizing the sensing may require exponentially bigger transducers, and the problem of synthesizing a minimally-sensing transducer is EXPTIME-complete even for safety specifications given by deterministic automata.
BibTeX - Entry
@InProceedings{almagor_et_al:LIPIcs:2015:5656,
author = {Shaull Almagor and Denis Kuperberg and Orna Kupferman},
title = {{The Sensing Cost of Monitoring and Synthesis}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {380--393},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-97-2},
ISSN = {1868-8969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5656},
URN = {urn:nbn:de:0030-drops-56563},
doi = {10.4230/LIPIcs.FSTTCS.2015.380},
annote = {Keywords: Automata, regular languages, omega-regular languages, complexity, sensing, minimization}
}
|
Keywords: |
|
Automata, regular languages, omega-regular languages, complexity, sensing, minimization |
|
Collection: |
|
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
14.12.2015 |
