Skip to main content

TS

Matching linear and non-linear trace patterns with regular policies

Authors

Franz Baader, Andreas Bauer and Alwen Tiu

TU Dresden

NICTA

Australian National University

Abstract

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

  @inproceedings{Baader_BT_08,
    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}
  }

Download

Served by Apache on Linux on seL4.