---
OA_place: publisher
OA_type: gold
_id: '22921'
abstract:
- lang: eng
  text: 'Runtime monitoring of quantitative signals faces a fundamental trade-off
    between volatility and over-aggregation: instantaneous observations are noisy,
    while long-run averages obscure local structure. Localisation measures such as
    discounted averages offer a principled middle ground, yet remain poorly understood
    in runtime verification. This paper studies discounted sums from a monitoring
    perspective, in both deterministic and stochastic settings. We formalize the discounted
    monitoring problem and show that exact, sound monitoring of discounted sums cannot
    be achieved with finite memory. To overcome this impossibility, we introduce ε-approximately
    sound monitoring, deriving explicit bounds on memory and observation requirements.
    We then extend the framework to stochastic processes via expected discounted sums,
    defining pointwise and uniform (ε,δ)-soundness notions, establishing statistical
    optimality, and proving impossibility beyond a precision threshold. We also formalize
    the resource complexity of deterministic discounted monitoring via affine register
    machines and prove a tight worst-case lower bound. Finally, we present a specification
    language for arithmetic expressions over multiple discounted sums with synchronous
    and asynchronous semantics, and evaluate our approach on practical scenarios including
    algorithmic fairness.'
acknowledgement: "This work has been supported by the European Research Council under
  Grant No.: ERC2020-AdG 101020093 and ERC-2021-AdG 101055412.\r\nFilip Cano: ERC-2020-AdG
  101020093\r\nThomas A. Henzinger: ERC-2020-AdG 101020093\r\nKonstantin Kueffner:
  ERC-2020-AdG 101020093\r\nN. Ege Saraç: ERC-2021-AdG 101055412"
alternative_title:
- LIPIcs
article_number: 22:1-22:19
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Filip
  full_name: Cano Cordoba, Filip
  id: 708cad98-e86a-11ef-8098-bdae2d7c6af1
  last_name: Cano Cordoba
  orcid: 0000-0002-0783-904X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
- first_name: Konstantin
  full_name: Kueffner, Konstantin
  id: 8121a2d0-dc85-11ea-9058-af578f3b4515
  last_name: Kueffner
  orcid: 0000-0001-8974-2542
- first_name: Naci E
  full_name: Sarac, Naci E
  id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
  last_name: Sarac
citation:
  ama: 'Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. Monitoring discounted
    sum properties. In: <i>37th International Conference on Concurrency Theory</i>.
    Vol 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.22">10.4230/LIPIcs.CONCUR.2026.22</a>'
  apa: 'Cano Cordoba, F., Henzinger, T. A., Kueffner, K., &#38; Sarac, N. E. (2026).
    Monitoring discounted sum properties. In <i>37th International Conference on Concurrency
    Theory</i> (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.22">https://doi.org/10.4230/LIPIcs.CONCUR.2026.22</a>'
  chicago: Cano Cordoba, Filip, Thomas A Henzinger, Konstantin Kueffner, and Naci
    E Sarac. “Monitoring Discounted Sum Properties.” In <i>37th International Conference
    on Concurrency Theory</i>, Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.22">https://doi.org/10.4230/LIPIcs.CONCUR.2026.22</a>.
  ieee: F. Cano Cordoba, T. A. Henzinger, K. Kueffner, and N. E. Sarac, “Monitoring
    discounted sum properties,” in <i>37th International Conference on Concurrency
    Theory</i>, Liverpool, United Kingdom, 2026, vol. 391.
  ista: 'Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. 2026. Monitoring discounted
    sum properties. 37th International Conference on Concurrency Theory. CONCUR: Conference
    on Concurrency Theory, LIPIcs, vol. 391, 22:1-22:19.'
  mla: Cano Cordoba, Filip, et al. “Monitoring Discounted Sum Properties.” <i>37th
    International Conference on Concurrency Theory</i>, vol. 391, 22:1-22:19, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.22">10.4230/LIPIcs.CONCUR.2026.22</a>.
  short: F. Cano Cordoba, T.A. Henzinger, K. Kueffner, N.E. Sarac, in:, 37th International
    Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026.
conference:
  end_date: 2026-09-04
  location: Liverpool, United Kingdom
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2026-09-01
corr_author: '1'
das_tickbox: '1'
dataavailabilitystatement: "Software (Source Code): https://github.com/filipcano/monitoringdiscounted-sum-properties
  [10]\r\narchived at swh:1:dir:cb99396415f279c985cd05206b44320227f64245\r\n"
date_created: 2026-09-13T22:01:54Z
date_published: 2026-08-24T00:00:00Z
date_updated: 2026-09-22T06:02:06Z
day: '24'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.4230/LIPIcs.CONCUR.2026.22
ec_funded: 1
external_id:
  arxiv:
  - '2606.25979'
file:
- access_level: open_access
  checksum: f7b2e22428344fd7972c54f099df6aba
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-22T05:59:03Z
  date_updated: 2026-09-22T05:59:03Z
  file_id: '22978'
  file_name: 2026_LIPIcsCONCUR_Cano.pdf
  file_size: 997156
  relation: main_file
  success: 1
file_date_updated: 2026-09-22T05:59:03Z
fulldoi: https://doi.org/10.4230/LIPIcs.CONCUR.2026.22
has_accepted_license: '1'
intvolume: '       391'
keyword:
- Runtime Verification
- Probabilistic Systems
- Quantitative Verification
- Approximate Monitoring
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 37th International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783959774475'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Monitoring discounted sum properties
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 391
year: '2026'
...