\title{Matching Specifications for Message Sequence Charts} 


\author{Anca Muscholl}

\institute{Institut f\"ur Informatik, Universit\"at Stuttgart,\\
  Breitwiesenstr.~20-22, 70565 Stuttgart, Germany 
}

\begin{abstract}
  Message sequence charts (MSC) are widely used in the early design of
  communication protocols. They allow describing the communication skeleton of a
  system. We consider a basic verification task for MSC graphs, the
  matching problem via MSC templates. We characterize the complexity
  of checking properties which are expressible by and-or templates,
  resp.~by LTL formulas. Both problems are shown to be PSPACE-complete.
\end{abstract}