---
_id: '78'
abstract:
- lang: eng
  text: We provide a procedure for detecting the sub-segments of an incrementally
    observed Boolean signal ω that match a given temporal pattern ϕ. As a pattern
    specification language, we use timed regular expressions, a formalism well-suited
    for expressing properties of concurrent asynchronous behaviors embedded in metric
    time. We construct a timed automaton accepting the timed language denoted by ϕ
    and modify it slightly for the purpose of matching. We then apply zone-based reachability
    computation to this automaton while it reads ω, and retrieve all the matching
    segments from the results. Since the procedure is automaton based, it can be applied
    to patterns specified by other formalisms such as timed temporal logics reducible
    to timed automata or directly encoded as timed automata. The procedure has been
    implemented and its performance on synthetic examples is demonstrated.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alexey
  full_name: Bakhirkin, Alexey
  last_name: Bakhirkin
- first_name: Thomas
  full_name: Ferrere, Thomas
  id: 40960E6E-F248-11E8-B48F-1D18A9856A87
  last_name: Ferrere
  orcid: 0000-0001-5199-3143
- first_name: Dejan
  full_name: Nickovic, Dejan
  last_name: Nickovic
- first_name: Oded
  full_name: Maler, Oded
  last_name: Maler
- first_name: Eugene
  full_name: Asarin, Eugene
  last_name: Asarin
citation:
  ama: 'Bakhirkin A, Ferrere T, Nickovic D, Maler O, Asarin E. Online timed pattern
    matching using automata. In: Vol 11022. Springer; 2018:215-232. doi:<a href="https://doi.org/10.1007/978-3-030-00151-3_13">10.1007/978-3-030-00151-3_13</a>'
  apa: 'Bakhirkin, A., Ferrere, T., Nickovic, D., Maler, O., &#38; Asarin, E. (2018).
    Online timed pattern matching using automata (Vol. 11022, pp. 215–232). Presented
    at the FORMATS: Formal Modeling and Analysis of Timed Systems, Bejing, China:
    Springer. <a href="https://doi.org/10.1007/978-3-030-00151-3_13">https://doi.org/10.1007/978-3-030-00151-3_13</a>'
  chicago: Bakhirkin, Alexey, Thomas Ferrere, Dejan Nickovic, Oded Maler, and Eugene
    Asarin. “Online Timed Pattern Matching Using Automata,” 11022:215–32. Springer,
    2018. <a href="https://doi.org/10.1007/978-3-030-00151-3_13">https://doi.org/10.1007/978-3-030-00151-3_13</a>.
  ieee: 'A. Bakhirkin, T. Ferrere, D. Nickovic, O. Maler, and E. Asarin, “Online timed
    pattern matching using automata,” presented at the FORMATS: Formal Modeling and
    Analysis of Timed Systems, Bejing, China, 2018, vol. 11022, pp. 215–232.'
  ista: 'Bakhirkin A, Ferrere T, Nickovic D, Maler O, Asarin E. 2018. Online timed
    pattern matching using automata. FORMATS: Formal Modeling and Analysis of Timed
    Systems, LNCS, vol. 11022, 215–232.'
  mla: Bakhirkin, Alexey, et al. <i>Online Timed Pattern Matching Using Automata</i>.
    Vol. 11022, Springer, 2018, pp. 215–32, doi:<a href="https://doi.org/10.1007/978-3-030-00151-3_13">10.1007/978-3-030-00151-3_13</a>.
  short: A. Bakhirkin, T. Ferrere, D. Nickovic, O. Maler, E. Asarin, in:, Springer,
    2018, pp. 215–232.
conference:
  end_date: 2018-09-06
  location: Bejing, China
  name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
  start_date: 2018-09-04
date_created: 2018-12-11T11:44:31Z
date_published: 2018-08-26T00:00:00Z
date_updated: 2023-09-13T09:35:46Z
day: '26'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-00151-3_13
external_id:
  isi:
  - '000884993200013'
file:
- access_level: open_access
  checksum: 436b7574934324cfa7d1d3986fddc65b
  content_type: application/pdf
  creator: dernst
  date_created: 2020-05-14T11:34:34Z
  date_updated: 2020-07-14T12:48:03Z
  file_id: '7831'
  file_name: 2018_LNCS_Bakhirkin.pdf
  file_size: 374851
  relation: main_file
file_date_updated: 2020-07-14T12:48:03Z
has_accepted_license: '1'
intvolume: '     11022'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 215 - 232
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication_identifier:
  isbn:
  - 978-3-030-00150-6
publication_status: published
publisher: Springer
publist_id: '7976'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online timed pattern matching using automata
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11022
year: '2018'
...