Online timed pattern matching using automata Conference Paper


Author(s): Bakhirkin, Alexey; Ferrère, Thomas; Ničković, Dejan; Maler, Oded; Asarin, Eugene A
Title: Online timed pattern matching using automata
Title Series: LNCS
Affiliation IST Austria
Abstract: 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.
Conference Title: FORMATS: Formal Modeling and Analysis of Timed Systems
Volume: 11022
Conference Dates: September 4 - 6, 2018
Conference Location: Beijing, China
ISBN: 978-303000150-6
Publisher: Springer  
Date Published: 2018-08-26
Start Page: 215
End Page: 232
DOI: 10.1007/978-3-030-00151-3_13
Open access: no
IST Austria Authors
Related IST Austria Work