Resumen:
In this paper we consider the problem of matching sequences of events against regular expressions when the detection of atomic events is subject to bounded time uncertainty. This work represents an extension of previous work, in which the semantics of matching continuous streams of events was defined for precisely placed atomic events. In this paper we show that the general problem of matching with time uncertainty is, under a reasonable semantics, NP-complete. However, the problem is polynomial if the expression is fixed.