From Reactive Systems to Cyber-Physical Systems - Essays Dedicated to Scott A. Smolka on the Occasion of His 65th Birthday
From Reactive Systems to Cyber-Physical Systems - Essays Dedicated to Scott A. Smolka on the Occasion of His 65th Birthday
复制标题
从反应式系统到网络物理系统 - 献给 Scott A. Smolka 65 岁生日的论文
DOI：
10.1007/978-3-030-31514-6_15
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Aceto L
中科院分区：
文献类型：
--
作者：
Aceto L
我们比较了两种监控系统（即并行监控器和常规监控器）对于无限迹线属性的简洁性。尽管并行监视器可以转变为等效的常规监视器，但这种转换的成本是监视器语法大小的双指数爆炸，并且当目标是确定性监视器时是三指数爆炸。我们证明这些界限是严格的，并且它们也适用于具有无限踪迹递归的 Hennessy-Milner 逻辑的相应片段之间的转换。
We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equivalent regular monitor, the cost of this transformation is a double-exponential blowup in the syntactic size of the monitors, and a triple-exponential blowup when the goal is a deterministic monitor. We show that these bounds are tight and that they also hold for translations between corresponding fragments of Hennessy-Milner logic with recursion over infinite traces.