  In this paper, we focus on the problem of dynamically analysing concurrent
software against high-level temporal specifications. Existing techniques for
runtime monitoring against such specifications are primarily designed for
sequential software and remain inadequate in the presence of concurrency --
violations may be observed only in intricate thread interleavings, requiring
many re-runs of the underlying software. Towards this, we study the problem of
predictive runtime monitoring, inspired by the analogous problem of predictive
data race detection studied extensively recently. The predictive runtime
monitoring question asks, given an execution $\sigma$, if it can be soundly
reordered to expose violations of a specification.
  In this paper, we focus on specifications that are given in regular
languages. Our notion of reorderings is trace equivalence, where an execution
is considered a reordering of another if it can be obtained from the latter by
successively commuting adjacent independent actions. We first show that the
problem of predictive admits a super-linear lower bound of $O(n^\alpha)$, where
$n$ is the number of events in the execution, and $\alpha$ is a parameter
describing the degree of commutativity. As a result, predictive runtime
monitoring even in this setting is unlikely to be efficiently solvable.
  Towards this, we identify a sub-class of regular languages, called pattern
languages (and their extension generalized pattern languages). Pattern
languages can naturally express specific ordering of some number of (labelled)
events, and have been inspired by popular empirical hypotheses, the `small bug
depth' hypothesis. More importantly, we show that for pattern (and generalized
pattern) languages, the predictive monitoring problem can be solved using a
constant-space streaming linear-time algorithm.
