On the Complexity of Timed Pattern Matching
19th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2021, Virtual, Online, 24 - 26 Ağustos 2021, cilt.12860 LNCS, ss.15-31, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 12860 LNCS
- Doi Numarası: 10.1007/978-3-030-85037-1_2
- Basıldığı Şehir: Virtual, Online
- Sayfa Sayıları: ss.15-31
- Anahtar Kelimeler: Complexity, Pattern matching, Timed regular expressions
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Timed pattern matching consists in finding occurrences of a timed regular expression in a timed word. This problem has been addressed using several techniques, its solutions are implemented in tools (quite efficient in practice), and used, for example in log analysis and runtime verification. In this article, we explore computational complexity of timed pattern matching, and prove P, NP and PSPACE bounds, depending on connectives used in expressions and other details. We conclude with a couple of open questions.