---
res:
  bibo_abstract:
  - The monitoring of event frequencies can be used to recognize behavioral anomalies,
    to identify trends, and to deduce or discard hypotheses about the underlying system.
    For example, the performance of a web server may be monitored based on the ratio
    of the total count of requests from the least and most active clients. Exact frequency
    monitoring, however, can be prohibitively expensive; in the above example it would
    require as many counters as there are clients. In this paper, we propose the efficient
    probabilistic monitoring of common frequency properties, including the mode (i.e.,
    the most common event) and the median of an event sequence. We define a logic
    to express composite frequency properties as a combination of atomic frequency
    properties. Our main contribution is an algorithm that, under suitable probabilistic
    assumptions, can be used to monitor these important frequency properties with
    four counters, independent of the number of different events. Our algorithm samples
    longer and longer subwords of an infinite event sequence. We prove the almost-sure
    convergence of our algorithm by generalizing ergodic theory from increasing-length
    prefixes to increasing-length subwords of an infinite sequence. A similar algorithm
    could be used to learn a connected Markov chain of a given structure from observing
    its outputs, to arbitrary precision, for a given confidence. @eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Thomas
      foaf_name: Ferrere, Thomas
      foaf_surname: Ferrere
      foaf_workInfoHomepage: http://www.librecat.org/personId=40960E6E-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0001-5199-3143
  - foaf_Person:
      foaf_givenName: Thomas A
      foaf_name: Henzinger, Thomas A
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
    orcid: 0000−0002−2985−7724
  - foaf_Person:
      foaf_givenName: Bernhard
      foaf_name: Kragl, Bernhard
      foaf_surname: Kragl
      foaf_workInfoHomepage: http://www.librecat.org/personId=320FC952-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0001-7745-9117
  bibo_doi: 10.4230/LIPIcs.CSL.2020.20
  bibo_volume: 152
  dct_date: 2020^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959771320
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Monitoring event frequencies@
...