TY - GEN

T1 - Matching trace patterns with regular policies

AU - Baader, Franz

AU - Bauer, Andreas

AU - Tiu, Alwen

PY - 2009

Y1 - 2009

N2 - We consider policies that are described by regular expressions, finite automata, or formulae of linear temporal logic (LTL). Such policies 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 also consider the dual case where the regular policy L is supposed to describe all the admissible situations. Here, we want to know whether u always adheres to the given policy L, i.e., whether all instances of u belong to L. We determine the complexity of the violation and the adherence problem, depending on whether trace patterns are linear or not, and on whether the policy is assumed to be fixed or not.

AB - We consider policies that are described by regular expressions, finite automata, or formulae of linear temporal logic (LTL). Such policies 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 also consider the dual case where the regular policy L is supposed to describe all the admissible situations. Here, we want to know whether u always adheres to the given policy L, i.e., whether all instances of u belong to L. We determine the complexity of the violation and the adherence problem, depending on whether trace patterns are linear or not, and on whether the policy is assumed to be fixed or not.

UR - http://www.scopus.com/inward/record.url?scp=67649958898&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-00982-2_9

DO - 10.1007/978-3-642-00982-2_9

M3 - Conference contribution

SN - 9783642009815

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 105

EP - 116

BT - Language and Automata Theory and Applications - Third International Conference, LATA 2009, Proceedings

T2 - 3rd International Conference on Language and Automata Theory and Applications, LATA 2009

Y2 - 2 April 2009 through 8 April 2009

ER -