Skip to main content


Matching linear and non-linear trace patterns with regular policies


Franz Baader, Andreas Bauer and Alwen Tiu

TU Dresden


Australian National University


In this paper, we consider policies that are described by regular languages. Such regular policies L are assumed to describe situations that are problematic, and thus should be avoided. Given a trace pattern u, i.e., a sequence of action symbols and variables, were the variables stand for unknown (i.e., not observed) sequences of actions, we ask whether u potentially violates a given policy L, i.e., whether the variables in u can be replaced by sequences of actions such that the resulting trace belongs to L. We determine the complexity of this violation problem, depending on whether trace patterns are linear or not, and on whether the policy is assumed to be fixed or not.

BibTeX Entry

    publisher        = {RISC-Linz},
    author           = {Baader, Franz and Bauer, Andreas and Tiu, Alwen},
    month            = jul,
    editor           = {{M. Marin}},
    year             = {2008},
    title            = {Matching linear and non-linear trace patterns with regular policies},
    booktitle        = {22nd International Workshop on Unification (UNIF)},
    pages            = {16--24},
    address          = {Linz, Austria}