---
_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:10.1007/978-3-030-00151-3_13'
apa: 'Bakhirkin, A., Ferrere, T., Nickovic, D., Maler, O., & 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. https://doi.org/10.1007/978-3-030-00151-3_13'
chicago: Bakhirkin, Alexey, Thomas Ferrere, Dejan Nickovic, Oded Maler, and Eugene
Asarin. “Online Timed Pattern Matching Using Automata,” 11022:215–32. Springer,
2018. https://doi.org/10.1007/978-3-030-00151-3_13.
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. Online Timed Pattern Matching Using Automata.
Vol. 11022, Springer, 2018, pp. 215–32, doi:10.1007/978-3-030-00151-3_13.
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'
...