Formal Test Purposes and The Validity of Test Cases\thanks{This paper appeared in the proceedings of the 22nd IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE 2002), number 2529 Lecture Notes in Computer Science.}
Peter H. Deussen
Fraunhofer FOKUS
Berlin
Germany
Stephan Tobies
Nokia Research Center
Bochum
We give a formalization of the notion of test purpose based on (suitably restricted) Message Sequence Charts. We define the validity of test cases with respect to such a formal test purpose and provide a simple decision procedure for validity.
appendix.tex












  













































\section{Appendix}

This appendix contains the proofs of
Theorems~\ref{theo:valid-tester-exists} and \ref{theorem:alg-correct}
(for technical reason in reverse order).  In the following, let
$\mathscr{M}$ denote a well-formed test purpose.

From property \ref{enum:wf2} we get that the function $\delin(\cdot):
\obs(X_{\mathscr{M}}) \rightarrow X_{\mathscr{M}}$
that maps
every $\sigma \in \obs(X_{\mathscr{M}})$ to a $\mathbit{x}_\sigma \in
X_{\mathscr{M}}$ such that $\sigma \in \lin(\mathbit{x}_\sigma)$ is in
fact a well-defined and total. It is easy to show the following
property:

\begin{lemma}\label{lemma:pre-invariance}
  Let $\mathscr{M}$ be a well-formed test purpose and $\rho,\sigma \in
  \obs(X_{\mathscr{M}})$ with $\rho \leq \sigma$. Then $\delin(\rho)
  \leq \delin(\sigma)$.
\end{lemma}

Let $\mathscr{M}$ be a well-formed test purpose, $\TS$ a test case for
$\mathscr{M}$ and $\sigma \in L_{\mathscr{M}}$ with
$\ver_{\mathscr{M}}(\sigma) \neq \Vnone$. A \emph{validation} for
$\sigma$ is a complete run $\rho_0 \xrightarrow[\TS]{} \rho_1
\xrightarrow[\TS]{} \cdots \xrightarrow[\TS]{} \rho_n$ such that
$\rho_n \simeq_{L_{\mathscr{M}}} \sigma$ and $\ver_\TS(\rho_n) =
\ver_{\mathscr{M}}(\sigma)$.
  
It is easy to see that validity of a test case w.\,r.\,t.\ a test purpose can
equivalently be formulated as follows.



\begin{lemma}\label{lemma:validation-run}
  Let $\mathscr{M}$ be a well-formed test purpose and $\TS$ a test
  case for $\mathscr{M}$. Then $\TS$ is valid w.\,r.\,t.
  $\mathscr{M}$ iff every $\sigma \in L_{\mathscr{M}}$ has a
  validation.
\end{lemma}

We will need the following technical lemma:

\begin{lemma}\label{lemma:prefer-send-action}
  Let $\mathscr{M}$ be a well-formed test purpose,
  $a, b \in \ObsAlph$ be actions, and $\rho,\sigma \in \ObsAlph^*$.
  Moreover, assume $\rho a, \rho b \in L_{\mathscr{M}}$,
  $\ver_{\mathscr{M}}(\sigma) \neq \Vnone$, and
  $\rho b \leq \sigma$. If $a \not\in \ObsSend$ or $b \not\in \ObsSend$ (or both),
  then there exists a $\sigma' \in
  L_{\mathscr{M}}$ with $\sigma \simeq_{L_{\mathscr{M}}}
  \sigma'$, $\ver_{\mathscr{M}}(\sigma) =
  \ver_{\mathscr{M}}(\sigma')$, $\rho a \leq \sigma'$, and
  $\ver_{\mathscr{M}}(\sigma) = \ver_{\mathscr{M}}(\sigma')$.
\end{lemma}


\begin{proof}
  Let $a,b,\rho,\sigma$ as required by the lemma and let $\mathbit{x}
  = \delin(\rho)$, and $\mathbit{z} = \delin(\sigma)$.  Let
  $\mathbit{y}_a, \mathbit{y}_b \in X_{\mathscr{M}} \res \ObsAlph$ such
  that $\mathbit{y}_a = \mathbit{x} \wsc{\ComSym} a$ and
  $\mathbit{y}_b = \mathbit{x} \wsc{\ComSym} b$. From \ref{enum:wf2} we
  get $\mathbit{x} \leq \mathbit{y}_b \leq \mathbit{z}$. From
  \ref{enum:wf3}, also $\mathbit{x} \leq \mathbit{y}_a \leq
  \mathbit{z}$ holds. Hence, there exists $\mathbit{u} \in
  X_{\mathscr{M}} \res \ObsAlph$ with $\mathbit{u} = \mathbit{x}
  \wsc{\ComSym} a \wsc{\ComSym} b$ and $\mathbit{u} \leq
  \mathbit{z}$ and we obtain $\sigma'$ setting $\sigma' = \rho a b
  \eta$, where $\eta$ is the string that can be appended to $\rho b$
  to obtain $\sigma$ with the first occurrence of $a$ deleted.  From
  what have said before, $\sigma'$ is a linearization of
  $\mathbit{z}$, hence $\sigma \simeq_{L_{\mathscr{M}}} \sigma'$ 
  and $\ver_{\mathscr{M}}(\sigma) =
  \ver_{\mathscr{M}}(\sigma')$.
\end{proof}


\begin{proof}[Proof of Theorem \ref{theorem:alg-correct}]
 Assume
  that {\bit valid}$(\mathscr{M},\TS,\epsilon)$ does not fail and let
  $\sigma \in L_{\mathscr{M}}$ with $\ver_{\mathscr{M}}(\sigma) \neq
  \Vnone$ and $|\sigma| = n$. By Lemma~\ref{lemma:validation-run}, it
  suffices to show that there exists a validation of $\sigma$. To this
  purpose, we will construct sequences $\rho_0,\dots, \rho_n$ and
  $\sigma_0, \dots, \sigma_n$ such that $|\rho_i| = i$, {\bit
    valid}$(\mathscr{M}.\TS,\rho_i)$ is called during the execution of
  the algorithm, $\rho_i \leq \sigma_i$, $\sigma_i
  \simeq_{L_\mathscr{M}} \sigma$, and
  $\ver_{\mathscr{M}}(\sigma) = \ver_{\mathscr{M}}(\sigma_i)$, for
  each $0 \leq i \leq n$.
  
  We start with $\rho_0 = \epsilon$ and $\sigma_i = \sigma$, which
  satisfies all the required properties. Assume that the sequences
  have been constructed up to $i$. Since {\bit
    valid}$(\mathscr{M},\TS,\rho_i)$ does not fail, $\rho_i \in
  L_{\mathscr{M}}$ holds and there are the following possibilities:
  \begin{itemize}
  \item $\TS(\rho) \in \FinVerdicts \And \TS(\rho) =
    \ver_{\mathscr{M}}(\rho)$. In this case, $|\rho| = n$ must hold
    because otherwise $\ver_{\mathscr{M}}(\sigma_i) \neq \Vnone$ and
    $\ver_{\mathscr{M}}(\rho_i) \neq \Vnone$, together with $\rho_i <
    \sigma_i$, would be (by Lemma~\ref{lemma:pre-invariance}) a
    contradiction to the fact that $\ver_{\mathscr{M}}$ is a verdict
    assignment on $L_{\mathscr{M}}$.
  \item $\TS(\rho) = \delta \And \ ${\bit en}$(\MS,\rho) \cap \ObsRec \neq
    \emptyset$. Then $i < n$ must hold and since $\rho_i < \sigma_i$,
    there exists $b \in \Ev(T)$ such that $\rho_i b \leq \sigma_i$. If
    $b \in \ObsRec$ then there will be a call {\bit
      valid}$(\mathscr{M},\TS,\rho_i b)$ and we set $\rho_{i+1} \df
    \rho_i b$ and $\sigma_{i+1} \df \sigma_i$ to continue the
    sequences.  Clearly, this satisfies all necessary properties. If
    $b \in \ObsSend$ then let $a \in \text{\bit en}(\MS,\rho_i) \cap
    \ObsRec$. Then $a, b, \rho_i, \sigma_i$ satisfy the
    prerequisites of Lemma~\ref{lemma:prefer-send-action}, which
    yields the existence of $\sigma_i' \in L_\mathscr{M}$ with
    $\sigma_i \simeq_{L_{\mathscr{M}}} \sigma_i'$,
    $\ver_{\mathscr{M}}(\sigma_i) =\ver_{\mathscr{M}}(\sigma_i')$, and
    $\rho_i a \leq \sigma_i'$. If we set $\rho_{i+1} \def \rho_i a$
    and $\sigma_{i+1} \df \sigma_i'$ then we have extended the
    sequence as required.
    \item $\TS(\rho) = a \in \ObsSend \And \rho a \in
      L_{\mathscr{M}}$. In this case we necessarily have to set
      $\rho_{i+1} \df \rho_i a$ and we need to show the existence of a
      suitable $\sigma_{i+1}$. This can be done similar to the
      previous case using Lemma~\ref{lemma:prefer-send-action}.
  \end{itemize}
  
  It is easy to see that $\TS(\rho_n) \in \FinVerdicts$ and by
  construction it holds that $\rho_n \simeq_{L_{\mathscr{M}}}
  \sigma$ as well as $\ver_{\TS}(\rho_n) = \ver_{\mathscr{M}}(\sigma)$.
  Moreover, obviously $\rho_0 \xrightarrow[\TS]{} \cdots \xrightarrow[\TS]{}
  \rho_n$ is complete run and thus we have found the desired
  validation for $\sigma$.
  
  For the converse direction, let $\TS$ be a test case that is valid
  w.\,r.\,t.\ $\mathscr{M}$. We need to show that the call {\bit
    valid}$(\mathscr{M},\TS, \epsilon)$ does not fail. Hence assume
  that is does fail and let $\rho \in L_{\mathscr{M}}$ a
  prefix-maximal word such that {\bit valid}$(\mathscr{M},\TS,\rho)$
  is evaluated. By definition of {\bit valid}, $\rho in L_\MS$ must
  holds.  One of the following choices for $\rho$ is the one that
  leads to failure.
  \begin{itemize}
  \item $\TS(\rho)$ is undefined, then obviously, for every $\sigma
    \in L_{\MS}$ with $\rho \leq \sigma$, $[\sigma]_{L_\MS} \cap
    L_{\TS} = \emptyset$.
  \item  $\TS(\rho) \in \FinVerdicts$ and $\TS(\rho)
    \neq \ver_{\mathscr{M}}(\rho)$, which violates the first condition
    in the definition of test case validity.
  \item $\TS(\rho) = \delta$ and {\bit en}$(\MS,\rho) \cap \ObsRec =
    \emptyset$. If $\ver_{\mathscr{M}}(\rho) \neq \Vnone$ then $L_{\TS}$
    and $L_{\mathscr{M}}$, then again the first condition of the
    definition of test case validity is violated. If
    $\ver_{\mathscr{M}}(\rho) = \Vnone$ then there exists $\sigma \in
    L_{\mathscr{M}}$ with $\ver_{\mathscr{M}}(\sigma) \neq \Vnone$ and
    $\rho < \sigma$. It is easy to see that, if there exists $\eta \in
    [\sigma]_{L_{\mathscr{M}}} \cap L_{\TS}$, then $\rho <
    \eta$, but since $\TS(\rho) = \delta$ and {\bit en}$(\MS,\rho) \cap
    \ObsRec = \emptyset$, for every $\chi \in L_{\TS}$ with $\rho < \chi$,
    $\chi \not \in L_{\mathscr{M}}$ holds and hence the does not
    exists such a $\eta$.
  \item The case that $\TS(\rho) = a \in \ObsSend$ but $\rho
    \cdot a \not \in L_{\mathscr{M}}$ is analog to the previous case.
  \end{itemize}
  
  Hence, {\bit valid}$(\mathscr{M},\TS,\epsilon)$ cannot fail.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{theo:valid-tester-exists}]
  We define a test case $\TS$ as follows: for $\sigma \in
  \obs(X_{\mathscr{M}})$:
  \begin{gather*}
  \TS(\sigma) \df 
  \left\{\begin{array}{l} 
    \ver_{\mathscr{M}}(\delin(\mathbit{x})), 
      \text{if {\bit en}$(\MS,\sigma) = \emptyset$};\\
    \delta, \text{if $\emptyset \neq \text{\bit en}(\MS,\sigma) \subseteq \ObsRec$}\\
    a, \text{ for an arbitrary $a \in \text{\bit en}(\MS,\sigma) \cap \ObsSend$ otherwise}
  \end{array}\right.
  \end{gather*}
  
  It is easy to see that for this test case $\TS$, {\bit valid}$(\MS,\TS,\epsilon)$
  does indeed not fail and hence, by
  Theorem~\ref{theorem:alg-correct}, $\TS$ is a valid test case w.\,r.\,t.\ 
  $\MS$.
\end{proof}









corr.tex


\documentclass{article} % Computer Modern font calls
\usepackage{viva2}
\usepackage{url}
\usepackage{epsfig}
\usepackage{array}
\usepackage{times}

\def\bit{\bfseries}








































\setcounter{secnumdepth}{3}







\setcounter{tocdepth}{3}








\let\lcitebracket(
\let\rcitebracket)









\begin{document}

\title{Formal Test Purposes and The Validity of Test Cases\thanks{This paper appeared in the proceedings of the 22nd IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE 2002), number 2529 Lecture Notes in Computer Science.} }

\author{Peter H. Deussen\\Fraunhofer FOKUS, Berlin, Germany\\ \texttt{deussen@fokus.fhg.de} 
  \and Stephan Tobies\\ Nokia Research Center, Bochum, Germany\\ \texttt{Stephan.Tobies@nokia.com}}


\maketitle

\vspace{-.5cm}

\begin{abstract}
  We give a formalization of the notion of test purpose based on
  (suitably restricted) Message Sequence Charts. We define the validity of
  test cases with respect to such a formal test purpose and provide a simple
  decision procedure for validity.
\end{abstract}






\renewcommand{\epsilon}{\varepsilon}

\newtheorem{algorithm}{Algorithm}{\bfseries}{\itshape}
\newtheorem{lemma}{Lemma}{\bfseries}{\itshape}
\newtheorem{theorem}{Theorem}{\bfseries}{\itshape}
\newtheorem{proof}{Proof}{\itshape}{\rmfamily}


\input{intro.tex}
\input{msc.tex}
\input{validity.tex}

\input{implementation.tex}
\input{outlook.tex}



\input{appendix.tex}




\bibliographystyle{abbrv}
\bibliography{viva2}


\end{document}






implementation.tex


\section{Practical Considerations}
\label{section:implementation}

The previous sections have discussed formally the relationship between
a test purpose defined using MSC and a test system that implements the
test purpose. No assumptions have been made on the test system besides
that it is deterministic and that it has observable test events and a
final verdict status.  An MSC based validator tool has been designed
and developed within a joint project between Nokia Research Center and
Fraunhofer FOKUS.

The validator is designed to run against any test system that provides
some basic functionality, like starting of a test case, retrieving the
status of the final verdict, sending and receiving messages, etc. The basic
idea was to create a validator that is not only able to validate the
abstract test suite but also a real test system (tester), i.\,e., an
abstract test suite plus its execution environment plus the glue that
is necessary to tie the test suite to the actual system under test.
Since this glue can be of considerable complexity, e.g., consisting of
implementations of various protocol stacks, message en- and decoders,
possibly tailored hardware, etc., testing of the whole test system is
indeed an important aspect.

This is also one of the advantages of our approach as compared to other
approaches like an isolated verification of the abstract test suite or
an automatic generation of test cases from test purposes.

Given a sufficiently detailed specification of the test purpose, a
combination of automatic generation of test cases
\cite{schmitt00:_test_gener_autol_testc} from the test purpose
together with a validation following our approach seems optimal. The
validation guarantees both the correctness of the implementation of
the generation algorithm and of the additional components that make up
the test system.










































The design of the validator aims to make it as independent of the test
system as possible by defining a small, well-defined interface to
connect the validator to the test system. In our case study we have
used a TTCN-3 test system with the MSC validator. The validator accesses
the test system at its (proprietary) control interface to trigger the
execution of testcases and retrieve the final verdict. It uses
TTCN-3's standardized communication interface toward the
SUT~\cite{schhulz02:_implem_ttcn_test_system_tri} to exchange messages
with the test system. The MSC validator has been implemented using
JAVA and the test system runs independently of the validator.
Although not all work within this project has been completely
finished, results so far show that using MSCs as test purpose
definition language and as basis for the test case validation can
improve the quality of test cases and thus the quality of system
implementations.










intro.tex


\section{Introduction} 

The quality of a test system directly influences the quality of the
tested implementation: high quality test systems are essential to
obtain high quality implementations.  Hence, a common problem in the
testing area is the so-called ``test the tester''
problem \cite{scheurer98:_revis_compar_autom_gener_manual}: how can the
validity of a test system with respect to a given specification, and
therefore the quality of the test system, be assured? To put it in
conformance testing terminology: how can it be assured that a test
case achieves its test purpose?

One approach used to obtain valid test systems is the derivation of
test cases from formal specifications or test purpose definitions. Other
approaches focus on the manual or automated simulation against a
formal specification (see \cite{schmitt00:_test_gener_autol_testc} for
a description of tools that employ these two approaches).  While many
modern telecommunication protocols come with (semi-) formal
specifications of test purposes, a formal protocol description is
provided only in very few cases (see
\cite{grabowski00:_ttcn_sdl_msc_inap} for a notable exception).  For
example, Internet Protocols defined in RFCs use natural language to
define the semantics of the specification. Due to this, a formal
description of the specification would have to be elaborated to allow
for an automatic generation of valid test cases.  Additionally, even
if formal descriptions are available, automated generation methods
only generate test skeletons that need to be manually refined to
obtain executable test cases for the execution against a concrete system
implementation. For all these reasons, the implementation of test cases
is still performed mainly in a manual manner.

In this paper, we give a new answer to the ``test the tester
problem'', namely, to check the validity of a (possibly hand-written)
test case against a formal test purpose definition. It does not rely
on the existence of a formal description of the system under test
(SUT) or the test system, but requires a formally defined test
purpose. From this test purpose, the allowed and required behavior of
the test case is derived. This information is then used in a guided
simulation of the executable test system to determine whether the test
system is valid with respect to this test purpose. Since our approach
is solely based on test purposes, it is not necessary to develop a
complete formal specification of the system as test purposes are only
a partial description of the system. We use Message Sequence Charts
(MSC) as the formal test purpose description language \cite{ITU-Z120},
which is widely used in the system development process in the
telecommunication area. This allows for an easy re-use of the
uses-cases developed during system design as a solid basis for the
test purpose definition.  This further reduces the work necessary for
the test purpose specification.

Despite the fact that MSCs are widely used to capture test purpose,
theoretical studies of MSCs so far seem to have failed to address the
following issues:

\begin{itemize}
\item What does it mean for a test case to implement a test purpose,
  i.e., when is a test case \emph{valid} w.\,r.\,t.\ a test purpose?
\item When is an MSC a \emph{well-formed} test purpose, i.\,e., when
  does an MSC characterize behavior that is indeed (black-box)
  testable?
\end{itemize}

We address these issues using a semantics for MSC based on pomsets
\cite{pratt86,grabowski81} in the spirit of \cite{kat-lam98}. We then
describe a simple decision procedure for the validity of test cases w.\,r.\,t.\ 
a test purpose and prove its correctness.





















The paper is structured as follows: Section \ref{section:msc} of this
paper introduces the partial order semantics of MSCs and their usage
as formal test purposes.  In Section \ref{section:validity}, we define
test case validity, describe the decision procedure and prove its
correctness. Section~\ref{section:implementation} presents one
possible implementation design for an MSC based test validator.
Section \ref{section:outlook} concludes. Proofs of key lemmata and
theorems can be found in the appendix.

\endinput








msc.tex


\section{Formal Test Purposes}\label{section:msc}

To check (or even define) validity of a test case wrt.\ a test
purposes, we need a formal definition of a test purpose together with
suitable semantics. In this section, we suggest a formalism to formally
express test purposes and establish a set of criteria that guarantee
that a test purposes indeed describes (black-box) testable behavior.

We use Message Sequence Charts (MSCs) to express formal test purposes
because they are widely used to capture test purposes and semantics
based on different approaches are available. We have chosen semantics
based on pomsets~\cite{grabowski81,pratt86} in an adaption of the
definition of \cite{kat-lam98} to better suit our purposes. The
particular choice of semantics of MSCs in not central to our approach,
but obviously some choice has to be made. Using the more operational
semantics from \cite{mauw-reniers97,jonsson01:_execut_seman_msc} would
lead to similar results.

After a short overview on the employed MSC syntax for test purposes,
we recapitulate the pomset-based semantics of MSC and define when an
MSC constitutes as well-formed test purpose.

\paragraph*{Message Sequence Charts.}

\begin{figure}[t]
  \begin{center}
    \begin{footnotesize}
      \setmscvalues{small}
         \begin{tabular}{cc}
           \begin{msc}{\ensuremath{m_1}}
             \declinst{p}{}{$p$}
             \declinst{q}{}{$q$}
             \declinst{r}{}{$r$}
             \mess{$a$}{p}{q}\nextlevel
             \coregionstart{r} \nextlevel
               \mess{$b$~~~~~~~~~~~~~~~~~~}{p}{r} \nextlevel
               \mess{$c$}{q}{r} \order{q}{p}[2] \nextlevel
             \coregionend{r}\nextlevel
             \mess{$d$}{p}{q}\nextlevel
             \mess{$e$}{r}{envright}
           \end{msc}
         &
           \begin{msc}{\ensuremath{m_2}}
               \declinst{p}{}{$p$}
               \declinst{q}{}{$q$}
               \inlinestart{alt}{alt}{p}{q} \nextlevel
                   \mess{$a$}{p}{q}\nextlevel
                   \condition{$C_1$}{p,q}\nextlevel[2]
                   \inlineseparator{alt} \nextlevel
                   \mess{$b$}{q}{p}\nextlevel
                   \condition{$C_2$}{p,q}\nextlevel[2]
               \inlineend{alt}
           \end{msc}
         \end{tabular}
     \end{footnotesize}
   \end{center}
   \vspace*{-.5cm}
   \caption{\label{fig:intro-example}Example MSCs.}
   \vspace*{-.2cm}
\end{figure}


The MSCs in Fig. \ref{fig:intro-example} serves as an explanatory
example for the basic MSC language as used throughout this paper. The
most fundamental constructs of MSCs are {\em instances\/} and {\em
  messages}. Instances represent components or communication
interfaces that exhibit a sequential behaviour.  Our example MSC $m_1$
consists of three instances $p$, $q$, and $r$. A message exchange
between a sending instance $p$ and a receiving instance $q$ comprises
two {\em events\/} $\send{p, q}a$ and $\rec{p, q}a$ for sending the
message $a$ at $p$ and for receiving $a$ at $q$, respectively.
Graphically, messages are depicted by arrows between instances
labeled with messages.


Events are considered to be causally or temporally ordered only if
they are located at the same instance (in this case the ordering is
top-to-bottom), or if they are part of the same message exchange.  In
our example $m_1$, the event $\send{p, q}a$ precedes the
events $\rec{p, q}a$ and $\send{p, r}b$, but no assumption on an
ordering of the events $\send{p, r}b$ and $\send{q, r}c$ is expressed,
even if $\send{p, r}b$ is drawn above  $\send{q, r}c$.

There is a way to express the concurrency of events of the same
instance: the concurrent region ({\em coregion}, for short). Coregions
are depicted by dashed sections on the corresponding instance line
bordered by small horizontal bars: the events that occur on this
dashed section are supposed to happen in parallel. In our example,
the events $\rec{p, r}b$ and $\rec{q, r}c$ are temporally unrelated.
On the other hand, it is possible to use {\em general order\/} arrows
(dotted lines between events with an arrow head in their middle
section) to express causal orderings of events on different instances.
In $m_1$, the event $\send{q, r}c$ precedes $\send{p, q}d$.  Finally,
the MSC language allows to express message exchange with the
environment of a MSC; e.\,g. in $m_1$ the message $e$ is send to the
environment of this MSC.

The MSC formalism provides not only communication primitives but also
control structures. For our purposes, only the \emph{alt operator}.
modeling nondeterministic choice, is of importance. $m_2$ in Fig.
\ref{fig:intro-example} shows an example: A choice between sending $a$
from $p$ to $q$ and sending $b$ from $q$ to $p$ is expressed. A final
construct considered in this paper is that of {\em conditions}.
Conditions model global states or predicates related to more than on
instance; $m_2$ contains two conditions $C_1$ and $C_2$. It is not an
easy task to assign a formal meaning to conditions. However, we use
conditions only to express test verdicts and handle them formally in a
special way. We will discuss this topic in detail in a later section.

Other important concepts of the basic MSC language not covered in this
paper are: {\em loop inline expressions\/} (since tests are finite,
loops occurring in test purposes comprises alway finite, fixed
boundaries and therefore can be unfolded), and especially {\em
  timers}, which require extra considerations and will be dealt with
in forthcoming work.

\paragraph*{Expressing test purposes.}

We will use the MSC formalism to capture test
purposes in the following way: the set of instances is partitioned into a non-empty set of
port instances and a non-empty set of SUT instance. Intuitively, the
port instances represent the different ports (PCOs, interfaces) at
which the SUT interacts with its environment. Conditions that span the
port instances are used to assign the test verdicts.

The SUT instances are used as ``syntactic sugar'' and serve two
purposes: (1) as communication partners
 for the port instances, and
(2) to impose an ordering of the sequence of messages.  The same could
be achieved by using communication with the environment and
generalized orderings, but our approach leads to a more concise and
intuitive representation of the test purpose and matches the common usage.
Fig. \ref{fig:alternatives} shows the two alternative ways of
depicting a simple test purpose: after having received the message $a$
on both its ports $p$ and $q$ (in arbitrary order), the SUT answers by
sending the message $b$, again both on port $p$ and $q$. If the
message is sent on port $p$ before it is sent on port $q$ then the SUT
shall pass the test, otherwise it shall fail. We will come back to
this example later in this paper.

\begin{figure}[t]
  \begin{center}
    \begin{footnotesize}
      \setmscvalues{small}
       \begin{tabular}{cc}
         \begin{msc}{\protect{\ensuremath{m_3}}}

           \declinst{p}{}{$p$}
           \declinst{q}{}{$q$}
           \declinst{r}{}{$r$}
           \coregionstart{r} 
           \mess{$a$~~~~~~~~~~~~~~~~~~}{p}{r} \nextlevel
           \mess{$a$}{q}{r} \nextlevel
           \coregionend{r}\nextlevel
           \inlinestart{alt}{alt}{p}{r} \nextlevel
           \mess{~~~~~~~~~~~~~~~~~~$b$}{r}{p} \order{p}{q}[1] \nextlevel
           \mess{$b$}{r}{q} \nextlevel
           \condition{$\Vpass$}{p,q} \nextlevel[2]
           \inlineseparator{alt} \nextlevel
           \mess{$b$}{r}{q} \order{q}{p}[1] \nextlevel
           \mess{~~~~~~~~~~~~~~~~~~$b$}{r}{p}  \nextlevel
           \condition{$\Vfail$}{p,q} \nextlevel[2]
           \inlineend{alt}
         \end{msc} &

         \begin{msc}{\ensuremath{m_3'}}
           \nextlevel
           \declinst{p}{}{$p$}
           \declinst{q}{}{$q$}
           \mess{$a$}{p}{envright} \order{p}{q}[8] \nextlevel
           \mess{$a$}{q}{envright}
        \order{q}{p}[2]\nextlevel
        \inlinestart{alt}{alt}{p}{q} \nextlevel
        \mess{~~~~~~~~~~~~~~~~~~$b$}{envright}{p} \order{p}{q}[1]\nextlevel
        \mess{$b$}{envright}{q} \nextlevel
        \condition{$\Vpass$}{p,q} \nextlevel[2]
        \inlineseparator{alt} \nextlevel
        \mess{$b$}{envright}{q} \order{q}{p}[1] \nextlevel
        \mess{~~~~~~~~~~~~~~~~~~$b$}{envright}{p} \nextlevel
        \condition{$\Vfail$}{p,q} \nextlevel[2]
        \inlineend{alt}
      \end{msc}
    \end{tabular}
    \end{footnotesize}
  \end{center}
  \vspace{-.5cm}
  \caption{\label{fig:alternatives}Expressing the same test purposes with and without SUT instances}
  \vspace*{-.2cm}
\end{figure}














    






          












          















\subsection{Partial Orders}

We quickly recapitulate how pomsets can be used to assign a semantics
to MSCs. We start by introducing the basic notations used throughout
this paper.

To avoid tedious notation, we fix the following convention: if a
structure $S = \<A, B, \ldots>$ is introduced, the components of $S$
will be denoted by $A_S, B_S, \ldots$

For some set $A$, $\Pow(A)$ is the set of all subsets of $A$.  For $R
\subseteq A \times B$ and $a \in A$, we denote the {\em image\/} of
$a$ under $R$ by $R(a) \df \{b \in B: a \mathrel{R} b\}$.  For $C
\subseteq A$ we define $R(C) \df \bigcup_{a \in C}R(a)$.  

The
\emph{inverse} $R^{-1}$ of a relation $R$, the identity relation
$\mathord{\id_A}$ on $A$, the relational composition $R \cdot S$ or
two relations $R,S$, the transitive closure $R^+$ of $R$, and the
reflexive-transitive closure $R^*$ of $R$ are defined in the usual
manner.
























\paragraph*{Lposets.} 
For the rest of this paper let us fix a finite alphabet
$\Sigma$.  A {\em labeled partial order\/} (lposet, for short) over
$\Sigma$ is a structure $x = \<E, \mathord<, \lambda>$ where $E$ is a
finite set of {\em events}, $\mathord< \subseteq E \times E$ is an
(irreflexive) partial order, and $\lambda: E \rightarrow \Sigma$ is a
labeling function.

Let $x$ be a lposet and let $e_1, e_2 \in E_x$. We use the following
notions: The {\em reflexive closure\/} of $<_x$ is $\mathord{\leq_x} \df
\mathord<_x \cup \id_{E_x}$.  Unrelated events are called {\em
concurrent\/}, i.\,e., $e_1 \co_x e_2 \dfeq e_1 \not\leq_x e_2 \And e_2
\not\leq_x e_1$, while related events are {\em in line}: $e_1 \li_x
e_2 \dfeq e_1 <_x e_2 \Or e_2 <_x e_1$.  





  The {\em downward closure\/} of a set
$D \subseteq E_x$ is $\dncl{D} \df \mathord{\leq^{-1}_x}(D)$. If $D =
\dncl{D}$ holds, then $D$ is called {\em downward closed\/} in $x$. By
$\cl(x)$ we denote the set of downward closed sets in $x$.  If $D
\subseteq E_x$, then $x[D] \df \<D, \mathord<_x \cap (D \times D),
\lambda\res D>$ is the lposet {\em generated by\/} $D$ in $x$ ($\lambda\res D$ denotes the
restriction of $\lambda$ to $D$).

\paragraph*{Pomsets.}
Lposets $x$ and $y$ over $\Sigma$ are called {\em isomorphic}, written $x \approx y$, if
there is a bijection $f: E_x \rightarrow E_y$ such 
that $(e_1 <_x e_2 \Leftrightarrow f(e_1) <_y f(e_2)) \And \lambda_x = \lambda_y \circ f$ holds.
A {\em partially ordered multiset\/} (a {\em pomset} for short) over $\Sigma$
is an isomorphism class of lposets, i.\,e., a set $[x] \df \{y: x
\approx y\}$.  We fix the convention, that pomsets are denoted by
boldfaced small letters $\mathbit{x}, \mathbit{y}, \mathbit{z}$.
Moreover $\mathbit{x}$ is assumed to be the equivalence class $[x]$ of
$x$. By this convention, $E_x$ always denotes the set of events of a
representative $x$ of $\mathbit{x}$.  The class of pomsets over
$\Sigma$ is denoted by $\Pomset(\Sigma)$.  

\begin{figure}[t]
\begin{center}
\grNogrid % use \grGrid to see where you are
\begin{gr}(0,-1)(8,3)

\grWindow[t](0,-.3){
\grEvent{a1}(0,1) \grEvLab[l]{$a$}
\grEvent{a2}(0,2) \grEvLab[l]{$a$}
\grLine{a1}{a2}
\grLine{c}{b3}
\grTextbox[b](0,.3){$\mathbit{x}$}
}

\grWindow[t](2,-.3){
\grEvent{a1}(0,1) \grEvLab[l]{$a$}
\grEvent{a2}(0,2) \grEvLab[l]{$a$}
\grEvent{b1}(1,1) \grEvLab[r]{$b$}
\grEvent{b2}(1,2) \grEvLab[l]{$b$}
\grEvent{b3}(1,3) \grEvLab[ur]{$b$}
\grEvent{c}(2,2.5) \grEvLab[r]{$c$}
\grLine{a1}{a2}
\grLine{b1}{b2}
\grLine{b1}{c}
\grLine{b2}{b3}
\grLine{b2}{c}
\grLine{c}{b3}
\grTextbox[b](1,.3){$\mathbit{y}$}
}

\grWindow[t](6,-.3){
\grEvent{a1}(.5,1) \grEvLab[l]{$a$}
\grEvent{a2}(0,2) \grEvLab[l]{$a$}
\grEvent{b1}(1.5,1) \grEvLab[r]{$b$}
\grEvent{b2}(1,2) \grEvLab[l]{$b$}
\grEvent{b3}(1,3) \grEvLab[ur]{$b$}
\grEvent{c}(2,2.5) \grEvLab[r]{$c$}
\grLine{a1}{a2}
\grLine{a1}{b2}
\grLine{b1}{b2}
\grLine{b1}{c}
\grLine{a2}{b3}
\grLine{b2}{b3}
\grLine{b2}{c}
\grLine{c}{b3}
\grTextbox[b](1,.3){$\mathbit{z}$}
}
\grTextbox[br](8,-1){\footnotesize$\begin{array}{rcl}
\Sigma &=& \{a, b, c\}\\
D &=& \{\<a, a>, \<b, b>, \<c, c>, \<b, c>, \<c, b>\}
\end{array}$} 
\end{gr}
\end{center}
\vspace{-.5cm}
\caption{\label{fig:pomsets}Example pomsets} 
\vspace{-.2cm}
\end{figure}

Fig. \ref{fig:pomsets} shows examples of pomsets. Graphically, we represent pomsets as directed acyclic
(not necessarily connected) graphs. Nodes are labeled with elements from the underlying alphabet $\Sigma$. 
Transitive arcs are sometimes omitted.

Let $\mathbit{x}, \mathbit{y} \in \Pomset(\Sigma)$ be pomsets. Then
$\mathbit{x}$ is called a {\em prefix\/} of $\mathbit{y}$---denoted
$\mathbit{x} \approximates \mathbit{y}$---iff there are
representatives $x \in \mathbit{x}$ and $y \in \mathbit{y}$ such that
$E_x \subseteq E_y \And \cl(x) \subseteq \cl(y)$ holds.  If there are
representatives $x \in \mathbit{x}$ and $y \in \mathbit{y}$ such that
$E_x = E_y \And \mathord<_x \subseteq \mathord<_y$ holds, then
$\mathbit{x}$ is called {\em less sequential\/} than $\mathbit{y}$.
This is denoted by $\mathbit{x} \seq \mathbit{y}$.  It is easy to see
that both $\approximates$ and $\seq$ partially order
$\Pomset(\Sigma)$. In Fig. \ref{fig:pomsets}, $\mathbit{x}
\approximates \mathbit{y}$, $\mathbit{x} \approximates \mathbit{z}$,
and $\mathbit{y} \seq \mathbit{z}$, holds.

An alternative definition of the prefix relation $\approximates$ and the ordering by
the degree of sequentiality $\seq$ can be obtained by introducing
the notion of {\em weak homomorphisms\/} between representatives of
pomsets \cite{deussen98a}. 





Special pomsets that will be encountered in this paper are:
\begin{enumerate}
\item Letters $a = [\{a\}, \emptyset, a \mapsto a]$ for $a \in \Sigma$ (we abuse
      $a, b, c, \ldots$ to denote both letters from $\Pomset(\Sigma)$ and
      from $\Sigma$).

\item Strings $[\{0, \ldots, n-1\}, \mathord<, i \mapsto a_i]$ for $a_0a_1\ldots a_{n-1} \in \Sigma^*$, where $<$ denotes the standard order relation on integers.




\item The empty word $\epsilon = [\emptyset, \emptyset, \emptyset]$. 
\end{enumerate} 
In this paper we do not distinguish between strings and pomset strings, i.\,e, if
$\Sigma$ is an alphabet then $\Sigma^*$ is considered to be the set of pomsets $\sigma$ over
$\Sigma$ such that $<_\sigma$ is a total ordering.

If $\mathbit{x} \in \Pomset(\Sigma)$, then by $\lin(\mathbit{x}) \df \{\sigma \in \Sigma^*: \mathbit{x} \seq \sigma\}$
we denote the set of {\em linearizations\/} of $\mathbit{x}$. 
 
\paragraph*{Dependencies and Weak Sequential Composition.}
A reflexive and symmetric relation $D \subseteq \Sigma \times \Sigma$
is called a {\em dependence\/} on $\Sigma$; for the rest of this paper
let $D$ be a dependence on $\Sigma$.  If $\mathbit{x}$ and
$\mathbit{y}$ are lposets over $\Sigma$, such that $E_{\mathbit x} \cap E_{\mathbit y} =
\emptyset$ holds, then the {\em weak sequential composition\/}
$\mathbit{x} \wsc{D} \mathbit{y}$ is defined by
\begin{eqnarray*}
\mathbit{x} \wsc{D} \mathbit{y} &\df& [E_{\mathbit x} \cup E_{\mathbit y}, (\mathord<_{\mathbit x} \cup \mathord<_{\mathbit y} \cup R)^+, \lambda_{\mathbit x} \cup \lambda_{\mathbit y}],
\end{eqnarray*}
where $R \subseteq E_{\mathbit x} \times E_{\mathbit y}$ is given by $e_1 \mathrel{R} e_2
\dfeq \lambda_{\mathbit x}(e_1) \mathrel{D} \lambda_{\mathbit y}(e_2)$.









A pomset $\mathbit{x}$ is called {\em $D$-consistent\/} if we have,
for all $e_1, e_2 \in E_x$, $e_1 \co_x e_2 \Rightarrow
\neg\lambda_x(e_1) \mathrel{D} \lambda_x(e_2)$. Let $\Pomset(\Sigma,
D)$ denote the class of $D$-consistent pomsets. Clearly, if
$\mathbit{x}$ and $\mathbit{y}$ are $D$-consistent, then also
$\mathbit{x} \wsc{D} \mathbit{y}$ is.  





Another operation on pomsets which is closely related to $\wsc{D}$ is
the {\em unsequentialization\/} via $D$: If $\mathbit{x} \in
\Pomset(\Sigma)$, then by $\unseq{\mathbit{x}}$ we denote the pomset
$[E_x, R^+, \lambda_x]$, where $R \subseteq E_x \times E_x$ is defined
by $e_1 \mathrel{R} e_2 \dfeq e_1 \leq e_2 \And \lambda_x(e_1)
\mathrel{D} \lambda_x(e_2)$.
\footnote{The operations $\wsc{D}$ and
  $\unseq{\cdot}$ impose an interesting and fruitful connection to the
  theory of Mazurkiewicz traces \cite{maz95}.  Although it is far
  beyond the scope of this paper it should be noted that pomsets of
  the form $\unseq{\mathbit{x}} \in \Pomset(\Sigma, D)$ are just
  alternative representations of Mazurkiewicz traces: in fact we have
  that $\lin(\unseq{\mathbit{x}})$ is a Mazurkiewicz trace over
  $\Sigma$ and $D$; moreover, the operation $\wsc{D}$ coincides with
  trace concatenation.  }

The pomsets in Fig. \ref{fig:pomsets} are all $D$-consistent for the dependence
$D$ shown in that figure. We have $\unseq{\mathbit{z}} = \mathbit{y}$.

The following lemma justifies the relation between the operations
$\wsc{D}$ and $\unseq{\cdot}$.

\begin{lemma}\label{lemma:unseq}
Let $\mathbit{x}, \mathbit{y}$ in $\Pomset(\Sigma)$.
Then $\unseq{\mathbit{x} \wsc{D} \mathbit{y}} = \unseq{\mathbit{x}} \wsc{D} \unseq{\mathbit{y}}$.
\end{lemma}































Some more definitions: if $A \subseteq \Sigma$ is a set of symbols and
$\mathbit{x}$ is a pomset, then $\mathbit{x}\res A \df
[x[\lambda^{-1}_x(A)]]$.  $\mathbit{x}\res A$ is called the {\em
  restriction of $\mathbit{x}$ to $A$}, i.e., $\mathbit{x}$ restricted
to those events labeled with elements from $A$. Finally, a set of
pomsets $X \subseteq \Pomset(\Sigma)$ is called {\em pre-closed\/} if
$\mathbit{x} \in X \And \mathbit{y} \approximates \mathbit{x}
\Rightarrow \mathbit{y} \in X$ holds.

 













\subsection{Partial Order Semantics for MSCs}

\setlength{\levelheight}{.5cm} \setlength{\inlineoverlap}{1.2cm}
\setlength{\conditionheight}{.4cm} \setlength{\instheadheight}{.4cm}
\setlength{\lastlevelheight}{.1cm}

\begin{figure}[t]
\begin{center}
\begin{footnotesize}
  \setmscvalues{small}
























      \begin{msc}{\ensuremath{m_4}}
        \declinst{p}{}{$p$}
        \declinst{q}{}{$q$}
        \declinst{r}{}{$r$}
        \coregionstart{r} \nextlevel
        \mess{$a$~~~~~~~~~~~~~~~~~~}{p}{r} \startlabel[r]{$\send{p, r}a$}\endlabel[l]{$\rec{p, r}a$} \nextlevel
        \mess{$a$}{q}{r} \startlabel[r]{$\send{q, r}a$}\endlabel[l]{$\rec{q, r}a$} \nextlevel
        \coregionend{r} \nextlevel
        \mess{~~~~~~~~~~~~~~~~~~$b$}{r}{p} \startlabel[l]{$\send{r,p}
          b$} \endlabel[r]{$\rec{r,p} b$} \nextlevel
        \mess{$0$}{p}{q} \startlabel[r]{$\send{p, q}0$}\endlabel[l]{$\rec{p, q}0$} \nextlevel[2]
        \mess{$b$}{r}{q} \startlabel[l]{$\send{r, q}b$}\endlabel[r]{$\rec{r, q}b$} \nextlevel
        \condition{$\Vpass$}{p,q} \nextlevel
      \end{msc}

















    
\end{footnotesize}
\end{center} 
\vspace*{-.5cm}
\caption{\label{fig:msc}An annotated MSC.}
\vspace*{-.2cm}
\end{figure}




To define the semantics of MSCs based on pomsets, we first need to fix
an alphabet $\Com\Sigma$ and a dependence $\Com D$ on $\Com\Sigma$.

\paragraph*{Communication Alphabet and Dependence.} 

Let $M$ be a set of {\em messages \/} and $P$ a set of {\em
  instances\/} fixed throughout this paper.  We assume that there is a
non-empty set $T \subset P$ of {\em port instances}; the instances
in $P - T$ will be called {\em SUT instances}.  Usually we will have
$|P - T| = 1$, but the theory presented in the following does not rely
on this.

Let $\Sigma_{\SendSym}, \Sigma_{\RecSym}$ 
be the two alphabets:
\begin{enumerate}
\item $\Sigma_{\SendSym} \df \{\SendSym\} \times P \times M \times P$
  is the set of {\em send actions}. Its elements $\<\SendSym, p, m,
  q>$ will be denoted by $\send{p, q}m$,
\item $\Sigma_{\RecSym} \df \{\RecSym\} \times P \times M \times P$ is
  the set of {\em receive actions}.  Its elements $\<\RecSym, p, m, q> \in
  \Sigma_?$ will be denoted by $\rec{p, q}m$.
\end{enumerate}

We put $\Com\Sigma \df \Sigma_{\SendSym} \cup \Sigma_{\RecSym}$ % \cup \Sigma_{\LocSym}$
to be the set of {\em communications}. The mapping $\ins(a)$
identifies the {\em instance\/} of an action $a \in \Com\Sigma$,
i.\,e.,  $\ins(\send{p, q}m) \df p$ and $\ins(\rec{p, q}m) \df q$. We
put $\ObsAlph \df \{a \in \Com\Sigma: \ins(a) \in T\}$ to be the set
of {\em tester observable actions}. For convenience, we furthermore
define $\ObsSend \df \ObsAlph \cap \Sigma_{\SendSym}$ and $\ObsRec \df
\ObsAlph \cap \Sigma_{\RecSym}$.

Fig. \ref{fig:msc} gives a few examples of this syntax of actions. It
shows the expansion of the first alternative of $m_4$ where the
generalized ordering has been replaced by sending the void message
$0$. The messages have been annotated with the corresponding symbols
from $\Com\Sigma$.

To build pomsets from actions, we define the dependence $\Com D$ on
$\Com\Sigma$: let $\Com D \subseteq \Com\Sigma \times \Com\Sigma$ be
the smallest reflexive, symmetric relation containing:
\begin{itemize}
\item $\<a, b>$ with  $\ins(a) = \ins(b)$ and $a$ and $b$ are not
  placed on the same co-region,
\item $\<\send{p, q}m, \rec{p, q}m>$ for instances $p, q \in P$ and
  messages $m \in M$.
\end{itemize}


To keep things simple, we restrict ourself to the following MSC
operators: message sending and receiving, co-regions, and the
alternative inline expression, which allows the expression of optional
behavior and finite iterations.  We simulate general ordering by
sending a void message $0$, which might also be sent between two
port or SUT instances.  Conditions are only allowed to assign
verdicts and are not dealt with by the semantics. In order to obtain a
set of $\Com D$-consistent pomsets, we have to impose the restriction
that identical actions (e.\,g. sending of a message twice from an
instance $p$ to an instance $q$) are not placed on the same co-region.


The semantics of an MSC $\mathscr{M}$ is given by a pre-closed set
of pomsets $X_{\mathscr{M}} \subseteq \Pomset(\Com\Sigma, \Com D)$.
We illustrate the construction of $X_{\mathscr{M}}$ only by informal
means of an example ($m_3$ from Fig.~\ref{fig:alternatives}); the
translation is done similar to \cite{kat-lam98} with slightly
different syntax for events of pomsets.



In the following, $\wsc\ComSym$ abbreviates $\wsc{\Com{D}}$.

                                %\mathbit{x} &\df& \send{p, r}a \wsc{\ComSym} \send{p, q}0 \wsc{\ComSym} \rec{p, r}{a} 







The semantics of our example $m_3$  is  given by the set
$X_{m_3}$:
\begin{eqnarray*}
X_{m_3} &=& \{\mathbit{z} \in \Pomset(\Com\Sigma, \Com D): \mathbit{z} \approximates \mathbit{x} \wsc{\ComSym} \mathbit{y}_{1} \Or \mathbit{z} \approximates \mathbit{x} \wsc{\ComSym} \mathbit{y}_{2}\}.
\end{eqnarray*}
where $\mathbit{x}, \mathbit{y}_1$, and $\mathbit{y}_2$ are defined by:
\begin{eqnarray}
\mathbit{x} &\df& \send{p,r}a \wsc{\ComSym} \send{q,r}a \wsc{\ComSym} \rec{p,r}a \wsc{\ComSym} \rec{q,r}a \label{eqn:x}\\
\mathbit{y}_1 &\df& \send{r,p}b \wsc{\ComSym} \rec{r,p}b \wsc{\ComSym} \send{p,q}0 \wsc{\ComSym} \rec{p,q}0 \wsc{\ComSym} \send{r,q}b \wsc{\ComSym} \rec{r,q}b \label{eqn:y1}\\
\mathbit{y}_2 &\df& \send{r,q}b \wsc{\ComSym} \rec{r,q}b \wsc{\ComSym} \send{q,p}0 \wsc{\ComSym} \rec{q,p}0 \wsc{\ComSym} \send{r,p}b \wsc{\ComSym} \rec{r,p}b \label{eqn:y2}
\end{eqnarray}


Without a proof (which would require a more formal treatment of the
definition of $X_{\mathscr{M}}$ we state:

\begin{lemma}\label{lemma:msc-pomsets-are-least-sequential}
If $\mathscr{M}$ is a MSC, then $\xunseq{\mathbit{x}}{D_\ComSym} = \mathbit{x}$ for all $\mathbit{x} \in X_{\mathscr{M}}$.
\end{lemma}

\subsection{Message Sequence Charts as Test Purposes}

Now that we have explained how to assign semantics to an MSC, we
show how MSCs can be utilized as a formal language to express test
purposes. We discuss how the notion of a test verdict can be
integrated into an MSC and how it can be guaranteed that an MSC
specifies behavior that is amenable to black-box testing.

\paragraph*{Verdict assignments.}

Syntactically, a verdict assignment is expressed by a condition on the
port instances on the very end of each terminal alternative of the
MSC. Semantically, the condition-like constructs pass, fail, and
inconc are not treated as an ordinary condition but as a convenient
way to define a \emph{verdict assignment}: \footnote{Alternatively,
  one could allow verdict conditions to appear also at other places
  within the MSC and, e.g., use the verdict assignment rules of TTCN-3
  \cite{etsi01:TTCN3} to resolve the case where different verdicts are
  encountered during a single run through the MSC.}

Let  $\Verdicts \df \{\Vpass, \Vfail, \Vinconc, \Vnone\}$ be a set of
{\em verdicts\/} and let $\FinVerdicts \df V -\{\Vnone\}$ be the set
of {\em final verdicts}.  A mapping $\ver: X \rightarrow V$ for some
finite, pre-closed set of pomsets $X$ is called a {\em verdict
  assignment\/} to $X$ if, for all $\mathbit{x} \in X$, we have:
\begin{enumerate}
\item $\exists \mathbit{y} \in X. \mathbit{x} \approximates
  \mathbit{y} \And \ver(\mathbit{y}) \neq \Vnone$, i.\,e., every pomset
  can be extended to a pomset that is assigned a final verdict, and
\item $\ver(\mathbit{x}) \neq \Vnone \Rightarrow \forall \mathbit{y}
  \in X. \mathbit{x} \not< \mathbit{y}$, i.\,e., pomsets that are
  assigned a final verdict are maximal in $X$.





\end{enumerate}

The verdict conditions drawn in an MSC $\mathscr{M}$ are used to define
a verdict mapping $\ver_{\mathscr{M}}$. Again, we introduce this
informally by the example of $m_3$ from Fig.~\ref{fig:alternatives},
where $\ver_{m_1}$ is defined by:
\begin{eqnarray*}
\ver_{m_3}(\mathbit{z}) &=& \begin{cases}
                           \Vpass, & \text{if } \mathbit{z} = \mathbit{x} \wsc{\ComSym} \mathbit{y}_{1};\\
                           \Vfail, & \text{if } \mathbit{z} = \mathbit{x} \wsc{\ComSym} \mathbit{y}_{2};\\
                           \Vnone, & \text{otherwise.}
                   \end{cases}
\end{eqnarray*}


It is obvious that not every MSC that satisfies the syntactic
restrictions that have been introduced above constitutes a test
purpose, i.\,e., describes behavior of the SUT that can be tested in a
black box testing approach. For example consider a modification of
$m_3$ from Fig.~\ref{fig:alternatives}, where the generalized ordering
constraints have been eliminated. There the verdict does not depend on
the order in which the messages $b$ can be observed at the ports of
the SUT but rather on the (SUT-internal) events that cause these
messages to be sent. Clearly, such an event is not visible to a
black-box test system and hence no test case can distinguish between
the behavior of the first and second alternative. In the following we
present a number of criteria that an MSC must satisfy to be
considered a \emph{well-formed} test purpose. Later we will see that
these criteria indeed guarantee the existence of a valid test case for
a test purpose.

\paragraph*{Well-Formed Test Purposes.}
First, we define a function that reduces the semantics of an MSC to
the information that is available to the test case, i.\,e., the sequences of
events that occur on port instances:

Given test purpose MSC $\mathscr{M}$ with semantics $X_{\mathscr{M}}$.
For $\mathbit{x} \in X_{\mathscr{M}}$, we define the \emph{tester
  observable traces} of $\mathbit{x}$ by $\obs(\mathbit{x}) \df
\lin(\mathbit{x} \res \ObsAlph)$. 




A MSC $\mathscr{M}$ is
called a \emph{well-formed test purpose} if it is possible to determine its state (and
hence assigned verdict) based on this information in its tester observable traces, i.\,e., if
\begin{enumerate}\def\theenumi{$\mathrm{WF}_{\text{\arabic{enumi}}}$}




\item\label{enum:wf2} for every $\mathbit{x}, \mathbit{y} \in X_{\mathscr{M}} \res
  \ObsAlph$, $\lin(\mathbit{x}) \cap \lin(\mathbit{y}) \neq \emptyset$ implies
  $\mathbit{x} = \mathbit{y}$.
\end{enumerate}


Unfortunately, this restriction does not yet suffice to guarantee that
an MSC describes testable behavior. Another aspect that needs
considerations is which party resolves \emph{essential choice} in the
sense of the following definition:

Let $X \subseteq \Pomset(\Com\Sigma, \Com D)$ be a pre-closed set of
pomsets. A pomset $\mathbit{x} \in X$ is called a \emph{choice point}
for two actions $a, b \in \Com\Sigma$ in $X$ if $\mathbit{x}
\wsc{\ComSym} a \in X$, $\mathbit{x} \wsc{\ComSym} b \in X$, and






\begin{eqnarray*}
\left\{\mathbit{y} \in \max{}_\approximates(X): \mathbit{x} \wsc{\ComSym} a \leq \mathbit{y}\right\}
   &\neq& \left\{\mathbit{y} \in \max{}_\approximates(X): \mathbit{x} \wsc{\ComSym} b \leq \mathbit{y}\right\} ,
\end{eqnarray*}
where $ \max_\approximates(X)$ denotes the $\approximates$-maximal pomsets in $X$.

Coming back to example from Fig.~\ref{fig:alternatives} with semantics
$X_{m_3}$ as defined in (\ref{eqn:x})--~(\ref{eqn:y2}), $\mathbit{x}
\res \ObsAlph$ is a choice point for $\rec{r,p}b$ and $\rec{r,q}b$. On
the other hand, $\epsilon$ is not a choice point even though there are
two ``available'' communications, namely $\send{p,r}a$ and
$\send{q,r}a$, since this choice does not alter the reachable maximal
configurations.









We require, for a well-formed test purpose, that each  choice point
is resolved by a message from the SUT:
\begin{enumerate}\setcounter{enumi}{1}\def\theenumi{$\mathrm{WF}_{\text{\arabic{enumi}}}$}
\item\label{enum:wf3} If $\mathbit{x}$ is a choice point of
  $X_{\mathscr{M}} \res \ObsAlph$ for actions $a, b \in \ObsAlph$,
  then both $a, b \in \ObsRec$.
\end{enumerate}

This restriction is necessary because both other possibilities for a
choice point ($a,b \in \ObsSend$ or $a \in \ObsSend$ and $b \in
\ObsRec$) are undesirable in a test purpose:
a choice that has to be resolved by the test case indicates
  that the test purpose should indeed be (at least) two test purposes,
  one for each choice of the test case. Otherwise, a deterministic
  test case will only be able to test the part of the test purpose
  that corresponds to the (necessarily fixed) way the test case
  resolves the choice.
On the other hand, a choice that can be resolved simultaneously by the test case and
  SUT leads to problems because it might lead to a race condition
  where both test case and SUT resolve the choice in an inconsistent
  manner. This situation bears strong resemblance to the presence of
  non-local choice in the MSC~\cite{benabdallah97syntactic}.

\begin{figure}[t]
  \centering
  \begin{footnotesize}
    \setmscvalues{small}
    \begin{tabular}{m{.34\linewidth}cm{.35\linewidth}}
      \begin{msc}{\ensuremath{m_5}}
        \declinst{p}{}{$p$}
        \declinst{r}{}{$r$}
        \mess{$a$}{r}{p} \nextlevel
        \inlinestart{alt}{alt}{p}{r} \nextlevel
        \mess{$b$}{p}{r} \nextlevel
        \condition{$\Vpass$}{p} \nextlevel[2]
        \inlineseparator{alt} \nextlevel
        \mess{$b$}{p}{r} \nextlevel
        \condition{$\Vfail$}{p} \nextlevel[2]
        \inlineend{alt}
      \end{msc}
      & &
      \begin{msc}{\ensuremath{m_6}}
        \declinst{p}{}{$p$}
        \declinst{r}{}{$r$}
        \inlinestart{alt}{alt}{p}{r} \nextlevel
        \mess{$a_1$}{r}{p} \nextlevel
        \mess{$b_1$}{p}{r} \nextlevel
        \condition{$\Vpass$}{p} \nextlevel[2]
        \inlineseparator{alt} \nextlevel
        \mess{$a_2$}{r}{p} \nextlevel
        \mess{$b_2$}{p}{r} \nextlevel
        \condition{$\Vpass$}{p} \nextlevel[2]
        \inlineseparator{alt} \nextlevel
        \mess{$c$}{p}{r} \nextlevel
        \condition{$\Vpass$}{p} \nextlevel[2]
        \inlineend{alt}
      \end{msc}
    \end{tabular}
  \end{footnotesize}
  \vspace*{-.2cm}
  \caption{Two malformed MSCs}
  \vspace*{-.2cm}
  \label{fig:malformed-mscs}
\end{figure}
  
Figure~\ref{fig:malformed-mscs} shows examples of malformed MSCs: in
$m_5$ exist $\mathbit{x}, \mathbit{y} \in X_{m_5}
\res \ObsAlph$ with $\mathbit{x} \neq \mathbit{y}$ and $\sigma =
\send{r,p}a \cdot \rec{p,r}b \in\lin(\mathbit{x}) \cap \lin(\mathbit{y})
\neq \emptyset$, and hence $\mathrm{WF}_1$ is violated. Indeed there
exist $\mathbit{x},\mathbit{y}$ with that property such that
$\ver_{m_5}(\mathbit{x}) = \Vpass$ and
$\ver_{m_5}(\mathbit{y}) = \Vfail$. Taking into account the
fact that a test system will only observe $\sigma$ it is clear that
$m_5$ does not describe testable behaviour---which verdict
should a test system assign after observing $\sigma$?  The MSC
$m_6$ is malformed because it violates $\mathrm{WF}_2$:
$\epsilon$ is a choice point for the actions $\send{r,p} a_1$,
$\send{r,p} a_2$, and $\send{p,r} c$. In its initial configuration,
the test system can either (deterministically) send $a_1$ or $a_2$,
but will then not be able to test the behaviour of the SUT that
corresponds to the respective other choice. Also, what happens if the
test system decides to perform action $\send{r,p} a_1$ while the SUT,
before it has received $a_1$, performs $\send{p,r} c$?  This
behaviour is not defined by the MSC.  For an example of a well-formed
MSC, the reader may verify that $m_3$ from Fig.~\ref{fig:alternatives}
is indeed well-formed.
































outlook.tex
 %%% $Id: outlook.tex,v 1.7 2001/09/14 11:28:57 tobies Exp $

\section{Future Work}
\label{section:outlook}

This paper defines a novel approach to test case validation and
provides the necessary theoretical background. Yet, it is only a first
step toward a working test case validation system. In particular, the
following issues need to be addressed in the future:

\paragraph*{Algorithms and Complexity.}

Deciding well-formedness of an MSC $\mathscr{M}$ so far requires the
calculation of the semantics $X_{\mathscr{M}}$, which is a costly
operation. A syntactic characterization of well-formedness would be
desirable because it would probably allow for faster tests for
well-formedness that could, e.g., also be built into an MSC editor to
support test purpose development by pointing out problematic
constructs. Additionally, a detailed analysis of the complexity of
well-formedness and test case validity would be desirable.

\paragraph*{Data.}

Since its last revision, data is an integral part of the MSC language.
An extension of our approach that also takes into account data passed
in messages is essential for the practical applicability of our
approach to a wider class of test cases. While this should not impose
any theoretical problems, it will be a challenge to integrate data
into the implementation in a user-friendly manner.

\paragraph*{Time.}

MSCs allow to express various timing constraints and timing aspects
are important in many testing efforts. Therefore, we plan to extend our
approach to MSCs with timing constraints. From a theoretical point of
view, this is probably the most interesting way to continue the work
presented in this paper.








pst-coil.tex
%% BEGIN pst-coil.tex
%%
%% Coils and zigzags with PSTricks 97.
%% See the PSTricks User's Guide for documentation.
%% For use with the PostScript header file `pst-coil.pro'.
%%
\def\fileversion{97 patch 2}
\def\filedate{1998/03/19}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\message{ v\fileversion, \filedate}
\csname PSTcoilsLoaded\endcsname
\let\PSTcoilsLoaded\endinput
\ifx\PSTricksLoaded\endinput\else
\def\next{\input pstricks.tex}\expandafter\next
\fi
\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11
\pstheader{pst-coil.pro}
\edef\pst@theheaders{\pst@theheaders,pst-coil.pro}
\def\pst@coildict{tx@CoilDict begin }
\def\psset@coilwidth#1{\pst@getlength{#1}\psk@coilwidth}
\psset@coilwidth{1cm}
\def\psset@coilheight#1{\pst@checknum{#1}\pscoilheight}
\psset@coilheight{1}
\def\psset@coilarmA#1{\pst@getlength{#1}\psk@coilarmA}
\def\psset@coilarmB#1{\pst@getlength{#1}\psk@coilarmB}
\def\psset@coilarm#1{%
\pst@getlength{#1}\psk@coilarmA
\let\psk@coilarmB\psk@coilarmA}
\psset@coilarm{.5cm}
\def\psset@coilaspect#1{\pst@getangle{#1}\psk@coilaspect}
\psset@coilaspect{45}
\def\psset@coilinc#1{\pst@getangle{#1}\psk@coilinc}
\psset@coilinc{10}
\def\pscoil{\def\pst@par{}\pst@object{pscoil}}
\def\pscoil@i{\pst@getarrows\pscoil@ii}
\def\pscoil@ii(#1){%
\@ifnextchar(%
{\pscoil@iii{1}(#1)}%
{\pscoil@iii{\z@}(0,0)(#1)}}
\def\pscoil@iii#1(#2)(#3){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#3}\pst@tempb
\pst@optcp{#1}\pst@tempa
\addto@pscode{%
\pst@tempa \pst@tempb
\psk@coilwidth \pscoilheight
\psk@coilarmA \psk@coilarmB
\psk@coilaspect \psk@coilinc
\pst@coildict \tx@Coil end}%
\showpointsfalse
\end@OpenObj}
\def\tx@CoilLoop{CoilLoop }
\def\tx@Coil{Coil }
\def\psCoil{\def\pst@par{}\pst@object{psCoil}}
\def\psCoil@i#1#2{%
\begin@AltOpenObj
\showpointsfalse
\pst@getangle{#1}\pst@tempa
\pst@getangle{#2}\pst@tempb
\addto@pscode{%
\pst@tempa
\pst@tempb
\psk@coilwidth
\pscoilheight
\psk@coilaspect
\psk@coilinc
\pst@coildict \tx@AltCoil end
\@nameuse{psls@\pslinestyle}}%
\end@OpenObj}
\def\tx@AltCoil{AltCoil }
\def\pszigzag{\def\pst@par{}\pst@object{pszigzag}}
\def\pszigzag@i{\pst@getarrows\pszigzag@ii}
\def\pszigzag@ii(#1){%
\@ifnextchar({\pszigzag@iii{1}(#1)}{\pszigzag@iii{\z@}(0,0)(#1)}}
\def\pszigzag@iii#1(#2)(#3){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#3}\pst@tempb
\pst@optcp{#1}\pst@tempa
\addto@pscode{%
\pst@tempa
\pst@tempb
\pscoilheight
\psk@coilwidth
\psk@coilarmA
\psk@coilarmB
\pst@coildict \tx@ZigZag end
\psline@iii
\tx@Line}%
\end@OpenObj}
\def\tx@ZigZag{ZigZag }
\def\nccoil{\pst@object{nccoil}}
\def\nccoil@i{\check@arrow{\nccoil@ii}}
\def\nccoil@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 2
4 2 roll
% DG/SR modification end
\psk@coilwidth \pscoilheight
\psk@coilarmA \psk@coilarmB
\psk@coilaspect \psk@coilinc
\pst@coildict \tx@Coil end
end}}
\def\pccoil{\def\pst@par{}\pst@object{pccoil}}
\def\pccoil@i{\pc@object\nccoil@ii}
\def\nczigzag{\pst@object{nczigzag}}
\def\nczigzag@i{\check@arrow{\nczigzag@ii}}
\def\nczigzag@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 2
4 2 roll
% DG/SR modification end
\pscoilheight
\psk@coilwidth
\psk@coilarmA
\psk@coilarmB
\pst@coildict \tx@ZigZag end
\psline@iii
\tx@Line
end}}
\def\pczigzag{\def\pst@par{}\pst@object{pczigzag}}
\def\pczigzag@i{\pc@object\nczigzag@ii}
\catcode`\@=\TheAtCode\relax
\endinput
%%
%% END pst-coil.tex

pst-node.tex
%% BEGIN pst-node.tex
%%
%% Nodes with PSTricks 97.
%% See the betadoc documentation for usage. 
%% This uses the header file `pst-node.pro'.
%%
\def\fileversion{97 patch 9}
\def\filedate{1999/04/14}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\message{ v\fileversion, \filedate}
\csname PSTnodesLoaded\endcsname
\let\PSTnodesLoaded\endinput
\ifx\PSTricksLoaded\endinput\else\input pstricks.tex\fi\relax
\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11
\pstheader{pst-node.pro}
\def\pst@nodedict{tx@NodeDict begin }
\def\pst@zapspace#1 #2{%
#1%
\ifx#2\@empty\else\expandafter\pst@zapspace\fi
#2}
\def\pst@getnode#1#2{%
\pst@expandafter\pst@@getnode{#1},,\@nil#2}
\def\pst@@getnode#1,#2,#3\@nil#4{%
\ifx\@empty#3\@empty
\edef#4{/N@\pst@zapspace#1 \@empty\space}%
\else
\pst@cntg=#1\relax
\pst@cnth=#2\relax
\edef#4{/N@M-\ifnum\psmatrixcnt=\z@ 1\else\the\psmatrixcnt\fi
-\the\pst@cntg-\the\pst@cnth\space}%
\fi}
\def\tx@NewNode{NewNode }
\def\pst@newnode#1#2#3#4{%
\leavevmode
\pst@getnode{#1}\pst@thenode
\pst@Verb{%
\pst@nodedict
{#3}
\ifx\psk@name\relax false \else \psk@name true \fi
\pst@thenode
#2
{#4}
\tx@NewNode
end}%
\global\let\psk@name\relax
\pstree@nodehook
\global\let\pstree@nodehook\relax}
\let\pstree@nodehook\relax
\newif\ifnodealign
\def\psset@nodealign#1{\@nameuse{nodealign#1}}
\psset@nodealign{false}
\def\pst@nodealign{%
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg2
\lower\pst@dimg}
\def\tx@InitPnode{InitPnode }
\def\pnode{\@ifnextchar({\pnode@}{\pnode@(0,0)}}
\def\pnode@(#1)#2{%
\pst@@getcoor{#1}%
\pst@newnode{#2}{10}{\pst@coor}{\tx@InitPnode}%
\ignorespaces}
\def\tx@InitCnode{InitCnode }
\def\cnode{\pst@object{cnode}}
\def\cnode@i{\@ifnextchar({\cnode@ii}{\cnode@ii(0,0)}}
\def\cnode@ii(#1)#2#3{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\pst@dimg=\psk@dimen\pslinewidth
\advance\pst@dimc-\pst@dimg
\advance\pst@dimc.5\pslinewidth
\ifnodealign
\kern\pst@dimc
\vrule width\z@ height \pst@dimc depth \pst@dimc
\fi
\pscircle@do(#1){#2}%
\pst@newnode{#3}{11}{\pst@coor \pst@number\pst@dimc}{\tx@InitCnode}%
% DG/SR modification begin - Jul. 30, 1997 - Patch 2
%\ifnodealign \kern\pst@dimc\egroup \fi}%
\ifnodealign\kern\pst@dimc\fi}%
% DG/SR modification end
\ignorespaces}
\def\Cnode{\pst@object{Cnode}}
\def\Cnode@i{\@ifnextchar({\Cnode@ii}{\Cnode@ii(0,0)}}
\def\Cnode@ii(#1)#2{\cnode@ii(#1){\psk@radius}{#2}}%
\def\cnodeput{\pst@object{cnodeput}}
\def\cnodeput@i{\@ifnextchar({\cnodeput@iii}{\cnodeput@ii}}
\def\cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cnodeput@iii}{\cnodeput@iii(\z@,\z@)}}
\def\cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiusfalse
\def\pst@nodehook{\cnodeput@iv{#2}}%
\pst@makebox{\cput@v{#1}}}
\def\cnodeput@iv#1{%
\pst@newnode{#1}{11}{\pscirclebox@iv \pst@number\pslinewidth add}%
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\Cnodeput{\pst@object{Cnodeput}}
\def\Cnodeput@i{\@ifnextchar({\Cnodeput@iii}{\Cnodeput@ii}}
\def\Cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\Cnodeput@iii}{\Cnodeput@iii(\z@,\z@)}}
\def\Cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiustrue
\def\pst@nodehook{\Cnodeput@iv{#2}}%
\pst@makebox{\cput@iv{#1}}}
\def\Cnodeput@iv#1{%
\pst@newnode{#1}{11}{%
\pst@number{\wd\pst@hbox} 2 div \pst@number\pst@dima % x y
\pst@number\pst@dimb \pst@number\pslinewidth \psk@dimen .5 sub mul sub }% r
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\circlenode{\pst@object{circlenode}}
\def\circlenode@i#1{\pst@makebox{\circlenode@ii{#1}}}
\def\circlenode@ii#1{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\cnodeput@iv{#1}%
\pscirclebox@iii
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\Circlenode{\pst@object{Circlenode}}
\def\Circlenode@i#1{\pst@makebox{\Circlenode@ii{#1}}}
\def\Circlenode@ii#1{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\Cnodeput@iv{#1}%
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\tx@GetRnodePos{GetRnodePos }
\def\tx@InitRnode{InitRnode }
\def\rnode{\@ifnextchar[{\rnode@i}{\def\pst@par{}\rnode@ii}}
\def\rnode@i[#1]{\def\pst@par{ref=#1}\rnode@ii}
\def\rnode@ii#1{\pst@makebox{\rnode@iii\rnode@iv{#1}}}
\def\rnode@iii#1#2{%
% DG modification begin - Jan. 1997
\leavevmode
% DG modification end
\begingroup
% DG/SR modification begin - Apr. 28, 1998 - Patch 6
\pst@useboxpar
% DG/SR modification end
#1%
\if@star\pst@starbox\fi
\ifnodealign\lower\pst@dimb\fi
\hbox{%
\pst@newnode{#2}{16}{%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\pst@number{\wd\pst@hbox}%
\pst@number\pst@dima
\pst@number\pst@dimb}%
{\tx@InitRnode}%
\box\pst@hbox}%
\endgroup}
\def\rnode@iv{%
\pst@dima=\psk@xref\wd\pst@hbox
\ifx\psk@yref\relax
\pst@dimb=\z@
\else
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\pst@dimb=\psk@yref\pst@dimb
\advance\pst@dimb-\dp\pst@hbox
\fi}
\def\psset@href#1{\pst@checknum{#1}\psk@href}
\psset@href{0}
\def\psset@vref#1{\def\psk@vref{#1}}
\psset@vref{.7ex}
\def\Rnode{\pst@object{Rnode}}
\def\Rnode@i#1{\pst@makebox{\rnode@iii\Rnode@ii{#1}}}
\def\Rnode@ii{%
% DG modification begin - Jan. 1997
%   - \begingroup removed  as it seems to doesn't work any more
%   - \Rnode doesn't process the optional parameter changes
%\begingroup
\use@par
% DG modification end
\pst@dima=\psk@href\wd\pst@hbox
\advance\pst@dima\wd\pst@hbox
\divide\pst@dima 2
\pssetlength\pst@dimb{\psk@vref}}
\def\tx@DiaNodePos{DiaNodePos }
\def\dianode{\pst@object{dianode}}
\def\dianode@i#1{\pst@makebox{\dianode@ii{#1}}}
\def\dianode@ii#1{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc 2 mul def
/h \pst@number\pst@dimd 2 mul def
/NodePos { \tx@DiaNodePos } def}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psdiabox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\tx@TriNodePos{TriNodePos }
\def\tx@InitTriNode{InitTriNode }
\def\trinode{\pst@object{trinode}}
\def\trinode@i#1{\pst@makebox{\trinode@ii{#1}}}
\def\trinode@ii#1{%
\begingroup
\pst@useboxpar
\pstribox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
\pst@number\pst@dimc
\pst@number\pst@dimd
\ifodd\psk@trimode
exch
\pst@number\pst@dima
\else
\pst@number\pst@dimb
\fi
\psk@trimode
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\tx@InitTriNode}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\pstribox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@tempa\fi
\box\pst@hbox
\endgroup}
\def\tx@OvalNodePos{OvalNodePos }
\def\ovalnode{\pst@object{ovalnode}}
\def\ovalnode@i#1{\pst@makebox{\ovalnode@ii{#1}}}
\def\ovalnode@ii#1{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc def
/h \pst@number\pst@dimd def
/NodePos { \tx@OvalNodePos } def}%
\unhbox\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psovalbox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\dotnode{\pst@object{dotnode}}
\def\dotnode@i{\@ifnextchar({\dotnode@ii}{\dotnode@ii(\z@,\z@)}}
\def\dotnode@ii(#1)#2{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pst@getdotsize
\pstree@nodehook
\ifnodealign
\pst@dima=\pst@dimg
\kern\pst@dima
\vrule width\z@ height \pst@dimh depth \pst@dimh
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/w \pst@number\pst@dimg def
/h \pst@number\pst@dimh def
/NodePos { \tx@OvalNodePos } def}%
\psdot@ii(#1)%
\ifnodealign\kern\pst@dima\fi}%
\ignorespaces}
\def\psset@framesize#1{\pst@expandafter\psset@@framesize{#1} \@nil}
\def\psset@@framesize#1 #2\@nil{%
\pssetlength\pst@dimg{#1}%
\divide\pst@dimg2
\edef\psk@framewidth{\pst@number\pst@dimg}%
\ifx\@empty#2\@empty
\let\psk@frameheight\psk@framewidth
\else
\pssetlength\pst@dimg{#2}%
\divide\pst@dimg2
\edef\psk@frameheight{\pst@number\pst@dimg}%
\fi}
\psset@framesize{10pt}
\def\fnode{\pst@object{fnode}}
\def\fnode@i{\@ifnextchar({\fnode@ii}{\fnode@ii(\z@,\z@)}}
\def\fnode@ii(#1)#2{%
\leavevmode
\pst@killglue
\hbox{%
\use@par
\begin@ClosedObj
\ifnodealign
\kern\psk@framewidth\p@
\vrule width\z@ height \psk@frameheight\p@ depth \psk@frameheight\p@
\edef\pst@coor{0 0 }%
\else
\pst@@getcoor{#1}%
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/d \psk@dimen .5 sub CLW mul neg def
/r \psk@framewidth d add def
/l r neg def
/u \psk@frameheight d add def
/d u neg def
/NodePos { \tx@GetRnodePos } def}%
\addto@pscode{%
/x2 \psk@framewidth CLW \psk@dimen mul sub def
/y2 \psk@frameheight CLW \psk@dimen mul sub def
\pst@coor 2 copy
y2 sub /y1 ED
x2 sub /x1 ED
y2 add /y2 ED
x2 add /x2 ED
\psk@cornersize
1 index 0 eq { pop pop \tx@Rect } { \tx@OvalFrame } ifelse}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\ifnodealign\kern\psk@framewidth\p@\fi}%
\ignorespaces}
\def\psset@nodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{0 }}
\def\psset@nodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{0 }}
\def\psset@nodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{0 }%
\def\psk@nodeseptypeB{0 }}
\psset@nodesep{0pt}
\def\psset@XnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{1 }}
\def\psset@XnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{1 }}
\def\psset@Xnodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{1 }%
\def\psk@nodeseptypeB{1 }}
\def\psset@YnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{2 }}
\def\psset@YnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{2 }}
\def\psset@Ynodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{2 }%
\def\psk@nodeseptypeB{2 }}
\def\psset@armA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{0 }}
\def\psset@armB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{0 }}
\def\psset@arm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{0 }%
\def\psk@armtypeB{0 }}
\psset@arm{10pt}
\def\psset@XarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{1 }}
\def\psset@XarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{1 }}
\def\psset@Xarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{1 }%
\def\psk@armtypeB{1 }}
\def\psset@YarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{2 }}
\def\psset@YarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{2 }}
\def\psset@Yarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{2 }%
\def\psk@armtypeB{2 }}
\def\psset@offsetA#1{\pst@getlength{#1}\psk@offsetA}
\def\psset@offsetB#1{\pst@getlength{#1}\psk@offsetB}
\def\psset@offset#1{\psset@offsetA{#1}\let\psk@offsetB\psk@offsetA}
\psset@offset{0pt}
\def\psset@angleA#1{\pst@getangle{#1}\psk@angleA}
\def\psset@angleB#1{\pst@getangle{#1}\psk@angleB}%
\def\psset@angle#1{%
\pst@getangle{#1}\psk@angleA
\let\psk@angleB\psk@angleA}
\psset@angle{0}
\def\psset@arcangleA#1{\pst@getangle{#1}\psk@arcangleA}
\def\psset@arcangleB#1{\pst@getangle{#1}\psk@arcangleB}%
\def\psset@arcangle#1{%
\pst@getangle{#1}\psk@arcangleA
\let\psk@arcangleB\psk@arcangleA}
\psset@arcangle{8}
\def\psset@ncurvA#1{\pst@checknum{#1}\psk@ncurvA}
\def\psset@ncurvB#1{\pst@checknum{#1}\psk@ncurvB}%
\def\psset@ncurv#1{\psset@ncurvA{#1}\let\psk@ncurvB\psk@ncurvA}
\psset@ncurv{.67}
\def\tx@GetCenter{GetCenter }
\def\tx@XYPos{XYPos }
\def\tx@GetEdge{GetEdge }
\def\tx@AddOffset{AddOffset }
\def\tx@GetEdgeA{GetEdgeA }
\def\tx@GetEdgeB{GetEdgeB }
\def\tx@GetArmA{GetArmA }
\def\tx@GetArmB{GetArmB }
\def\check@arrow#1#2{%
\check@@arrow#2-\@nil
\if@pst
\addto@par{arrows=#2}%
\def\next{#1}%
\else
\def\next{#1{#2}}%
\fi
\next}
\def\check@@arrow#1-#2\@nil{%
\ifx\@nil#2\@nil\@pstfalse\else\@psttrue\fi}
\def\tx@InitNC{InitNC }
\def\nc@object#1#2#3#4#5{%
\csname begin@#1Obj\endcsname
\showpointsfalse
\pst@getnode{#2}\pst@tempa
\pst@getnode{#3}\pst@tempb
\gdef\npos@default{#4 }%
\addto@pscode{%
/NCLW CLW def
\pst@nodedict
\psk@offsetA
\psk@offsetB neg
\psk@nodesepA
\psk@nodesepB
\psk@nodeseptypeA
\psk@nodeseptypeB
\pst@tempa
\pst@tempb
\tx@InitNC { #5 } if
end}%
\def\use@pscode{%
\pst@Verb{gsave \tx@STV newpath \pst@code\space grestore}%
\gdef\pst@code{}}%
\csname end@#1Obj\endcsname
\pst@shortput}
\def\npos@default{.5 }
\def\pc@object#1{%
\@ifnextchar({\pc@@object#1}{\pst@getarrows{\pc@@object#1}}}
\def\pc@@object#1(#2)(#3){%
\pnode(#2){@@A}\pnode(#3){@@B}%
#1{@@A}{@@B}}
\def\tx@LPutLine{LPutLine }
\def\tx@LPutLines{LPutLines }
\def\tx@BezierMidpoint{BezierMidpoint }
\def\tx@HPosBegin{HPosBegin }
\def\tx@HPosEnd{HPosEnd }
\def\tx@HPutLine{HPutLine }
\def\tx@HPutLines{HPutLines }
\def\tx@VPosBegin{VPosBegin }
\def\tx@VPosEnd{VPosEnd }
\def\tx@VPutLine{VPutLine }
\def\tx@VPutLines{VPutLines }
\def\tx@HPutCurve{HPutCurve }
\def\tx@NCCoor{NCCoor }
\def\tx@NCLine{NCLine }
\def\ncline{\pst@object{ncline}}
\def\ncline@i{\check@arrow{\ncline@ii}}
\def\ncline@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{\tx@NCLine}}
\def\pcline{\pst@object{pcline}}
\def\pcline@i{\pc@object\ncline@ii}
\def\ncLine{\pst@object{ncLine}}
\def\ncLine@i{\check@arrow{\ncLine@ii}}
\def\ncLine@ii#1#2{\nc@object{Open}{#1}{#2}{.5}%
% DG/SR modification begin - Apr. 14, 1999 - Patch 9
%{\tx@NCLine /LPutPos { xB xA yB yA \tx@LPutLine } def}}
{\tx@NCLine /LPutPos { xB yB xA yA \tx@LPutLine } def}}
% DG/SR modification end
\def\tx@NCLines{NCLines }
\def\nclines{\pst@object{nclines}}
\def\nclines@i{\check@arrow\nclines@ii}
\def\nclines@ii#1#2{%
\begingroup
\use@par
\def\pst@aftercoors{\nclines@iii{#1}{#2}}%
\def\pst@coors{}%
\pst@@getcoors}
\def\nclines@iii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
mark \pst@coors \tx@NCLines}%
\endgroup
\ignorespaces}
\def\tx@NCCurve{NCCurve }
\def\nccurve{\pst@object{nccurve}}
\def\nccurve@i{\check@arrow{\nccurve@ii}}
\def\nccurve@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
/AngleA \psk@angleA\space def /AngleB \psk@angleB\space def
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pccurve{\pst@object{pccurve}}
\def\pccurve@i{\pc@object\nccurve@ii}
\def\ncarc{\pst@object{ncarc}}
\def\ncarc@i{\check@arrow{\ncarc@ii}}
\def\ncarc@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
yB yA sub xB xA sub \tx@Atan dup
\psk@arcangleA\space add /AngleA ED
\psk@arcangleB\space sub 180 add /AngleB ED
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pcarc{\pst@object{pcarc}}
\def\pcarc@i{\pc@object\ncarc@ii}
\def\tx@NCAngles{NCAngles }
\def\ncangles{\pst@object{ncangles}}
\def\ncangles@i{\check@arrow{\ncangles@ii}}
\def\ncangles@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngles}}
\def\ncangles@iii{%
tx@Dict begin \psline@iii pop end
/AngleA \psk@angleA def
/AngleB \psk@angleB def
/ArmA \psk@armA def
/ArmB \psk@armB def
/ArmTypeA \psk@armtypeA def
/ArmTypeB \psk@armtypeB def }
\def\pcangles{\pst@object{pcangles}}
\def\pcangles@i{\pc@object\ncangles@ii}
\def\tx@NCAngle{NCAngle }
\def\ncangle{\pst@object{ncangle}}
\def\ncangle@i{\check@arrow{\ncangle@ii}}
\def\ncangle@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngle}}
\def\pcangle{\pst@object{pcangle}}
\def\pcangle@i{\pc@object\ncangle@ii}
\def\tx@NCBar{NCBar }
\def\ncbar{\pst@object{ncbar}}
\def\ncbar@i{\check@arrow{\ncbar@ii}}
\def\ncbar@ii#1#2{\nc@object{Open}{#1}{#2}{1.5}{%
\ncangles@iii /AngleB \psk@angleA def \tx@NCBar}}
\def\pcbar{\pst@object{pcbar}}
\def\pcbar@i{\pc@object\ncbar@ii}
\def\tx@NCDiag{NCDiag }
\def\ncdiag{\pst@object{ncdiag}}
\def\ncdiag@i{\check@arrow{\ncdiag@ii}}
\def\ncdiag@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCDiag}}
\def\pcdiag{\pst@object{pcdiag}}
\def\pcdiag@i{\pc@object\ncdiag@ii}
\def\tx@NCDiagg{NCDiagg }
\def\ncdiagg{\pst@object{ncdiagg}}
\def\ncdiagg@i{\check@arrow{\ncdiagg@ii}}
\def\ncdiagg@ii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{\ncangles@iii \tx@NCDiagg}}
\def\pcdiagg{\pst@object{pcdiagg}}
\def\pcdiagg@i{\pc@object\ncdiagg@ii}
\def\tx@NCLoop{NCLoop }
\def\psset@loopsize#1{\pst@getlength{#1}\psk@loopsize}
\psset@loopsize{1cm}
\def\ncloop{\pst@object{ncloop}}
\def\ncloop@i{\check@arrow{\ncloop@ii}}
\def\ncloop@ii#1#2{%
\nc@object{Open}{#1}{#2}{2.5}%
{\ncangles@iii /loopsize \psk@loopsize def \tx@NCLoop}}
\def\pcloop{\pst@object{pcloop}}
\def\pcloop@i{\pc@object\ncloop@ii}
\def\tx@NCCircle{NCCircle }
\def\nccircle{\pst@object{nccircle}}
\def\nccircle@i{\check@arrow{\nccircle@ii}}
\def\nccircle@ii#1#2{%
\pssetlength\pst@dima{#2}%
\nc@object{Open}{#1}{#1}{.5}{%
/AngleA \psk@angleA def
/r \pst@number\pst@dima def
\tx@NCCircle \psarc@v end}}
\def\tx@NCBox{NCBox }
\def\ncbox{\pst@object{ncbox}}
\def\ncbox@i{\check@arrow{\ncbox@ii}}
\def\ncbox@ii#1#2{%
\def\pst@linetype{2}%
\nc@object{Closed}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
\psk@boxheight \psk@boxdepth
\tx@NCBox}}
\def\pcbox{\pst@object{pcbox}}
\def\pcbox@i{\pc@object\ncbox@ii}
\def\tx@NCArcBox{NCArcBox }
\def\psset@boxheight#1{\pst@getlength{#1}\psk@boxheight}
\def\psset@boxdepth#1{\pst@getlength{#1}\psk@boxdepth}
\def\psset@boxsize#1{%
\psset@boxheight{#1}%
\let\psk@boxdepth\psk@boxheight}
\psset@boxsize{.4cm}
\def\ncarcbox{\pst@object{ncarcbox}}
\def\ncarcbox@i{\check@arrow{\ncarcbox@ii}}
\def\ncarcbox@ii#1#2{%
\def\pst@linetype{1}%
\nc@object{Closed}{#1}{#2}{.5}{%
\psk@arcangleA \psk@boxheight \psk@boxdepth \pst@number\pslinearc
\tx@NCArcBox}}
\def\pcarcbox{\pst@object{pcarcbox}}
\def\pcarcbox@i{\pc@object\ncarcbox@ii}
\def\tx@Tfan{Tfan }
% Changed according pst-beta.bug December 3, 1993
% nrot=:<angle> does not work when : is active.
\begingroup
\catcode`\:=13
\gdef\pst@activerot{\def:{\string:}}
\endgroup
\def\psset@nrot#1{%
\begingroup
\pst@activerot
\pst@expandafter{\@ifnextchar:{\psset@@nrot}{\psset@@rot}}{#1}\@nil
\global\let\pst@tempg\psk@rot
\endgroup
\let\psk@nrot\pst@tempg}
\def\psset@@nrot:#1\@nil{%
\psset@@rot#1\@nil
\edef\psk@rot{NAngle \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\psset@nrot{0}
\def\tx@LPutCoor{LPutCoor }
\def\tx@LPut{LPut }
\def\psset@npos#1{%
\def\pst@tempa{#1}%
\ifx\pst@tempa\@empty
\def\psk@npos{\npos@default}%
\else
\pst@checknum{#1}\psk@npos
\fi}
\psset@npos{}
\def\ncput{\pst@object{ncput}}
\def\ncput@i{\pst@killglue\pst@makebox{\ncput@ii}}
\def\ncput@ii{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\ncput@iii{%
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@npos def
\tx@LPut
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}}
\def\naput{\pst@object{naput}}
\def\naput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 add}}}
\def\naput@ii#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\def\psk@refangle{#1 }%
\let\psk@rot\psk@nrot
\uput@vii
{exch pop add a \tx@PtoC h1 add exch w1 add exch }%
{tx@Dict /NCLW known { NCLW add } if }%
\ncput@iii
\endgroup
\pst@shortput}
\def\nbput{\pst@object{nbput}}
\def\nbput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 sub}}}
\def\psset@tpos#1{%
\pst@checknum{#1}\psk@tpos
\ifdim\psk@tpos \p@<\z@
\def\psk@tpos{.5}%
% DG/SR modification begin - Sep. 23, 1998 - Patch 7
%\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@ehpa
% DG/SR modification end
\else
\ifdim\psk@tpos \p@>\p@
\def\psk@tpos{.5}%
% DG/SR modification begin - Sep. 23, 1998 - Patch 7
%\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@ehpa
% DG/SR modification end
\fi
\fi}
\psset@tpos{.5}
\def\tvput{\pst@object{tvput}}
\def\tvput@i{\pst@makebox{\psput@tput{H}{1}}}
\def\tlput{\pst@object{tlput}}
\def\tlput@i{\pst@makebox{\psput@tput{H}{true}}}
\def\trput{\pst@object{trput}}
\def\trput@i{\pst@makebox{\psput@tput{H}{false}}}
\def\thput{\pst@object{thput}}
\def\thput@i{\pst@makebox{\psput@tput{V}{1}}}
\def\taput{\pst@object{taput}}
\def\taput@i{\pst@makebox{\psput@tput{V}{true}}}
\def\tbput{\pst@object{tbput}}
\def\tbput@i{\pst@makebox{\psput@tput{V}{false}}}
\def\tx@HPutAdjust{HPutAdjust }
\def\tx@VPutAdjust{VPutAdjust }
\def\psput@tput#1#2{%
\begingroup
\use@par
\pst@tputmakesmall
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@tpos \pst@tposflip def
tx@NodeDict /HPutPos known
{ #1PutPos }
{ CP /Y ED /X ED /NAngle 0 def /NCLW 0 def }
ifelse
/Sin NAngle sin def
/Cos NAngle cos def
/s \pst@number\pslabelsep NCLW add def
/l \pst@number\pst@dima def
/r \pst@number\pst@dimb def
/h \pst@number\pst@dimc def
/d \pst@number\pst@dimd def
% DG/SR modification begin - Sep. 26, 1997 - Patch 4
%\ifnum1=0#2\else
\ifnum1=0#2 \else
% DG/SR modification end
/flag #2 def
\csname tx@#1PutAdjust\endcsname
\fi
\tx@LPutCoor
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}%
\endgroup
\pst@shortput}
\def\pst@tposflip{}
\def\pst@tputmakesmall{%
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimg=\psk@href\pst@dimg
\pst@dimb\pst@dima
\advance\pst@dima\pst@dimg % leftsize
\advance\pst@dimb-\pst@dimg % rightsize
\pst@dimd=\psk@vref\relax
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc-\pst@dimd % height
\advance\pst@dimd\dp\pst@hbox % depth
\setbox\pst@hbox=\hbox to\z@{%
\kern-\pst@dima\vbox to\z@{\vss\box\pst@hbox\vskip-\pst@dimd}\hss}}
\def\MakeShortNab#1#2{%
  \def\pst@shortput@nab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\naput
    \else
      \ifx#2\next
        \let\pst@tempg\nbput
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortNab{^}{_}
\def\MakeShortTablr#1#2#3#4{%
  \def\pst@shortput@tablr{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\taput
    \else
      \ifx#2\next
        \let\pst@tempg\tbput
      \else
        \ifx#3\next
          \let\pst@tempg\tlput
        \else
          \ifx#4\next
            \let\pst@tempg\trput
          \else
            \ifx\@sptoken\next
              \let\pst@tempg\pst@shortput
            \fi
          \fi
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTablr{^}{_}{<}{>}
\def\MakeShortTab#1#2{%
  \def\pst@shortput@tab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \def\pst@tempg{%
        \@nameuse{%
          t\ifodd\psk@treemode\ifpstreeflip b\else a\fi
          \else\ifpstreeflip r\else l\fi\fi put}}%
    \else
      \ifx#2\next
        \def\pst@tempg{%
          \@nameuse{%
            t\ifodd\psk@treemode\ifpstreeflip a\else b\fi
            \else\ifpstreeflip l\else r\fi\fi put}}%
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTab{^}{_}
\def\psset@shortput#1{%
\def\pst@tempg{#1}%
\ifx\pst@tempg\@none
\let\pst@shortput\ignorespaces
\else
\@ifundefined{pst@shortput@#1}%
{\@pstrickserr{Bad short put: `#1'}\@ehpa}%
{\edef\pst@shortput{\noexpand\afterassignment\expandafter\noexpand
\csname pst@shortput@#1\endcsname\noexpand\let\noexpand\next}}%
\fi}
\psset@shortput{none}
\def\lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\lput@i}{\lput@ii}}}
\def\lput@i[#1]{\addto@par{ref=#1}\lput@ii}
\def\lput@ii{\@ifnextchar({\lput@iv}{\lput@iii}}
\def\lput@iii#1{\addto@par{nrot=#1}\@ifnextchar({\lput@iv}{\ncput@i}}
\def\lput@iv(#1){\addto@par{npos=#1}\ncput@i}
\def\mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\mput@i}{\ncput@i}}}
\def\mput@i[#1]{\addto@par{ref=#1}\ncput@i}
\def\Lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Lput@ii}{\Lput@i}}}
\def\Lput@i#1{\addto@par{labelsep=#1}\Lput@ii}
\def\Lput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Lput@iv}{\Lput@iii}}
\def\Lput@iii#1{\addto@par{nrot={#1}}\@ifnextchar({\Lput@iv}{\Lput@v}}
\def\Lput@iv(#1){\addto@par{npos=#1}\Lput@v}
\def\Lput@v{\pst@killglue\pst@makebox{\Lput@vi}}
\def\Lput@vi{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\Mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Mput@ii}{\Mput@i}}}
\def\Mput@i#1{\addto@par{labelsep=#1}\Mput@ii}
\def\Mput@ii[#1]{\addto@par{ref={#1}}\Lput@v}
\def\aput@#1{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\aput@i#1}{\aput@ii#1}}}
\def\aput@i#1[#2]{\addto@par{labelsep=#2}\aput@ii#1}
\def\aput@ii#1{\@ifnextchar({\aput@iv#1}{\aput@iii#1}}
\def\aput@iii#1#2{\addto@par{nrot=#2}\@ifnextchar({\aput@iv#1}{#1}}
\def\aput@iv#1(#2){\addto@par{npos=#2}#1}
\def\aput{\aput@\naput@i}
\def\bput{\aput@\nbput@i}
\def\Aput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Aput@i}{\naput@i}}}
\def\Aput@i[#1]{\addto@par{labelsep=#1}\naput@i}
\def\Bput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Bput@i}{\nbput@i}}}
\def\Bput@i[#1]{\addto@par{labelsep=#1}\nbput@i}
\def\node@coor#1;#2\@nil{%
\pst@getnode{#1}\pst@tempg
\edef\pst@coor{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \pst@tempg load \tx@GetCenter }
{ 0 0 }
ifelse
end }}
\def\Node@coor[#1]#2;#3\@nil{%
\begingroup
\psset{#1}%
\@ifnextchar\bgroup{\Node@@@coor}{\Node@@coor}#2\@nil
\endgroup
\let\pst@coor\pst@tempg}
\def\Node@@coor#1\@nil{%
\pst@getnode{#1}\pst@tempg
\xdef\pst@tempg{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \psk@nodesepA \psk@angleA
\pst@tempg load \psk@nodeseptypeA \tx@GetEdge
\psk@offsetA \psk@angleA \tx@AddOffset
\pst@tempg load \tx@GetCenter
3 -1 roll add 3 1 roll add exch }
{ CP }
ifelse
end }}%
\def\Node@@@coor#1{%
\pst@@getcoor{#1}%
\def\psk@angleA{%
\pst@tempg load \tx@GetCenter \pst@coor
3 -1 roll sub 3 1 roll sub neg \tx@Atan}%
\Node@@coor}
\def\nput{\pst@object{nput}}
\def\nput@i#1#2{\pst@killglue\pst@makebox{\nput@ii{#1}{#2}}}
\def\nput@ii#1#2{%
\begingroup
\use@par
\psset@refangle{#1}%
\let\psk@angleA\psk@refangle
\edef\psk@nodesepA{\pst@number\pslabelsep}%
\def\psk@nodeseptypeA{0 }%
\pslabelsep\z@
\uput@vi
\Node@@coor#2\@nil
\let\pst@coor\pst@tempg
\leavevmode
\psput@special\pst@hbox
\endgroup
\ignorespaces}
\newcount\psrow
\newcount\pscol
\newcount\psmatrixcnt
\newskip\psrowsep
\newskip\pscolsep
\def\psset@colsep#1{\pssetlength\pscolsep{#1}}
\def\psset@rowsep#1{\pssetlength\psrowsep{#1}}
\psset@colsep{1.5cm}
\psset@rowsep{1.5cm}
\newif\ifpsmatrix
% DG/SR modification begin - Nov. 27, 1998 - Patch 8
%\let\mscount\@multicnt
\ifx\mscount\@undefined\let\mscount\@multicnt\fi
% DG/SR modification end
\def\psmatrix{%
  \begingroup
{\ifnum0=`}\fi % Don't want to expand any &.
\@ifnextchar[{\psmatrix@i}{\ifnum0=`{\fi}{}\psmatrix@ii}}
\def\psmatrix@i[#1]{%
\ifnum0=`{\fi}{}%
\psset{#1}%
\psmatrix@ii}
\def\psmatrix@ii{%
\KillGlue
\edef\psm@beginmath{%
\ifmmode$\m@th\ifinner\textstyle\else\displaystyle\fi\fi}%
\edef\psm@endmath{\ifmmode$\fi}%
\let\\\psm@cr
\advance\psmatrixcnt 1
\def\psm@thenode{M-\the\psmatrixcnt-\the\psrow-\the\pscol}%
\tabskip\z@
\psrow1
\pscol\z@
\psset@shortput{tablr}%
\leavevmode
\vbox\bgroup\halign\bgroup&%
\begingroup
\global\advance\pscol 1
\csname psrowhook\romannumeral\psrow\endcsname
\csname pscolhook\romannumeral\pscol\endcsname
\psm@beginnode##\psm@endnode\endgroup
\cr}
\def\endpsmatrix{%
\crcr\egroup\unskip\egroup
\endgroup}
\def\psm@cr{{\ifnum0=`}\fi\@ifnextchar[{\psm@@cr}{\psm@@@cr{}}}
\def\psm@@cr[#1]{\psm@@@cr{\vskip#1\relax}}
\def\psm@@@cr#1{%
\ifnum0=`{\fi}{}\cr
\noalign{%
\global\advance\psrow 1
\global\pscol\z@
\vskip\psrowsep
#1}}
\def\psm@beginnode{%
\@ifnextchar\psm@endnode
{\let\psm@endnode@i\relax\setbox\pst@hbox=\hbox{}}%
{\pst@object{psm@beginnode}}}
\def\psm@beginnode@i{%
\setbox\pst@hbox=\hbox\bgroup
\psm@beginmath
\begingroup
\ignorespaces}
\def\psm@endnode@i{%
\unskip
\endgroup
\psm@endmath
\egroup
\use@par
\@psttrue}
\def\psm@endnode{%
\@pstfalse
\psm@endnode@i
\ifnum\pscol>1 \hskip\pscolsep \fi
\psk@mnodesize
\hfil
\nodealigntrue
\if@pst
\csname mnode@\psk@mnode\endcsname
\else
\csname mnode@\psk@emnode\endcsname
\fi
\psk@mcol
\psk@@mnodesize}
\def\psspan#1{\mscount#1\relax\loop\ifnum\mscount>\@ne \sp@n\repeat}
\def\psset@name#1{\pst@getnode{#1}\psk@name}
\let\psk@name\relax
\def\psset@mcol#1{%
\ifx r#1\relax
\let\psk@mcol\relax
\else
\ifx l#1\relax
\let\psk@mcol\hfill
\else
\let\psk@mcol\hfil
\fi
\fi}
\psset@mcol{c}
\def\psset@mnodesize#1{%
\pssetlength\pst@dimg{#1}%
\ifdim\pst@dimg<\z@
\let\psk@mnodesize\relax
\let\psk@@mnodesize\relax
\else
\edef\psk@mnodesize{\noexpand\hbox to\number\pst@dimg sp\noexpand\bgroup}%
\let\psk@@mnodesize\egroup
\fi}
\psset@mnodesize{-1pt}
\def\mnode@R{\rnode@iii\Rnode@ii{\psm@thenode}}
\def\mnode@r{\rnode@iii\rnode@iv{\psm@thenode}}
\def\mnode@oval{\ovalnode@ii{\psm@thenode}}
\def\mnode@tri{\trinode@ii{\psm@thenode}}
\def\mnode@dia{\dianode@ii{\psm@thenode}}
\def\mnode@C{{\nodealigntrue\cnode@ii(\z@,\z@){\psk@radius}{\psm@thenode}}}
\def\mnode@f{{\nodealigntrue\fnode@ii(\z@,\z@){\psm@thenode}}}
\def\mnode@circle{\circlenode@ii{\psm@thenode}}
\def\mnode@p{\pnode(\z@,\z@){\psm@thenode}}
% DG/SR modification begin - Jul. 22, 1997 - Patch 1
\def\mnode@dot{\dotnode@ii(\z@,\z@){\psm@thenode}}
% DG/SR modification end
\def\mnode@none{\box\pst@hbox}
\def\psset@mnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@mnode{#1}}}
\def\psset@emnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@emnode{#1}}}
\psset@mnode{R}
\psset@emnode{none}
%%%% FROM pst-coil.tex
\def\nccoil{\pst@object{nccoil}}
\def\nccoil@i{\check@arrow{\nccoil@ii}}
\def\nccoil@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 5
4 2 roll
% DG/SR modification end
\psk@coilwidth \pscoilheight
\psk@coilarmA \psk@coilarmB
\psk@coilaspect \psk@coilinc
\pst@coildict \tx@Coil end
end}}
\def\nczigzag{\pst@object{nczigzag}}
\def\nczigzag@i{\check@arrow{\nczigzag@ii}}
\def\nczigzag@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 5
4 2 roll
% DG/SR modification end
\pscoilheight
\psk@coilwidth
\psk@coilarmA
\psk@coilarmB
\pst@coildict \tx@ZigZag end
\psline@iii
\tx@Line
end}}
\catcode`\@=\TheAtCode\relax
\endinput
%%
%% END pst-node.tex

pstricks.tex
%% BEGIN: pstricks.tex
%%
%% PostScript macros for Generic TeX: main input file for PSTricks 97.
%% See the PSTricks User's Guide for description.
%% This uses the header file `pstricks.pro'.
%%
\def\fileversion{97 patch 10}
\def\filedate{1999/03/24}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\csname PSTricksLoaded\endcsname
\let\PSTricksLoaded\endinput
\edef\PstAtCode{\the\catcode`\@}
\catcode`\@=11\relax
\expandafter\ifx\csname @latexerr\endcsname\relax
\long\def\@ifundefined#1#2#3{\expandafter\ifx\csname
#1\endcsname\relax#2\else#3\fi}
\def\@namedef#1{\expandafter\def\csname #1\endcsname}
\def\@nameuse#1{\csname #1\endcsname}
\def\@eha{%
Your command was ignored.^^J
Type \space I <command> <return> \space to replace
it with another command,^^J
or \space <return> \space to continue without it.}
\def\@spaces{\space\space\space\space}
\def\typeout#1{\immediate\write\@unused{#1}}
\alloc@7\write\chardef\sixt@@n\@unused
\def\@empty{}
\def\@gobble#1{}
\def\@nnil{\@nil}
\def\@ifnextchar#1#2#3{%
\let\@tempe#1\def\@tempa{#2}\def\@tempb{#3}\futurelet\@tempc\@ifnch}
\def\@ifnch{%
\ifx\@tempc\@sptoken
\let\@tempd\@xifnch
\else
\ifx\@tempc\@tempe \let\@tempd\@tempa \else \let\@tempd\@tempb \fi
\fi
\@tempd}
\begingroup
\def\:{\global\let\@sptoken= } \:
\def\:{\@xifnch} \expandafter\gdef\: {\futurelet\@tempc\@ifnch}
\endgroup
\fi
\typeout{`PSTricks' v\fileversion\space\space <\filedate> (tvz)}
\def\@pstrickserr#1#2{%
\begingroup
\newlinechar`\^^J
\edef\pst@tempc{#2}%
\expandafter\errhelp\expandafter{\pst@tempc}%
\typeout{%
PSTricks error. \space See User's Guide for further information.^^J
\@spaces\@spaces\@spaces\@spaces
Type \space H <return> \space for immediate help.}%
\errmessage{#1}%
\endgroup}
\def\@ehpa{%
Your command was ignored. Default value substituted.^^J
Type \space <return> \space to procede.}
\def\@ehpb{%
Your command was ignored. Will recover best I can.^^J
Type \space <return> \space to procede.}
\def\@ehpc{%
You better fix this before proceding.^^J
See the PSTricks User's Guide or ask your system administrator for help.^^J
Type \space X <return> \space to quit.}
\def\pst@misplaced#1{\@pstrickserr{Misplaced \string#1 command}\@ehpb}
\newdimen\pst@dima
\newdimen\pst@dimb
\newdimen\pst@dimc
\newdimen\pst@dimd
\newdimen\pst@dimg
\newdimen\pst@dimh
\newbox\pst@hbox
\newbox\pst@boxg
\newcount\pst@cnta
\newcount\pst@cntb
\newcount\pst@cntc
\newcount\pst@cntd
\newcount\pst@cntg
\newcount\pst@cnth
\newif\if@pst
\newtoks\pst@toks
\newif\if@star
\def\pst@ifstar#1{%
\@ifnextchar*{\@startrue\def\next*{#1}\next}{\@starfalse#1}}
\def\pst@expandafter#1#2{%
\def\next{#1}%
\edef\@tempa{#2}%
\ifx\@tempa\@empty
\@pstrickserr{Unexpected empty argument!}\@ehpb
\def\@tempa{\@empty}%
\fi
\expandafter\next\@tempa}
\def\pst@dimtonum#1#2{\edef#2{\pst@@dimtonum#1}}
\def\pst@@dimtonum#1{\expandafter\pst@@@dimtonum\the#1}
{\catcode`\p=12 \catcode`\t=12 \global\@namedef{pst@@@dimtonum}#1pt{#1}}
\def\pst@pyth#1#2#3{%
\ifdim#1>#2\pst@@pyth#1#2#3\else\pst@@pyth#2#1#3\fi}
\def\pst@@pyth#1#2#3{%
\ifdim4#1>9#2%
#3=#1\advance#3 .2122#2%
\else
#3=.8384#1\advance#3 .5758#2%
\fi}
\def\pst@divide#1#2#3{%
\pst@@divide{#1}{#2}%
\pst@dimtonum\pst@dimg{#3}}
\def\pst@@divide#1#2{%
\pst@dimg=#1\relax
\pst@dimh=#2\relax
\pst@cntg=\pst@dimh
\pst@cnth=67108863
\pst@@@divide\pst@@@divide\pst@@@divide\pst@@@divide
\divide\pst@dimg\pst@cntg}
\def\pst@@@divide{%
\ifnum
\ifnum\pst@dimg<\z@-\fi\pst@dimg<\pst@cnth
\multiply\pst@dimg\sixt@@n
\else
\divide\pst@cntg\sixt@@n
\fi}
\def\pst@configerr#1{%
\@pstrickserr{\string#1 not defined in pstricks.con}\@ehpc}
% % \begin{macrocode}
\def\pstVerb#1{\pst@configerr\pstVerb}
\def\pstverb#1{\pst@configerr\pstverb}
\def\pstverbscale{\pst@configerr\pstverbscale}
\def\pstrotate{\pst@configerr\pstrotate}
\def\pstheader#1{\pst@configerr\pstheader}
\def\pstdriver{\pst@configerr\pstdriver}
\@ifundefined{pstcustomize}%
{\def\pstcustomize{\endinput\let\pstcustomize\relax}}{}
\input pstricks.con
\newif\ifPSTricks
\PSTrickstrue
\def\PSTricksOff{%
\def\pstheader##1{}%
\def\pstverb##1{}%
\def\pstVerb##1{}%
\PSTricksfalse}
\@ifundefined{pst@def}{\def\pst@def#1<#2>{\@namedef{tx@#1}{#2 }}}{}
\@ifundefined{pst@ATH}{\def\pst@ATH<#1>{}}{}
\pstheader{pstricks.pro}
\def\pst@dict{tx@Dict begin }
\def\pst@theheaders{pstricks.pro}
\def\pst@Verb#1{\pstVerb{\pst@dict #1 end}}
\def\tx@Atan{Atan }
\def\tx@Div{Div }
\def\tx@NET{NET }
\def\tx@Pyth{Pyth }
\def\tx@PtoC{PtoC }
\def\tx@PathLength@{PathLength@ }
\def\tx@PathLength{PathLength }
\pst@dimg=\pstunit\relax
\ifdim\pst@dimg=1bp
\def\pst@stp{.996264 dup scale}
\else
\edef\pst@stp{1 \pst@@dimtonum\pst@dimg\space div dup scale}
\fi
\def\tx@STP{STP }
\def\tx@STV{STV }
\def\pst@number#1{\pst@@dimtonum#1\space}
\def\pst@checknum#1#2{%
\edef\next{#1}%
\ifx\next\@empty
\let\pst@num\z@
\else
\expandafter\pst@@checknum\next..\@nil
\fi
\ifnum\pst@num=\z@
\@pstrickserr{Bad number: `#1'. 0 substituted.}\@ehpa
\def#2{0 }%
\else
\edef#2{\ifnum\pst@num=\tw@-\fi\the\pst@cntg.%
\expandafter\@gobble\the\pst@cnth\space}%
\fi}
\def\pst@@checknum{%
\@ifnextchar-%
{\let\pst@num\tw@\expandafter\pst@@@checknum\@gobble}%
{\let\pst@num\@ne\pst@@@checknum}}
\def\pst@@@checknum#1.#2.#3\@nil{%
\afterassignment\pst@@@@checknum\pst@cntg=0#1\relax\@nil
\afterassignment\pst@@@@checknum\pst@cnth=1#2\relax\@nil}
\def\pst@@@@checknum#1\relax\@nil{%
\ifx\@nil#1\@nil\else\let\pst@num\z@\fi}
\def\pst@getnumii#1 #2 #3\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph}
\def\pst@getnumiii#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi}
\def\pst@getnumiv#1 #2 #3 #4 #5\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\pst@checknum{#4}\pst@tempj}
\def\pst@getdimnum#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pst@checknum{#2}\pst@tempg}
% DG/SR modification begin - Jan. 7, 1998 - Patch 9
% Missing from pstricks.bug 0.93
%\def\pst@getscale#1#2{%
%\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
%\@psttrue
%\ifdim\pst@tempg\p@=\z@
%\@pstrickserr{Bad scaling argument `#1'}\@ehpa
%\def\pst@tempg{1 }%
%\@pstfalse
%\fi
%\ifdim\pst@temph\p@=\z@
%\if@pst\@pstrickserr{Bad scaling argument `#1'}\@ehpa\fi
%\def\pst@temph{1 }%
%\fi
%\edef#2{\pst@tempg\space \pst@temph\space scale }%
%\ifdim\pst@tempg\p@=\p@ \ifdim\pst@temph\p@=\p@
%\def#2{}%
%\fi\fi}
\def\pst@getscale#1#2{%
\edef\pst@tempg{#1}%
\ifx\pst@tempg\@none
\def#2{}%
\else
\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
\ifdim\pst@tempg\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\ifdim\pst@temph\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\edef#2{\pst@tempg\space \pst@temph\space scale }%
\fi
\fi
\fi}
% DG/SR modification end
\def\pst@getint#1#2{%
\pst@cntg=#1\relax
\edef#2{\the\pst@cntg\space}}
\begingroup
\catcode`\{=12
\catcode`\}=12
\catcode`\[=1
\catcode`\]=2
\gdef\pslbrace[{ ]
\gdef\psrbrace[} ]
\endgroup
\def\@newcolor#1#2{%
\expandafter\edef\csname #1\endcsname{\noexpand\pst@color{#2}}%
\expandafter\edef\csname color@#1\endcsname{#2}%
\ignorespaces}
\def\pst@color#1{%
\def\pst@currentcolor{#1}\pstVerb{#1}\aftergroup\pst@endcolor}
\def\pst@endcolor{\pstVerb{\pst@currentcolor}}
\def\pst@currentcolor{0 setgray}
\def\altcolormode{%
\def\pst@color##1{%
\pstVerb{gsave ##1}\aftergroup\pst@endcolor}%
\def\pst@endcolor{\pstVerb{\pst@grestore}}}
\def\pst@grestore{%
currentpoint
matrix currentmatrix
currentfont
grestore
setfont
setmatrix
moveto}
\def\pst@usecolor#1{\csname color@#1\endcsname\space}
\def\newgray#1#2{%
\pst@checknum{#2}\pst@tempg
\@newcolor{#1}{\pst@tempg setgray}}
\def\newrgbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi setrgbcolor}}
\def\newhsbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi sethsbcolor}}
\def\newcmykcolor#1#2{%
\pst@expandafter\pst@getnumiv{#2} {} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi \pst@tempj setcmykcolor}}
\newgray{black}{0}
\newgray{darkgray}{.25}
\newgray{gray}{.5}
\newgray{lightgray}{.75}
\newgray{white}{1}
\newrgbcolor{red}{1 0 0}
\newrgbcolor{green}{0 1 0}
\newrgbcolor{blue}{0 0 1}
\newrgbcolor{yellow}{1 1 0}
\newrgbcolor{cyan}{0 1 1}
\newrgbcolor{magenta}{1 0 1}
\def\psset#1{\@psset#1,\@nil\ignorespaces}
\def\@psset#1,{%
\@@psset#1==\@nil
\@ifnextchar\@nil{\@gobble}{\@psset}}
\def\@@psset#1=#2=#3\@nil{%
\@ifundefined{psset@#1}%
{\@pstrickserr{Graphics parameter `#1' not defined.}\@ehpa}%
{\@nameuse{psset@#1}{#2}}}%
\def\psset@style#1{%
\@ifundefined{pscs@#1}%
{\@pstrickserr{Custom style `#1' undefined}\@ehpa}%
{\@nameuse{pscs@#1}}}
\def\newpsstyle#1#2{\@namedef{pscs@#1}{\psset{#2}}}
\def\@none{none}
\def\pst@getcolor#1#2{%
\@ifundefined{color@#1}%
{\@pstrickserr{Color `#1' not defined}\@eha}%
{\edef#2{#1}}}
\newdimen\psunit \psunit 1cm
\newdimen\psxunit \psxunit 1cm
\newdimen\psyunit \psyunit 1cm
\let\psrunit\psunit
\def\pstunit@off{\let\@psunit\ignorespaces\ignorespaces}
\def\pssetlength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psaddtolength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
\advance#1 #2\@psunit}
\def\pssetxlength#1#2{%
\let\@psunit\psxunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\pssetylength#1#2{%
\let\@psunit\psyunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psset@unit#1{%
\pssetlength\psunit{#1}%
\psxunit=\psunit
\psyunit=\psunit}
\def\psset@runit#1{\pssetlength\psrunit{#1}}
\def\psset@xunit#1{\pssetxlength\psxunit{#1}}
\def\psset@yunit#1{\pssetylength\psyunit{#1}}
\def\pst@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\pst@number\pst@dimg}}
\def\pst@@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\number\pst@dimg sp}}
\def\pst@getcoor#1#2{\pst@@getcoor{#1}\let#2\pst@coor}
\def\pst@coor{0 0 }
\def\pst@getcoors#1#2{%
\def\pst@aftercoors{\addto@pscode{#1 \pst@coors }#2}%
\def\pst@coors{}%
\pst@@getcoors}
\def\pst@@getcoors(#1){%
\pst@@getcoor{#1}%
\edef\pst@coors{\pst@coor\pst@coors}%
\@ifnextchar({\pst@@getcoors}{\pst@aftercoors}}
\def\pst@getangle#1#2{\pst@@getangle{#1}\let#2\pst@angle}
\def\pst@angle{0 }
\def\cartesian@coor#1,#2,#3\@nil{%
\pssetxlength\pst@dimg{#1}%
\pssetylength\pst@dimh{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\NormalCoor{%
\def\pst@@getcoor##1{\pst@expandafter\cartesian@coor{##1},\relax,\@nil}%
\def\pst@@getangle##1{%
\pst@checknum{##1}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@cartesian}}
\NormalCoor
\def\degrees{\@ifnextchar[{\@degrees}{\def\pst@angleunit{}}}
\def\@degrees[#1]{%
\pst@checknum{#1}\pst@tempg
\edef\pst@angleunit{360 \pst@tempg div mul }%
\ignorespaces}
\def\radians{\def\pst@angleunit{57.2956 mul }}
\def\pst@angleunit{}
\def\SpecialCoor{%
\def\pst@@getcoor##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@coor\pst@tempg||\@nil}%
\def\pst@@getangle##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@angle\pst@tempg\@empty)\@nil}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@special}}
\begingroup
\catcode`\|=13
\catcode`\;=13
\catcode`\!=13
\gdef\pst@activecoor{%
\def|{\string|}%
\def;{\string;}%
\def!{\string!}}
\endgroup
\def\special@coor#1|#2|#3\@nil{%
\ifx#3|\relax
\mixed@coor{#1}{#2}%
\else
\special@@coor#1;;\@nil
\fi}
\def\special@@coor#1{%
\ifcat#1a\relax
\def\next{\node@coor#1}%
\else
\ifx#1[\relax
\def\next{\Node@coor[}%
\else
\ifx#1!\relax
\def\next{\raw@coor}%
\else
\def\next{\special@@@coor#1}%
\fi
\fi
\fi
\next}
\def\special@@@coor#1;#2;#3\@nil{%
\ifx#3;\relax
\polar@coor{#1}{#2}%
\else
\cartesian@coor#1,\relax,\@nil
\fi}
\def\mixed@coor#1#2{%
\begingroup
% DG/SR modification begin - Oct. 27, 1997 - Patch 6
%\specialcoor@ii#1;;\@nil
%\let\pst@tempa\pst@coor
%\specialcoor@ii#2;;\@nil
\special@@coor#1;;\@nil
\let\pst@tempa\pst@coor
\special@@coor#2;;\@nil
% DG/SR modification end
\xdef\pst@tempg{\pst@tempa pop \pst@coor exch pop }%
\endgroup
\let\pst@coor\pst@tempg}
\def\polar@coor#1#2{%
\pssetlength\pst@dimg{#1}%
\pst@@getangle{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@angle \tx@PtoC}}
\def\raw@coor#1;#2\@nil{%
\edef\pst@coor{%
#1 \pst@number\psyunit mul exch \pst@number\psxunit mul exch }}
\def\node@coor#1\@nil{%
\@pstrickserr{You must load `pst-node.tex' to use node coordinates.}\@ehps
\def\pst@coor{0 0 }}
\def\Node@coor{\node@coor}
\def\special@angle#1#2)#3\@nil{%
\ifx!#1\relax
\edef\pst@angle{#2 \pst@angleunit}%
\else
\ifx(#1\relax
\pst@@getcoor{#2}%
\edef\pst@angle{\pst@coor exch \tx@Atan}%
\else
\pst@checknum{#1#2}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}%
\fi
\fi}
\def\Cartesian{%
\def\cartesian@coor##1,##2,##3\@nil{%
\pssetxlength\pst@dimg{##1}%
\pssetylength\pst@dimh{##2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}%
\@ifnextchar({\Cartesian@}{}}
\def\Cartesian@(#1,#2){%
\pssetxlength\psxunit{#1}%
\pssetylength\psyunit{#2}%
\ignorespaces}
\def\Polar{%
\def\psput@cartesian{\psput@special}%
\def\cartesian@coor##1,##2,##3\@nil{\polar@coor{##1}{##2}}}%
\def\psset@origin#1{%
\pst@@getcoor{#1}%
\edef\psk@origin{\pst@coor \tx@NET }}
\def\psk@origin{}
\newif\ifswapaxes
\def\psset@swapaxes#1{%
\@nameuse{@pst#1}%
\if@pst
\def\psk@swapaxes{-90 rotate -1 1 scale }%
\else
\def\psk@swapaxes{}%
\fi}
\psset@swapaxes{false}
\newif\ifshowpoints
\def\psset@showpoints#1{\@nameuse{showpoints#1}}
\psset@showpoints{false}
\let\pst@setrepeatarrowsflag\relax
\def\psset@border#1{%
\pst@getlength{#1}\psk@border
\pst@setrepeatarrowsflag}
\psset@border{0pt}
\def\psset@bordercolor#1{\pst@getcolor{#1}\psbordercolor}
\psset@bordercolor{white}
\newif\ifpsdoubleline
\def\psset@doubleline#1{%
\@nameuse{psdoubleline#1}%
\pst@setrepeatarrowsflag}
\psset@doubleline{false}
\def\psset@doublesep#1{\def\psdoublesep{#1}}
\psset@doublesep{1.25\pslinewidth}
\def\psset@doublecolor#1{\pst@getcolor{#1}\psdoublecolor}
\psset@doublecolor{white}
\newif\ifpsshadow
\def\psset@shadow#1{%
\@nameuse{psshadow#1}%
\pst@setrepeatarrowsflag}
\psset@shadow{false}
\def\psset@shadowsize#1{\pst@getlength{#1}\psk@shadowsize}
\psset@shadowsize{3pt}
\def\psset@shadowangle#1{\pst@getangle{#1}\psk@shadowangle}
\psset@shadowangle{-45}
\def\psset@shadowcolor#1{\pst@getcolor{#1}\psshadowcolor}
\psset@shadowcolor{darkgray}
\def\pst@repeatarrowsflag{\z@}
\def\pst@setrepeatarrowsflag{%
\edef\pst@repeatarrowsflag{%
\ifdim\psk@border\p@>\z@ 1\else\ifpsdoubleline 1\else
\ifpsshadow 1\else \z@\fi\fi\fi}}
\def\psls@none{}
\newdimen\pslinewidth
\def\psset@linewidth#1{\pssetlength\pslinewidth{#1}}
\psset@linewidth{.8pt}
\def\psset@linecolor#1{\pst@getcolor{#1}\pslinecolor}
\psset@linecolor{black}
\def\psls@solid{0 setlinecap stroke }
\def\pst@missing{%
\z@
\@pstrickserr{Missing number or dimension. 0 substituted}\@ehpa}
\def\psset@dash#1{%
\pst@expandafter\psset@@dash{#1} {\pst@missing} {\pst@missing} {}\@nil
\edef\psk@dash{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\psset@@dash#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pssetlength\pst@dimh{#2}}
\psset@dash{5pt 3pt}
\newif\ifpsdashadjust
\def\psset@dashadjust#1{\@nameuse{psdashadjust#1}}
\psset@dashadjust{true}
\def\psls@dashed{%
\ifpsdashadjust
\psk@dash \pst@linetype\space \tx@DashLine
\else
[ \psk@dash ] 0 setdash stroke
\fi}
\def\tx@DashLine{DashLine }
\def\psset@dotsep#1{\pst@getlength{#1}\psk@dotsep}
\psset@dotsep{3pt}
\def\psls@dotted{%
\ifpsdashadjust
\psk@dotsep \pst@linetype\space \tx@DotLine
\else
[ 0 \psk@dotsep CLW add ] 0 setdash 1 setlinecap stroke
\fi}
\def\tx@DotLine{DotLine }
\def\psset@linestyle#1{%
\@ifundefined{psls@#1}%
{\@pstrickserr{Line style `#1' not defined}\@eha}%
{\edef\pslinestyle{#1}}}
\psset@linestyle{solid}
\def\psfs@none{}
\def\psset@fillcolor#1{\pst@getcolor{#1}\psfillcolor}
\psset@fillcolor{white}
\def\psfs@solid{\pst@fill{\pst@usecolor\psfillcolor fill}}
\def\psset@hatchwidth#1{\pst@getlength{#1}\psk@hatchwidth}
\psset@hatchwidth{.8pt}
\def\psset@hatchsep#1{\pst@getlength{#1}\psk@hatchsep}
\psset@hatchsep{4pt}
\def\psset@hatchcolor#1{\pst@getcolor{#1}\pshatchcolor}
\psset@hatchcolor{black}
\def\psset@hatchangle#1{\pst@getangle{#1}\psk@hatchangle}
\psset@hatchangle{45}
\def\pst@linefill{%
\psk@hatchangle rotate
\psk@hatchwidth SLW
\pst@usecolor\pshatchcolor
\psk@hatchsep \tx@LineFill}
\def\psfs@vlines{\pst@fill\pst@linefill}
\@namedef{psfs@vlines*}{\psfs@solid \psfs@vlines}
\def\psfs@hlines{\pst@fill{90 rotate \pst@linefill}}
\@namedef{psfs@hlines*}{\psfs@solid \psfs@hlines}
\def\psfs@crosshatch{\psfs@vlines \psfs@hlines}
\@namedef{psfs@crosshatch*}{\psfs@solid \psfs@vlines \psfs@hlines}
\def\tx@LineFill{LineFill }
\def\psset@fillstyle#1{%
\edef\pst@tempg{#1}\def\pst@temph{none}%
\ifx\pst@tempg\pst@temph
\let\psk@fillstyle\relax
\else
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{\expandafter\noexpand\csname psfs@#1\endcsname}}%
\fi}
\def\psset@addfillstyle#1{%
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{%
\expandafter\noexpand\psk@fillstyle
\expandafter\noexpand\csname psfs@#1\endcsname}}}
\psset@fillstyle{none}
\def\psset@arrows#1{%
\begingroup
\pst@activearrows
\xdef\pst@tempg{#1}%
\endgroup
\expandafter\psset@@arrows\pst@tempg\@empty-\@empty\@nil
\if@pst\else
\@pstrickserr{Bad arrows specification: #1}\@ehpa
\fi}
\def\psset@@arrows#1-#2\@empty#3\@nil{%
\@psttrue
\def\next##1,#1-##2,##3\@nil{\def\pst@tempg{##2}}%
\expandafter\next\pst@arrowtable,#1-#1,\@nil
\@ifundefined{psas@\pst@tempg}%
{\@pstfalse\def\psk@arrowA{}}%
{\let\psk@arrowA\pst@tempg}%
\@ifundefined{psas@#2}%
{\@pstfalse\def\psk@arrowB{}}%
{\def\psk@arrowB{#2}}}
\def\psk@arrowA{}
\def\psk@arrowB{}
\def\pst@arrowtable{,<->,<<->>,>-<,>>-<<,(-),[-]}
\begingroup
\catcode`\<=13
\catcode`\>=13
\catcode`\|=13
\gdef\pst@activearrows{\def<{\string<}\def>{\string>}\def|{\string|}}
\endgroup
\def\tx@BeginArrow{BeginArrow }
\def\tx@EndArrow{EndArrow }
\def\psset@arrowscale#1{\pst@getscale{#1}\psk@arrowscale}
\psset@arrowscale{1}
\def\psset@arrowsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@arrowsize{\pst@number\pst@dimg \pst@tempg}}
\psset@arrowsize{1.5pt 2}
\def\psset@arrowlength#1{\pst@checknum{#1}\psk@arrowlength}
\psset@arrowlength{1.4}
\def\psset@arrowinset#1{\pst@checknum{#1}\psk@arrowinset}%
\psset@arrowinset{.4}
\def\tx@Arrow{Arrow }
\@namedef{psas@>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
0 h T
gsave
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP
grestore
CP newpath moveto
2 copy
L
stroke
moveto}
\@namedef{psas@<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@<<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP newpath moveto 0 a neg L stroke 0 h neg T
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\def\psset@tbarsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@tbarsize{\pst@number\pst@dimg \pst@tempg}}
\psset@tbarsize{2pt 5}
\def\tx@Tbar{Tbar }
\@namedef{psas@|}{\psk@tbarsize \tx@Tbar}
\@namedef{psas@|*}{0 CLW -2 div T \psk@tbarsize \tx@Tbar}
\@namedef{psas@>|}{%
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>|*}{%
0 CLW -2 div T
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\edef\pst@arrowtable{\pst@arrowtable,|<*->|*,|<->|}
\def\psset@bracketlength#1{\pst@checknum{#1}\psk@bracketlength}
\psset@bracketlength{.15}
\def\tx@Bracket{Bracket }
\@namedef{psas@]}{\psk@bracketlength \psk@tbarsize \tx@Bracket}
\def\psset@rbracketlength#1{\pst@checknum{#1}\psk@rbracketlength}
\psset@rbracketlength{.15}
\def\tx@RoundBracket{RoundBracket }
\@namedef{psas@)}{\psk@rbracketlength \psk@tbarsize \tx@RoundBracket}
\def\psas@c{1 \psas@@c}
\def\psas@cc{0 CLW 2 div T 1 \psas@@c}
\def\psas@C{2 \psas@@c}
\def\psas@@c{%
setlinecap
0 0 moveto
0 CLW 2 div L
stroke
0 0 moveto}
\def\psas@{}
\psset@arrows{-}
\def\tx@SD{SD }
\def\tx@EndDot{EndDot }
\def\psas@oo{{\pst@usecolor\psfillcolor true} true \psk@dotsize \tx@EndDot}
\def\psas@o{{\pst@usecolor\psfillcolor true} false \psk@dotsize \tx@EndDot}
\@namedef{psas@**}{{false} true \psk@dotsize \tx@EndDot}
\@namedef{psas@*}{{false} false \psk@dotsize \tx@EndDot}
\def\pst@par{}
\def\addto@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\expandafter\def\expandafter\pst@par\expandafter{\pst@par,#1}%
\fi}
\def\addbefore@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\toks@{#1}%
\pst@toks\expandafter{\pst@par}%
\edef\pst@par{\the\toks@,\the\pst@toks}%
\fi}
\def\use@par{%
\ifx\pst@par\@empty\else
\expandafter\@psset\pst@par,\@nil
\def\pst@par{}%
\fi}
\def\pst@object#1{%
\pst@ifstar{%
\@ifnextchar[%
{\pst@@object{#1}}%
{\def\pst@par{}\@nameuse{#1@i}}}}
\def\pst@@object#1[#2]{%
\def\pst@par{#2}%
\@ifnextchar+{\@nameuse{#1@i}}{\@nameuse{#1@i}}}
\def\newpsobject#1#2#3{%
\@ifundefined{#2@i}%
{\@pstrickserr{Graphics object `#2' not defined}\@eha}{%
\@namedef{#1}{\pst@object{#1}}%
\@namedef{#1@i}{\addbefore@par{#3}\@nameuse{#2@i}}}%
\ignorespaces}
\def\pst@getarrows#1{\@ifnextchar({#1}{\pst@@getarrows{#1}}}
\def\pst@@getarrows#1#2{\addto@par{arrows=#2}#1}
\def\begin@ClosedObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\solid@star
\ifpsdoubleline \pst@setdoublesep \fi
\init@pscode}
\def\end@ClosedObj{%
\ifpsshadow \pst@closedshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifshowpoints
% DG modification begin - Mar. 4, 1995
%\addto@pscode{Points aload length 2 div cvi /N ED \psdots@iii}%
\pst@OpenShowPoints
% DG modification end
\fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@OpenObj{%
\begin@ClosedObj
\let\pst@linetype\pst@arrowtype
\pst@addarrowdef}
\def\begin@AltOpenObj{%
\begin@ClosedObj
\def\pst@repeatarrowsflag{\z@}%
\def\pst@linetype{0}}
\def\end@OpenObj{%
\ifpsshadow \pst@openshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifnum\pst@repeatarrowsflag>\z@ \pst@repeatarrows \fi
\ifshowpoints \pst@OpenShowPoints \fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@SpecialObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\init@pscode}
\def\end@SpecialObj{%
\use@pscode
\endgroup
\ignorespaces}
\def\pst@code{}%
\def\init@pscode{%
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\addto@pscode#1{\xdef\pst@code{\pst@code#1\space}}
\def\use@pscode{%
\pstverb{%
\pst@dict
\tx@STP
\pst@newpath
\psk@origin
\psk@swapaxes
\pst@code
end}%
\gdef\pst@code{}}
\def\pst@newpath{newpath }
\def\pst@@killglue{\unskip\ifdim\lastskip>\z@\expandafter\pst@@killglue\fi}
\def\KillGlue{\let\pst@killglue\pst@@killglue}
\def\DontKillGlue{\let\pst@killglue\relax}
\DontKillGlue
\def\solid@star{%
\if@star
\pslinewidth=\z@
\psdoublelinefalse
\def\pslinestyle{none}%
\def\psk@fillstyle{\psfs@solid}%
\let\psfillcolor\pslinecolor
\fi}
\def\pst@setdoublesep{%
\pst@getlength\psdoublesep\psdoublesep
\pslinewidth=2\pslinewidth
\advance\pslinewidth\psdoublesep\p@
\let\pst@setdoublesep\relax}
\def\tx@Shadow{Shadow }
\def\pst@closedshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
gsave fill grestore
stroke
grestore
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}}
\def\pst@openshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
\ifx\psk@fillstyle\relax\else
gsave fill grestore
\fi
stroke}%
\pst@repeatarrows
\addto@pscode{grestore}
\ifx\psk@fillstyle\relax\else
\addto@pscode{%
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}
\fi}
\def\pst@addborder{%
\addto@pscode{%
gsave
\psk@border 2 mul
CLW add SLW
\pst@usecolor\psbordercolor
stroke
grestore}}
\def\pst@stroke{%
\ifx\pslinestyle\@none\else
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor
\@nameuse{psls@\pslinestyle}
grestore}%
\fi}
\def\pst@fill#1{\addto@pscode{gsave #1 grestore}}%
\def\pst@doublestroke{%
\addto@pscode{%
gsave
\psdoublesep SLW
\pst@usecolor\psdoublecolor
stroke
grestore}}
\def\pst@arrowtype{%
\ifx\psk@arrowB\@empty 0 \else -2 \fi
\ifx\psk@arrowA\@empty 0 \else -1 \fi
add}
\def\pst@addarrowdef{%
\addto@pscode{%
/ArrowA {
\ifx\psk@arrowA\@empty
\pst@oplineto
\else
\pst@arrowdef{A}
moveto
\fi
} def
/ArrowB {
\ifx\psk@arrowB\@empty \else \pst@arrowdef{B} \fi
} def}}
\def\pst@arrowdef#1{%
\ifnum\pst@repeatarrowsflag>\z@
/Arrow#1c [ 6 2 roll ] cvx def Arrow#1c
\fi
\tx@BeginArrow
\psk@arrowscale
\@nameuse{psas@\@nameuse{psk@arrow#1}}
\tx@EndArrow}
\def\pst@repeatarrows{%
\addto@pscode{%
gsave
\ifx\psk@arrowA\@empty\else
ArrowAc ArrowA pop pop
\fi
\ifx\psk@arrowB\@empty\else
ArrowBc ArrowB pop pop pop pop
\fi
grestore}}
\def\pst@OpenShowPoints{%
\addto@pscode{%
gsave
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
Points aload length 2 div 2 sub cvi /N ED
N 0 ge
{ \ifx\psk@arrowA\@empty
Dot
\else
pop pop
\fi
N { Dot } repeat
\ifx\psk@arrowB\@empty
Dot
\else
pop pop
\fi }
{ N 2 mul { pop } repeat }
ifelse
grestore}}
\def\pscustom{\pst@object{pscustom}}
\long\def\pscustom@i#1{%
\begin@SpecialObj
\solid@star
\let\pst@ifcustom\iftrue
\let\begin@ClosedObj\begin@CustomObj
\let\end@ClosedObj\endgroup
\def\begin@OpenObj{\begin@CustomObj\pst@addarrowdef}%
\let\end@OpenObj\endgroup
\let\begin@AltOpenObj\begin@CustomObj
\def\begin@SpecialObj{%
\begingroup
\pst@misplaced{special graphics object}%
\def\addto@pscode####1{}
\let\end@SpecialObj\endgroup}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\pst@repeatarrowsflag{\z@}%
\let\pst@setrepeatarrowsflag\relax
\showpointsfalse
\let\showpointstrue\relax
\def\pst@linetype{\pslinetype}%
\let\psset@liftpen\psset@@liftpen
\psset@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\def\pst@optcp##1##2{%
\ifnum##1=\z@\def##2{/currentpoint load stopped { 0 0 } if }\fi}%
\let\caddto@pscode\addto@pscode
\def\cuse@par##1{{\use@par##1}}%
\the\pst@customdefs
\setbox\pst@hbox=\hbox{#1}%
\psk@fillstyle
\pst@stroke
\end@SpecialObj}
\def\begin@CustomObj{%
\begingroup
\use@par
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\pst@oplineto{moveto }
\def\pst@cp{}
\def\pst@optcp#1#2{}
\def\psset@liftpen#1{}
\def\psset@@liftpen#1{%
\ifcase#1\relax
\def\psk@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{1}%
\def\pst@cp{}%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{2}%
\def\pst@cp{}%
\def\pst@oplineto{moveto }%
\fi}
\psset@liftpen{0}
\def\psk@liftpen{-1}
\def\psset@linetype#1{%
\pst@getint{#1}\pslinetype
\ifnum\pst@dimg<-3
\@pstrickserr{linetype must be greater than -3}\@ehpa
\def\pslinetype{0}%
\fi}
\psset@linetype{0}
\def\caddto@pscode#1{%
\@pstrickserr{Command can only be used in \string\pscustom}\@ehpa}
\let\cuse@par\caddto@pscode
\def\tx@MSave{%
/msavemtrx
[ tx@Dict /msavemtrx known { msavemtrx aload pop } if CM ]
def }
\def\tx@MRestore{%
tx@Dict /msavemtrx known { length 0 gt } { false } ifelse
{ /msavematrx [ msavematrx aload pop setmatrix ] def }
if }
\newtoks\pst@customdefs
\pst@customdefs{%
\def\newpath{\addto@pscode{newpath}}%
\def\moveto(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\closepath{\addto@pscode{closepath}}%
\def\gsave{\begingroup\addto@pscode{gsave}}%
\def\grestore{\endgroup\addto@pscode{grestore}}%
% DG/SR modification begin - May 12, 1997 - Patch 2
%\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor translate}}%
% DG/SR modification end
\def\rotate#1{\pst@@getangle{#1}\addto@pscode{\pst@angle rotate}}%
\def\scale#1{\pst@getscale{#1}\pst@tempg\addto@pscode{\pst@tempg}}%
\def\msave{\addto@pscode{\tx@MSave}}%
\def\mrestore{\addto@pscode{\tx@MRestore}}%
\def\swapaxes{\addto@pscode{-90 rotate -1 1 scale}}%
\def\stroke{\pst@object{stroke}}%
\def\fill{\pst@object{fill}}%
\def\openshadow{\pst@object{openshadow}}%
\def\closedshadow{\pst@object{closedshadow}}%
% DG/SR modification begin - Jan. 7, 1998 - Patch 8
%\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor tx@Shadow}}%
\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor \tx@Shadow}}%
% DG/SR modification end
\def\lineto{\pst@onecoor{lineto}}%
\def\rlineto{\pst@onecoor{rlineto}}%
\def\curveto{\pst@threecoor{curveto}}%
\def\rcurveto{\pst@threecoor{rcurveto}}%
\def\code#1{\addto@pscode{#1}}%
\def\coor(#1){\pst@@getcoor{#1}\addto@pscode\pst@coor\@ifnextchar({\coor}{}}%
\def\rcoor{\pst@getcoors{}{}}%
\def\dim#1{\pssetlength\pst@dimg{#1}\addto@pscode{\pst@number\pst@dimg}}%
\def\setcolor#1{%
\@ifundefined{color@#1}{}{\addto@pscode{\use@color{#1}}}}%
\def\arrows#1{{\psset@arrows{#1}\pst@addarrowdef}}%
\let\file\pst@rawfile
} % END \pst@customdefs
\def\closedshadow@i{\cuse@par\pst@closedshadow}
\def\openshadow@i{\cuse@par\pst@openshadow}
\def\stroke@i{\cuse@par\pst@stroke}%
\def\fill@i{\cuse@par\psk@fillstyle}%
\def\pst@onecoor#1(#2){%
\pst@@getcoor{#2}%
\addto@pscode{\pst@coor #1}}
\def\pst@threecoor#1(#2)#3(#4)#5(#6){%
\begingroup
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#4}\pst@tempb
\pst@getcoor{#6}\pst@tembc
\addto@pscode{\pst@tempa \pst@tempb \pst@tempc #1}%
\endgroup}
\def\pst@rawfile#1{%
\begingroup
\def\do##1{\catcode`##1=12\relax}"
\dospecials
\catcode`\%=14
\pst@@rawfile{#1}%
\endgroup}
\def\pst@@rawfile#1{%
\immediate\openin1 #1
\ifeof1
\@pstrickserr{File `#1' not found}\@ehpa
\else
\immediate\read1 to \pst@tempg
\loop
\ifeof1 \@pstfalse\else\@psttrue\fi
\if@pst
\addto@pscode\pst@tempg
\immediate\read1 to \pst@tempg
\repeat
\fi
\immediate\closein1\relax}
\def\tx@NArray{NArray }
\def\tx@NArray{NArray }
\def\tx@Line{Line }
\def\tx@Arcto{Arcto }
\def\tx@CheckClosed{CheckClosed }
\def\tx@Polygon{Polygon }
\def\psset@gangle#1{\pst@getangle{#1}\psk@gangle}
\psset@gangle{0}
\def\tx@Diamond{Diamond }
\def\psdiamond{\pst@object{psdiamond}}
\def\psdiamond@i(#1){%
\@ifnextchar({\psdiamond@ii(#1)}{\psdiamond@ii(0,0)(#1)}}
\def\psdiamond@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj}
\def\tx@Triangle{Triangle }
\def\pstriangle{\pst@object{pstriangle}}
\def\pstriangle@i(#1){%
\@ifnextchar({\pstriangle@ii(#1)}{\pstriangle@ii(0,0)(#1)}}
\def\pstriangle@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\tx@CCA{CCA }
\def\tx@CCA{CCA }
\def\tx@CC{CC }
\def\tx@IC{IC }
\def\tx@BOC{BOC }
\def\tx@NC{NC }
\def\tx@EOC{EOC }
\def\tx@BAC{BAC }
\def\tx@NAC{NAC }
\def\tx@EAC{EAC }
\def\tx@OpenCurve{OpenCurve }
\def\tx@AltCurve{AltCurve }
\def\tx@ClosedCurve{ClosedCurve }
\def\psset@curvature#1{%
\edef\pst@tempg{#1 }%
\expandafter\psset@@curvature\pst@tempg * * * \@nil}
\def\psset@@curvature#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\edef\psk@curvature{\pst@tempg \pst@temph \pst@tempi}}
\psset@curvature{1 .1 0}
\def\pscurve{\pst@object{pscurve}}
\def\pscurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\pscurve@ii}}
\def\pscurve@ii{%
\addto@pscode{%
\pst@cp
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@OpenCurve}%
\end@OpenObj}
\def\psecurve{\pst@object{psecurve}}
\def\psecurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psecurve@ii}}
\def\psecurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@AltCurve}%
\end@OpenObj}
\def\psccurve{\pst@object{psccurve}}
\def\psccurve@i{%
\begin@ClosedObj
\pst@getcoors[\psccurve@ii}
\def\psccurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@ClosedCurve}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@dotsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@@dotsize{\pst@number\pst@dimg}%
\let\psk@@@dotsize\pst@tempg
\edef\psk@dotsize{%
/DS \psk@@dotsize \psk@@@dotsize CLW mul add 2 div def }}
\psset@dotsize{2pt 2}
\def\psset@dotscale#1{%
\pst@getscale{#1}\psk@dotscale
\ifx\psk@dotscale\@empty
\def\psk@xdotscale{1 }%
\def\psk@ydotscale{1 }%
\else
\let\psk@xdotscale\pst@tempg
\let\psk@ydotscale\pst@temph
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
%\fi}
\fi
\pst@getdotsize%
\psset@dotsize{\pst@dimg\space\pst@@dimtonum\pst@dimh}}
%\psset@dotscale{1}
% DG/SR modification end
\def\pst@Getangle#1#2{%
\pst@getangle{#1}\pst@tempg
\def\pst@temph{0. }%
\ifx\pst@tempg\pst@temph
\def#2{}%
\else
\edef#2{\pst@tempg\space rotate }%
\fi}
\def\psset@dotangle#1{%
\pst@getangle{#1}\psk@@dotangle
\ifdim\psk@@dotangle\p@=\z@
\let\psk@dotangle\@empty
\else
% DG/SR modification begin - Aug. 8, 1997 - Patch 4
%\edef\psk@dotangle{\psk@@dotangle rotate }
\edef\psk@dotangle{\psk@@dotangle rotate }%
% DG/SR modification end
\fi}
\psset@dotangle{0}
\def\pst@getdotsize{%
\pst@dimg=\psk@@@dotsize\pslinewidth
\advance\pst@dimg\psk@@dotsize\p@
\pst@dimh=\psk@ydotscale\pst@dimg
\pst@dimg=\psk@xdotscale\pst@dimg
\divide\pst@dimh 2
\divide\pst@dimg 2\relax}
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
\psset@dotscale{1}
% DG/SR modification end
\def\psdot{\pst@object{psdot}}
\def\psdot@i{\@ifnextchar({\psdot@ii}{\psdot@ii(\z@,\z@)}}
\def\psdot@ii(#1){%
\begin@SpecialObj
\pst@@getcoor{#1}%
\addto@pscode{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}%
\pst@coor Dot}%
\end@SpecialObj}
\def\psdots{\pst@object{psdots}}
\def\psdots@i{%
\begin@SpecialObj
\pst@getcoors[\psdots@ii}
\def\psdots@ii{%
\addto@pscode{false \tx@NArray \psdots@iii}%
\end@SpecialObj}
\def\psdots@iii{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
n { transform floor .5 add exch floor .5 add exch itransform Dot } repeat}
% DG: dead code (to suppress until \psset@dotstyle) ? - Aug. 4, 1997
\def\tx@SQ{SQ }
\def\tx@ST{ST }
\def\tx@SP{SP }
\def\pst@gdot#1{/Dot { gsave T \psk@dotangle \psk@dotscale #1 grestore } def }
\@namedef{psds@*}{\pst@gdot{0 0 DS \tx@SD}}
\@namedef{psds@o}{%
/r2 DS CLW sub def
\pst@gdot{0 0 DS \tx@SD \pst@usecolor\psfillcolor 0 0 r2 \tx@SD}}
\@namedef{psds@square*}{%
/r1 DS .886 mul def
\pst@gdot{r1 \tx@SQ}}
\@namedef{psds@square}{%
/r1 DS .886 mul def /r2 r1 CLW sub def
\pst@gdot{r1 \tx@SQ \pst@usecolor\psfillcolor r2 \tx@SQ}}
\@namedef{psds@triangle*}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST}}
\@namedef{psds@triangle}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
/y2 y1 CLW add def /x2 y2 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST \pst@usecolor\psfillcolor x2 y2 \tx@ST}}
\@namedef{psds@pentagon*}{%
/r1 DS 1.149 mul def
\pst@gdot{r1 \tx@SP}}
\@namedef{psds@pentagon}{%
DS .93 mul dup 1.236 mul /r1 ED CLW sub 1.236 mul /r2 ED
\pst@gdot{r1 \tx@SP \pst@usecolor\psfillcolor r2 \tx@SP}}
\@namedef{psds@+}{%
/DS DS 1.253 mul def
\pst@gdot{DS 0 moveto DS neg 0 L stroke 0 DS moveto 0 DS neg L stroke}}
\@namedef{psds@|}{%
\psk@tbarsize CLW mul add 2 div /DS ED
\pst@gdot{0 DS moveto 0 DS neg L stroke}}
% DG: end dead code?
\def\psset@dotstyle#1{%
\@ifundefined{psds@#1}%
{\@pstrickserr{Dot style `#1' not defined}\@eha}%
{\edef\psk@dotstyle{#1}}}
\psset@dotstyle{*}
\def\tx@FontDot{FontDot }
\def\newpsfontdot#1[#2]#3#4{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot { moveto #4 show } bind def }}
\def\newpsfontdotH#1[#2]#3#4#5{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot {
moveto
\iftrue
gsave \pst@usecolor\psfillcolor #5 show grestore
\fi
#4 show
} bind def }}
\pstheader{pst-dots.pro}
\newpsfontdot{*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(b)}
\newpsfontdotH{o}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(c)}{(b)}
\newpsfontdotH{Bo}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(C)}{(b)}
\newpsfontdotH{triangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(t)}{(u)}
\newpsfontdotH{Btriangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(T)}{(u)}
\newpsfontdot{triangle*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(u)}
\newpsfontdotH{square}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(s)}{(r)}
\newpsfontdotH{Bsquare}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(S)}{(r)}
\newpsfontdot{square*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(r)}
\newpsfontdotH{pentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(p)}{(q)}
\newpsfontdotH{Bpentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(P)}{(q)}
\newpsfontdot{pentagon*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(q)}
% DG/SR modification begin - Mar. 18, 1997
%\newpsfontdot{diamond*}%
%[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
%\newpsfontdot{diamond}%
%[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
\newpsfontdot{diamond}%
[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
\newpsfontdot{diamond*}%
[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
% DG/SR modification end
\newpsfontdot{oplus}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.478261]{Symbol}{<C5>}
\newpsfontdot{otimes}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.475362]{Symbol}{<C4>}
\newpsfontdot{x}%
[1.8 0.0 0.0 1.8 -0.495 -0.4788]{Symbol}{<B4>}
\newpsfontdot{+}%
[2.3 0.0 0.0 2.3 -0.6486 -0.5819]{Times-Roman}{<2B>}
\newpsfontdot{asterisk}%
[2.43309 0.0 0.0 2.43309 -0.609489 -1.14477]{Times-Roman}{<2A>}
\newpsfontdot{B+}%
[2.3 0.0 0.0 2.3 -0.6555 -0.5819]{Times-Bold}{<2B>}
\newpsfontdot{Basterisk}%
[2.29358 0.0 0.0 2.29358 -0.576835 -1.08486]{Times-Bold}{<2A>}
\newpsfontdot{|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.258929 -0.712302]{Helvetica}{(|)}
[1.98413 0.0 0.0 1.38 -0.258929 -0.5]{Helvetica}{(|)}
% DG/SR modification end
\newpsfontdot{B|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.277778 -0.78302]{Helvetica-Bold}{(|)}
[1.98413 0.0 0.0 1.38 -0.277778 -0.5]{Helvetica-Bold}{(|)}
% DG/SR modification end
\iffalse
\newpsfontdot{*}%
[2.77778 0.0 0.0 2.77778 -0.638889 -0.813889]{Symbol}{<B7>}
\newpsfontdot{o}%
[3.33333 0.0 0.0 3.33333 -0.666667 -1.78167]{Symbol}{<B0>}
\newpsfontdot{Bo}%
[4.69484 0.0 0.0 4.69484 -0.78169 -2.97418]{Times-Bold}{<CA>}
\fi
\newdimen\pslinearc
\def\psset@linearc#1{\pssetlength\pslinearc{#1}}
\psset@linearc{0pt}
\def\psline{\pst@object{psline}}
\def\psline@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psline@ii}}
\def\psline@ii{%
\addto@pscode{\pst@cp \psline@iii \tx@Line}%
\end@OpenObj}
\def\psline@iii{%
\ifdim\pslinearc>\z@
/r \pst@number\pslinearc def
/Lineto { \tx@Arcto } def
\else
/Lineto /lineto load def
\fi
\ifshowpoints true \else false \fi}
\def\qline(#1)(#2){%
\def\pst@par{}%
\begin@SpecialObj
\def\pst@linetype{0}%
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
\pst@tempa moveto \pst@coor L
\@nameuse{psls@\pslinestyle}}%
\end@SpecialObj}
\def\pspolygon{\pst@object{pspolygon}}
\def\pspolygon@i{%
\begin@ClosedObj
\def\pst@cp{}%
\pst@getcoors[\pspolygon@ii}
\def\pspolygon@ii{%
\addto@pscode{\psline@iii \tx@Polygon}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@framearc#1{\pst@checknum{#1}\psk@framearc}
\psset@framearc{0}
\def\psset@cornersize#1{%
\pst@expandafter\psset@@cornersize{#1}\@nil}
\def\psset@@cornersize#1#2\@nil{%
\if #1a\relax
\def\psk@cornersize{\pst@number\pslinearc false }%
\else
\def\psk@cornersize{\psk@framearc true }%
\fi}
\psset@cornersize{relative}
\def\tx@Rect{Rect }
\def\tx@OvalFrame{OvalFrame }
\def\tx@Frame{Frame }
\def\psset@dimen#1{%
\pst@expandafter\psset@@dimen{#1}\@nil}
\def\psset@@dimen#1#2\@nil{%
\if #1o\relax
\def\psk@dimen{.5 }%
\else
\if #1m\relax
\def\psk@dimen{0 }%
\else
\if #1i\relax
\def\psk@dimen{-.5 }%
\fi
\fi
\fi}
\psset@dimen{outer}
\def\psframe{\pst@object{psframe}}
\def\psframe@i(#1){%
\@ifnextchar({\psframe@ii(#1)}{\psframe@ii(0,0)(#1)}}
\def\psframe@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{\psk@cornersize \pst@tempa \pst@coor \psk@dimen \tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj}
\def\tx@BezierNArray{BezierNArray }
\def\tx@OpenBezier{OpenBezier }
\def\tx@ClosedBezier{ClosedBezier }
\def\tx@BezierShowPoints{BezierShowPoints }
\def\psbezier{\pst@object{psbezier}}
\def\psbezier@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psbezier@ii}}
\def\psbezier@ii{%
\addto@pscode{%
% DG/SR modification begin - Apr. 28, 1997 - Patch 1
% \psbezier doesn't work inside \pscustom
%\pst@cp
% DG/SR modification end
\ifshowpoints true \else false \fi
\tx@OpenBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\end@OpenObj}
\def\pscbezier{\pst@object{pscbezier}}
\def\pscbezier@i{%
\begin@ClosedObj
\pst@getcoors[\pscbezier@ii}
\def\pscbezier@ii{%
\addto@pscode{%
\ifshowpoints true \else false \fi
\tx@ClosedBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\chardef\pst@linetype=1
\end@ClosedObj}
\def\tx@Parab{Parab }
\def\parabola{\pst@object{parabola}}
\def\parabola@i{\pst@getarrows\parabola@ii}
\def\parabola@ii#1(#2)#3(#4){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@@getcoor{#4}%
\addto@pscode{\pst@tempa \pst@coor \tx@Parab}%
\end@OpenObj}
\def\psset@gridwidth#1{\pst@getlength{#1}\psk@gridwidth}
\psset@gridwidth{.8pt}
\def\psset@griddots#1{%
\pst@cntg=#1\relax
\edef\psk@griddots{\the\pst@cntg}}
\psset@griddots{0}
\def\psset@gridcolor#1{\pst@getcolor{#1}\psgridcolor}
\psset@gridcolor{black}
\def\psset@subgridwidth#1{\pst@getlength{#1}\psk@subgridwidth}
\psset@subgridwidth{.4pt}
\def\psset@subgridcolor#1{\pst@getcolor{#1}\pssubgridcolor}
\psset@subgridcolor{gray}
\def\psset@subgriddots#1{%
\pst@cntg=#1\relax\edef\psk@subgriddots{\the\pst@cntg}}
\psset@subgriddots{0}
\def\psset@subgriddiv#1{%
\pst@cntg=#1\relax\edef\psk@subgriddiv{\the\pst@cntg}}
\psset@subgriddiv{5}
\def\psset@gridlabels#1{\pst@getlength{#1}\psk@gridlabels}
\psset@gridlabels{10pt}
\def\psset@gridlabelcolor#1{\pst@getcolor{#1}\psgridlabelcolor}
\psset@gridlabelcolor{black}
\def\tx@Grid{Grid }
\def\psgrid{\pst@object{psgrid}}
\def\psgrid@i{\@ifnextchar(%
{\psgrid@ii}{\expandafter\psgrid@iv\pic@coor}}
\def\psgrid@ii(#1){\@ifnextchar(%
{\psgrid@iii(#1)}{\psgrid@iv(0,0)(0,0)(#1)}}
\def\psgrid@iii(#1)(#2){\@ifnextchar(%
{\psgrid@iv(#1)(#2)}{\psgrid@iv(#1)(#1)(#2)}}
\def\psgrid@iv(#1)(#2)(#3){%
\begin@SpecialObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\pst@@getcoor{#3}%
\ifnum\psk@subgriddiv>1
\addto@pscode{gsave
\psk@subgridwidth SLW \pst@usecolor\pssubgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
\psk@subgriddiv\space \psk@subgriddots\space
{} 0 \tx@Grid grestore}%
\fi
\addto@pscode{gsave
\psk@gridwidth SLW \pst@usecolor\psgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
1 \psk@griddots\space { \pst@usecolor\psgridlabelcolor }
\psk@gridlabels \tx@Grid grestore}%
\end@SpecialObj}
\newif\ifpsmathbox
\psmathboxtrue
\def\pst@mathflag{\z@}
\newtoks\everypsbox
\let\pst@thisbox\relax
\long\def\pst@makenotverbbox#1#2{%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox=\hbox{%
\ifcase\pst@mathflag\or$\m@th\textstyle\or$\m@th\displaystyle\fi
{\pst@thisbox\the\everypsbox#2}%
\ifnum\pst@mathflag>\z@$\fi}%
#1}
\def\pst@makeverbbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\afterassignment\pst@beginbox
\setbox\pst@hbox\hbox}
\def\pst@beginbox{%
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\bgroup\aftergroup\pst@endbox
\pst@thisbox
\the\everypsbox}
\def\pst@endbox{%
\ifnum\pst@mathflag>\z@$\fi
\egroup
\pst@afterbox}
\def\pst@makebox{\pst@@makebox}
\def\psverbboxtrue{\def\pst@@makebox{\pst@makeverbbox}}
\def\psverbboxfalse{\def\pst@@makebox{\pst@makenotverbbox}}
\psverbboxfalse
\def\pst@longbox{%
\def\pst@makebox{%
\gdef\pst@makebox{\pst@@makebox}%
\pst@makelongbox}}
\def\pst@makelongbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox\hbox\bgroup
\aftergroup\pst@afterbox
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\begingroup
\pst@thisbox
\the\everypsbox}
\def\pst@endlongbox{%
\endgroup
\ifnum\pst@mathflag>\z@$\fi
\egroup}
\def\pslongbox#1#2{%
\@namedef{#1}{\pst@longbox#2}%
\@namedef{end#1}{\pst@endlongbox}}
\newdimen\psframesep
\def\psset@framesep#1{\pssetlength\psframesep{#1}}
\psset@framesep{3pt}
\newif\ifpsboxsep
\def\psset@boxsep#1{\@nameuse{psboxsep#1}}
\psset@boxsep{true}
\def\pst@useboxpar{%
\use@par
\if@star
\let\pslinecolor\psfillcolor
\solid@star
\let\solid@star\relax
\fi
\ifpsdoubleline \pst@setdoublesep \fi}
\def\psframebox{\pst@object{psframebox}}
\def\psframebox@i{\pst@makebox\psframebox@ii}
\def\psframebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\pslinewidth
\advance\pst@dima by \psframesep
\pst@dimc=\wd\pst@hbox\advance\pst@dimc by \pst@dima
\pst@dimb=\dp\pst@hbox\advance\pst@dimb by \pst@dima
\pst@dimd=\ht\pst@hbox\advance\pst@dimd by \pst@dima
\setbox\pst@hbox=\hbox{%
\ifpsboxsep\kern\pst@dima\fi
\begin@ClosedObj
\addto@pscode{%
\psk@cornersize
\pst@number\pst@dima neg
\pst@number\pst@dimb neg
\pst@number\pst@dimc
\pst@number\pst@dimd
.5
\tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\box\pst@hbox
\ifpsboxsep\kern\pst@dima\fi}%
\ifpsboxsep\dp\pst@hbox=\pst@dimb\ht\pst@hbox=\pst@dimd\fi
\leavevmode\box\pst@hbox
\endgroup}
\def\psdblframebox{\pst@object{psdblframebox}}
\def\psdblframebox@i{\addto@par{doubleline=true}\psframebox@i}
\def\psclip#1{%
\leavevmode
\begingroup
\begin@psclip
\begingroup
\def\use@pscode{%
\pstVerb{%
\pst@dict
/mtrxc CM def
CP CP T
\tx@STV
\psk@origin
\psk@swapaxes
newpath
\pst@code
clip
newpath
mtrxc setmatrix
moveto
0 setgray
end}%
\gdef\pst@code{}}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
\hbox to\z@{#1}%
\endgroup
\def\endpsclip{%
\end@psclip
\endgroup}%
\ignorespaces}
\def\endpsclip{\pst@misplaced\endpsclip}
\let\begin@psclip\relax
\def\end@psclip{\pstVerb{currentpoint initclip moveto}}
\def\AltClipMode{%
\def\end@psclip{\pstVerb{\pst@grestore}}%
\def\begin@psclip{\pstVerb{gsave}}}
\def\clipbox{\@ifnextchar[{\clipbox@}{\clipbox@[\z@]}}
% DG modification begin - Apr. 3, 1997
% From paulus@immd5.informatik.uni-erlangen.de (Dietrich Paulus)
%\def\clipbox@[#1]{\pst@makebox\clipbox@@{#1}}
\def\clipbox@[#1]{\pst@makebox{\clipbox@@{#1}}}
% DG modification end
\def\clipbox@@#1{%
\pssetlength\pst@dimg{#1}%
\leavevmode\hbox{%
\begin@psclip
\pst@Verb{%
CM \tx@STV CP T newpath
/a \pst@number\pst@dimg def
/w \pst@number{\wd\pst@hbox}a add def
/d \pst@number{\dp\pst@hbox}a add neg def
/h \pst@number{\ht\pst@hbox}a add def
a neg d moveto
a neg h L
w h L
w d L
closepath
clip
newpath
0 0 moveto
setmatrix}%
\unhbox\pst@hbox
\end@psclip}}
\def\psshadowbox{\pst@object{psshadowbox}}
\def\psshadowbox@i{\pst@makebox\psshadowbox@ii}
\def\psshadowbox@ii{%
\begingroup
\pst@useboxpar
\psshadowtrue
\psboxseptrue
\def\psk@shadowangle{-45 }%
\setbox\pst@hbox=\hbox{\psframebox@ii}%
\pst@dimh=\psk@shadowsize\p@
\pst@dimh=.7071\pst@dimh
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pst@dimh
\dp\pst@hbox=\pst@dimg
\pst@dimg=\wd\pst@hbox
\advance\pst@dimg\pst@dimh
\wd\pst@hbox=\pst@dimg
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox{\pst@object{pscirclebox}}
\def\pscirclebox@i{\pst@makebox\pscirclebox@ii}
\def\pscirclebox@ii{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscirclebox@iii
\box\pst@hbox}%
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox@iii{%
\if@star
\pslinewidth\z@
\pstverb{\pst@dict \tx@STP \pst@usecolor\psfillcolor
newpath \pscirclebox@iv \tx@SD end}%
\else
\begin@ClosedObj
\def\pst@linetype{4}\showpointsfalse
\addto@pscode{%
\pscirclebox@iv CLW 2 div add 0 360 arc closepath}%
\end@ClosedObj
\fi}
\def\pscirclebox@iv{%
\pst@number{\wd\pst@hbox}2 div
\pst@number{\ht\pst@hbox}\pst@number{\dp\pst@hbox}add 2 div
2 copy \pst@number{\dp\pst@hbox}sub 4 2 roll
\tx@Pyth \pst@number\psframesep add }
\def\pscirclebox@sep{%
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\divide\pst@dimb 2
\pst@dima=.5\wd\pst@hbox
\pst@pyth\pst@dima\pst@dimb\pst@dimc
\advance\pst@dimc\pslinewidth
\advance\pst@dimc\psframesep
\advance\pst@dimb-\pst@dimc
\setbox\pst@hbox=\hbox to2\pst@dimc{%
\hss
\vbox{\kern-\pst@dimb\box\pst@hbox}%
\hss}%
\advance\pst@dimb-\dp\pst@hbox
\dp\pst@hbox=-\pst@dimb}
\let\pst@nodehook\relax
\def\psCirclebox{\pst@object{psCirclebox}}
\def\psCirclebox@i{\pst@makebox\psCirclebox@ii}
\def\psCirclebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psCirclebox@sep{%
\pst@dimc=\pst@dimb
\advance\pst@dimb-\pst@dima
\advance\pst@dima\pst@dimc
\setbox\pst@hbox=\hbox to\tw@\pst@dimc{%
\hss
\vrule width \z@ depth \pst@dimb height \pst@dima
\box\pst@hbox
\hss}}%
\def\psovalbox{\pst@object{psovalbox}}
\def\psovalbox@i{\pst@makebox{\psovalbox@ii}}
\def\psovalbox@ii{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\ifpsboxsep\psovalbox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psovalbox@iii{%
\psovalbox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
0 360
\pst@number\pst@dimc CLW 2 div sub
\pst@number\pst@dimd CLW 2 div sub
\pst@number\pst@dima
\pst@number\pst@dimb
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj
\unhbox\pst@hbox}}
\def\psovalbox@iv{%
\pst@dimc=\pslinewidth\advance\pst@dimc\psframesep
\pst@dimd=\ht\pst@hbox\advance\pst@dimd\dp\pst@hbox
\pst@dima=.5\wd\pst@hbox
\pst@dimb=.5\pst@dimd\advance\pst@dimb-\dp\pst@hbox
\pst@dimd=.707\pst@dimd
\advance\pst@dimd\pst@dimc
\advance\pst@dimc.707\wd\pst@hbox}
\def\psovalbox@sep{%
\setbox\pst@hbox\hbox to 2\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\pst@dimg=\pst@dimd
\advance\pst@dimg-\pst@dimb
\dp\pst@hbox=\pst@dimg
\advance\pst@dimd\pst@dimb
\ht\pst@hbox=\pst@dimd}
\def\psdiabox{\pst@object{psdiabox}}
\def\psdiabox@i{\pst@makebox{\psdiabox@ii}}
\def\psdiabox@ii{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\ifpsboxsep\psdiabox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psdiabox@iv{%
\pst@dimg=.707\pslinewidth
\advance\pst@dimg.707\psframesep
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimc=\pst@dima
\advance\pst@dimc\pst@dimg
\pst@dimd=\ht\pst@hbox
\advance\pst@dimd\dp\pst@hbox
\divide\pst@dimd 2
\pst@dimb=\pst@dimd
\advance\pst@dimb-\dp\pst@hbox
\advance\pst@dimd\pst@dimg}
\def\psdiabox@iii{%
\psdiabox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc 2 mul \pst@number\pst@dimd 2 mul
0
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj
\box\pst@hbox}}
\def\psdiabox@sep{%
\setbox\pst@hbox\hbox to 4\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\multiply\pst@dimd 2
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\advance\pst@dimd-2\pst@dimb
\dp\pst@hbox\pst@dimd}
\def\psset@trimode#1{\pst@expandafter\psset@@trimode{#1}\@empty\@empty\@nil}
\def\psset@@trimode#1#2#3\@nil{%
\let\pst@tempg#1\relax
\ifx\pst@tempg*%
\let\psk@@trimode\@empty
\let\pst@tempg#2\relax
\else
\let\psk@@trimode\relax
\fi
\edef\psk@trimode{%
\ifx R\pst@tempg 1 \else\ifx D\pst@tempg 2
\else\ifx L\pst@tempg 3 \else 0 \fi\fi\fi}}
\psset@trimode{U}
\def\pstribox{\pst@object{pstribox}}
\def\pstribox@i{\pst@makebox{\pstribox@ii}}
\def\pstribox@ii{%
\begingroup
\pst@useboxpar
\pstribox@iii
\ifpsboxsep\pstribox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pstribox@iii{%
\pstribox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc \pst@number\pst@dimd
\ifodd\psk@trimode exch \fi
\psk@trimode -90 mul
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj
\box\pst@hbox}}
\def\pstribox@iv{%
\pst@dimh=\pslinewidth
\advance\pst@dimh\psframesep
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg 2
\edef\pst@tempa{\number\pst@dimg sp}% For use by nodes.
\ifodd\psk@trimode
\pst@dimb\pst@dimg
\else
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\fi
\ifcase\psk@trimode
\pst@dimb=-\dp\pst@hbox
\advance\pst@dimb-\pst@dimh
\or
\pst@dima=-\pst@dimh
\or
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\pst@dimh
\or
\pst@dima=\wd\pst@hbox
\advance\pst@dima\pst@dimh
\fi
\pst@dimd=\dp\pst@hbox
\advance\pst@dimd\ht\pst@hbox
\ifx\psk@@trimode\relax
\pst@dimc=\wd\pst@hbox
\advance\pst@dimc\ifodd\psk@trimode 1.447\else 1.789\fi\pst@dimh
\multiply\pst@dimc 2
\advance\pst@dimd\ifodd\psk@trimode 1.789\else 1.447\fi\pst@dimh
\multiply\pst@dimd 2
\else
\ifodd\psk@trimode
\advance\pst@dimd 1.1547\wd\pst@hbox
\advance\pst@dimd 3.4641\pst@dimh
\pst@dimc=.866\pst@dimd
\else
\advance\pst@dimd .866\wd\pst@hbox %.866=(sqrt(3)/2)
\advance\pst@dimd 3\pst@dimh
\pst@dimc=1.1547\pst@dimd % 1.1547=(2/sqrt(3))
\fi
\fi}
\def\pstribox@sep{%
\ifodd\psk@trimode
\advance\pst@dimb.5\pst@dimd
\ht\pst@hbox=\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox=\pst@dimd
\else
\setbox\pst@hbox\hbox to \pst@dimc{\hss\unhbox\pst@hbox\hss}%
\global\pst@dimg=.5\pst@dimc
\fi
\ifcase\psk@trimode
\dp\pst@hbox-\pst@dimb
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\or
\pst@dimg=.5\wd\pst@hbox
\global\advance\pst@dimg-\pst@dima
\setbox\pst@hbox\hbox to \pst@dimc{\kern-\pst@dima\box\pst@hbox\hss}%
\or
\ht\pst@hbox\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox\pst@dimd
\or
\pst@dimg=\pst@dimc
\advance\pst@dimg-\pst@dima
\global\advance\pst@dimg.5\wd\pst@hbox
\setbox\pst@hbox\hbox to \pst@dimc{%
\hss\box\pst@hbox\kern\psframesep\kern\pslinewidth}%
\fi}
\def\psset@arcsepA#1{\pst@getlength{#1}\psk@arcsepA}
\def\psset@arcsepB#1{\pst@getlength{#1}\psk@arcsepB}
\def\psset@arcsep#1{%
\psset@arcsepA{#1}\let\psk@arcsepB\psk@arcsepA}
\psset@arcsep{0}
\def\tx@ArcArrow{ArcArrow }
\def\psarc{\pst@object{psarc}}
\def\psarc@i{%
\@ifnextchar({\psarc@iii}{\psarc@ii}}
\def\psarc@ii#1{\addto@par{arrows=#1}%
\@ifnextchar({\psarc@iii}{\psarc@iii(0,0)}}
\def\psarc@iii(#1)#2#3#4{%
\begin@OpenObj
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\pssetlength\pst@dima{#2}%
\addto@pscode{\psarc@iv \psarc@v}%
\gdef\psarc@type{0}%
\showpointsfalse
\end@OpenObj}
\def\psarc@iv{%
\pst@coor /y ED /x ED
/r \pst@number\pst@dima def
/c 57.2957 r \tx@Div def
/angleA
\pst@tempa
\psk@arcsepA c mul 2 div
\ifcase \psarc@type add \or sub \fi
def
/angleB
\pst@tempb
\psk@arcsepB c mul 2 div
\ifcase \psarc@type sub \or add \fi
def
\ifshowpoints\psarc@showpoints\fi
\ifx\psk@arrowA\@empty
\ifnum\psk@liftpen=2
r angleA \tx@PtoC
y add exch x add exch
moveto
\fi
\fi}
\def\psarc@v{%
x y r
angleA
\ifx\psk@arrowA\@empty\else
{ ArrowA CP }
{ \ifcase\psarc@type add \or sub \fi }
\tx@ArcArrow
\fi
angleB
\ifx\psk@arrowB\@empty\else
{ ArrowB }
{ \ifcase\psarc@type sub \or add \fi }
\tx@ArcArrow
\fi
\ifcase\psarc@type arc \or arcn \fi}
\def\psarc@type{0}
\def\psarc@showpoints{%
gsave
newpath
x y moveto
x y r \pst@tempa \pst@tempb
\ifcase\psarc@type arc \or arcn \fi
closepath
CLW 2 div SLW
[ \psk@dash\space ] 0 setdash stroke
grestore }
\def\psarcn{\pst@object{psarcn}}
\def\psarcn@i{\def\psarc@type{1}\psarc@i}
\def\pscircle{\pst@object{pscircle}}
\def\pscircle@i{\@ifnextchar({\pscircle@do}{\pscircle@do(0,0)}}
\def\pscircle@do(#1)#2{%
\if@star
{\use@par\qdisk(#1){#2}}%
\else
\begin@ClosedObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\def\pst@linetype{4}%
\addto@pscode{%
\pst@coor
\pst@number\pst@dimc
\psk@dimen CLW mul sub
0 360 arc
closepath}%
\showpointsfalse
\end@ClosedObj
\fi
\ignorespaces}
\def\qdisk(#1)#2{%
\def\pst@par{}%
\begin@SpecialObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimg{#2}%
\addto@pscode{\pst@coor \pst@number\pst@dimg \tx@SD}%
\end@SpecialObj}
\def\psset@radius#1{\pst@@getlength{#1}\psk@radius}
\psset@radius{.25cm}
\def\psCircle{\pst@object{psCircle}}
\def\psCircle@i{\@ifnextchar({\psCircle@ii}{\psCircle@ii(0,0)}}
\def\psCircle@ii(#1){\pscircle@do(#1){\psk@radius}}
\def\pswedge{\pst@object{pswedge}}
\def\pswedge@i{\@ifnextchar({\pswedge@ii}{\pswedge@ii(0,0)}}
\def\pswedge@ii(#1)#2#3#4{%
\begin@ClosedObj
\pssetlength\pst@dimc{#2}
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\def\pst@linetype{1}%
\addto@pscode{%
\pst@coor
2 copy
moveto
\pst@number\pst@dimc \psk@dimen CLW mul sub % Adjusted radius
\pst@tempa \pst@tempb
arc
closepath}%
\showpointsfalse
\end@ClosedObj}
\def\tx@Ellipse{Ellipse }
\def\psellipse{\pst@object{psellipse}}
\def\psellipse@i(#1){\@ifnextchar(%
{\psellipse@ii(#1)}{\psellipse@ii(0,0)(#1)}}
\def\psellipse@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
0 360
\pst@coor
\ifdim\psk@dimen\p@=\z@\else
\psk@dimen CLW mul
dup 4 -1 roll sub neg 3 1 roll sub
\fi
\pst@tempa
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\multips{\@ifnextchar({\def\pst@par{}\multips@ii}{\multips@i}}
\def\multips@i#1{\def\pst@par{rot=#1}\multips@ii}
\def\multips@ii(#1){\@ifnextchar({\multips@iii(#1)}{\multips@iii(\z@,\z@)(#1)}}
\long\def\multips@iii(#1)(#2)#3#4{%
\begingroup
\use@par
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\pst@cnta=#3\relax
\init@pscode
\addto@pscode{%
\pst@tempa T \the\pst@cnta\space \pslbrace
gsave \ifx\psk@rot\@empty\else\psk@rot rotate \fi}%
\hbox to\z@{%
\def\init@pscode{%
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}%
\def\use@pscode{\addto@pscode{grestore}}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
#4}%
\addto@pscode{grestore \pst@coor T \psrbrace repeat}%
\leavevmode
\use@pscode
\endgroup
\ignorespaces}
\def\scalebox#1{\pst@makebox{\@scalebox{#1}}}
\def\@scalebox#1{%
\begingroup
\pst@getscale{#1}\pst@tempa
\let\pst@tempc\pst@tempg
\let\pst@tempd\pst@temph
\@@scalebox
\endgroup}
\def\@@scalebox{%
\leavevmode
\hbox{%
\ifdim\pst@tempd\p@<\z@
\pst@dimg=\pst@tempd\ht\pst@hbox
\pst@dimh=\pst@tempd\dp\pst@hbox
\dp\pst@hbox=-\pst@dimg
\ht\pst@hbox=-\pst@dimh
\else
\ht\pst@hbox=\pst@tempd\ht\pst@hbox
\dp\pst@hbox=\pst@tempd\dp\pst@hbox
\fi
\pst@dima=\pst@tempc\wd\pst@hbox
\ifdim\pst@dima<\z@\kern-\pst@dima\fi
\pst@Verb{CP CP translate \pst@tempa \tx@NET}%
\hbox to \z@{\box\pst@hbox\hss}%
\pst@Verb{%
CP CP translate
1 \pst@tempc div 1 \pst@tempd div scale
\tx@NET}%
\ifdim\pst@dima>\z@\kern\pst@dima\fi}}
\pslongbox{Scalebox}{\scalebox}
\def\scaleboxto(#1,#2){\pst@makebox{\@scaleboxto(#1,#2)}}
\def\@scaleboxto(#1,#2){%
\begingroup
\pssetlength\pst@dima{#1}%
\pssetlength\pst@dimb{#2}%
\ifdim\pst@dima=\z@\else
\pst@divide{\pst@dima}{\wd\pst@hbox}\pst@tempc
\edef\pst@tempc{\pst@tempc\space}%
\fi
\ifdim\pst@dimb=\z@
\ifdim\pst@dima=\z@
\@pstrickserr{%
\string\scaleboxto\space dimensions cannot both be zero}\@ehpa
\def\pst@tempa{}%
\def\pst@tempc{1 }%
\def\pst@tempd{1 }%
\else
\let\pst@tempd\pst@tempc
\fi
\else
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc\dp\pst@hbox
\pst@divide{\pst@dimb}{\pst@dimc}\pst@tempd
\edef\pst@tempd{\pst@tempd\space}%
\ifdim\pst@dima=\z@ \let\pst@tempc\pst@tempd \fi
\fi
\edef\pst@tempa{\pst@tempc \pst@tempd scale }%
\@@scalebox
\endgroup}
\pslongbox{Scaleboxto}{\scaleboxto}
\def\tx@Rot{Rot }
\def\rotateleft{\pst@makebox{\@rotateleft\pst@hbox}}
\def\@rotateleft#1{%
\leavevmode\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{90 \tx@Rot}
\vbox to \z@{\vss\hbox to \z@{\box#1\hss}\vskip\z@}%
\pst@Verb{-90 \tx@Rot}}}}
\def\rotateright{\pst@makebox{\@rotateright\pst@hbox}}
\def\@rotateright#1{%
\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{-90 \tx@Rot}
\vbox to \z@{\hbox to \z@{\hss\box#1}\vss}%
\pst@Verb{90 \tx@Rot}}}}
\def\rotatedown{\pst@makebox{\@rotatedown\pst@hbox}}
\def\@rotatedown#1{%
\hbox{\hskip\wd#1\vbox{\vskip\ht#1\vskip\dp#1%
\pst@Verb{180 \tx@Rot}%
\vbox to \z@{\hbox to \z@{\box#1\hss}\vss}%
\pst@Verb{-180 \tx@Rot}}}}
\pslongbox{Rotateleft}{\rotateleft}
\pslongbox{Rotateright}{\rotateright}
\pslongbox{Rotatedown}{\rotatedown}
\def\pst@starbox{%
\setbox\pst@hbox\hbox{\psframebox*[boxsep=false]{\unhbox\pst@hbox}}}
\def\pst@@makesmall#1{%
\setbox#1=\hbox to\z@{\hss\vbox to \z@{\vss\box#1\vss}\hss}}
\def\pst@@@makesmall#1{%
\pst@dimh=\psk@xref\wd#1%
\ifx\psk@yref\relax
\pst@dimg=\dp#1%
\else
\pst@dimg=\psk@yref\ht#1%
\advance\pst@dimg\psk@yref\dp#1%
\fi
\setbox#1=\hbox to\z@{%
\kern-\pst@dimh\vbox to\z@{\vss\box#1\kern-\pst@dimg}\hss}}
\def\psset@ref#1{\pst@expandafter\psset@@ref{#1}\@empty,,\@nil}
\def\psset@@ref#1#2,#3,#4\@nil{%
\def\psk@xref{.5}%
\def\psk@yref{.5}%
\let\pst@makesmall\pst@@@makesmall
\ifx\@empty#3\@empty
\@nameuse{getref@#1}%
\@nameuse{getref@#2}%
\else
\pst@checknum{#1#2}\psk@xref
\pst@checknum{#3}\psk@yref
\fi}
\def\getref@c{\let\pst@makesmall\pst@@makesmall}
\def\getref@t{\def\psk@yref{1}}
\def\getref@b{\def\psk@yref{0}}
\def\getref@B{\let\psk@yref\relax}
\def\getref@l{\def\psk@xref{0}}
\def\getref@r{\def\psk@xref{1}}
\psset@ref{c}
\def\psset@rot#1{%
\pst@expandafter{\@ifnextchar*{\psset@@@rot}{\psset@@rot}}{#1}\@nil}
\def\psset@@rot#1\@nil{%
\def\next##1@#1=##2@##3\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@rot
\else
\def\psk@rot{##2}%
\fi}%
\expandafter\next\pst@rottable @#1=\relax @\@nil}
\def\psset@@@rot#1#2\@nil{%
\psset@@rot#2\@nil
\edef\psk@rot{\pst@rotlist \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\def\pst@rotlist{mark RAngle /a ED cleartomark a neg }
\def\pst@rottable{%
@0=%
@U=%
@L=90 %
@D=180 %
@R=-90 %
@N=\pst@rotlist
@W=\pst@rotlist 90 add %
@S=\pst@rotlist 180 add %
@E=\pst@rotlist 90 sub }
\psset@rot{0}
\def\tx@RotBegin{RotBegin }
\def\tx@RotEnd{RotEnd }
\def\pst@rotate#1#2{%
\ifx#1\@empty\else
\setbox#2=\hbox{\pst@Verb{#1 \tx@RotBegin}\box#2\pst@Verb{\tx@RotEnd}}%
\fi}
\def\psput@cartesian#1{%
\hbox to \z@{\kern\pst@dimg{\vbox to \z@{\vss\box#1\vskip\pst@dimh}\hss}}}
\def\psput@special#1{%
\hbox{%
\pst@Verb{{ \pst@coor } \tx@PutCoor \tx@PutBegin}%
\box#1%
\pst@Verb{\tx@PutEnd}}}
\def\tx@PutCoor{PutCoor }
\def\tx@PutBegin{PutBegin }
\def\tx@PutEnd{PutEnd }
\def\rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\rput@i}{\rput@ii}}}
\def\rput@i[#1]{\addto@par{ref={#1}}\rput@ii}
\def\rput@ii{\@ifnextchar({\rput@iv}{\rput@iii}}
\def\rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\rput@iv}{\rput@iv(\z@,\z@)}}
\def\rput@iv(#1){\pst@killglue\pst@makebox{\rput@v{#1}}}
\def\rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\multirput{%
\def\pst@par{}%
\pst@ifstar{\@ifnextchar[{\multirput@i}{\multirput@ii}}}
\def\multirput@i[#1]{\addto@par{ref={#1}}\multirput@ii}
\def\multirput@ii{\@ifnextchar({\multirput@iv}{\multirput@iii}}
\def\multirput@iii#1{\addto@par{rot={#1}}\multirput@iv}
\def\multirput@iv(#1){%
\@ifnextchar({\multirput@v(#1)}{\multirput@v(\z@,\z@)(#1)}}
\def\multirput@v(#1,#2)(#3,#4)#5{%
\pst@makebox{\multirput@vi(#1,#2)(#3,#4){#5}}}
\def\multirput@vi(#1,#2)(#3,#4)#5{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\pssetxlength\pst@dima{#1}%
\pssetylength\pst@dimb{#2}%
\pssetxlength\pst@dimc{#3}%
\pssetylength\pst@dimd{#4}%
\pst@cntg=#5\relax
\pst@cnth=\@ne
\leavevmode
\loop
\vbox to \z@{%
\vss
\hbox to \z@{\kern\pst@dima\copy\pst@hbox\hss}%
\vskip\pst@dimb}%
\ifnum\pst@cntg>\pst@cnth
\advance\pst@dima\pst@dimc
\advance\pst@dimb\pst@dimd
\advance\pst@cnth\@ne
\repeat
\endgroup
\ignorespaces}
\newif\if@fixedradius
\def\cput{\pst@object{cput}}
\def\cput@i{\@fixedradiusfalse\cput@ii}
\def\cput@ii{\pst@killglue\@ifnextchar({\cput@iv}{\cput@iii}}
\def\cput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cput@iv}{\cput@iv(\z@,\z@)}}
\def\cput@iv(#1){\pst@makebox{\cput@v{#1}}}
\def\cput@v#1{%
\begingroup
\use@par
\setbox\pst@hbox=\hbox{%
\psboxsepfalse
\if@fixedradius\psCirclebox@ii\else\pscirclebox@ii\fi}%
\pst@@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Cput{\pst@object{Cput}}
\def\Cput@i{\@fixedradiustrue\cput@ii}
\newdimen\pslabelsep
\def\psset@labelsep#1{\pssetlength\pslabelsep{#1}}
\psset@labelsep{5pt}
\def\psset@refangle#1{\pst@expandafter\psset@@refangle{#1}\@nil}
\def\psset@@refangle#1\@nil{%
\def\next##1@#1=##2"##3@##4\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@refangle
\def\psk@uputref{}%
\else
\def\psk@refangle{##2 }%
\def\psk@uputref{##3}%
\fi}%
\expandafter\next\pst@refangletable @#1=\relax"@\@nil}
\def\pst@refangletable{%
@r=0"20%
@u=90"02%
@l=180"10%
@d=-90"01%
@ur=45"22%
@ul=135"12%
@dr=-135"21%
@dl=-45"11}
\psset@refangle{0}
% DG/SR modification begin - Mar. 24, 1999 - Patch 10
%\def\uput{\def\pst@par{}\@ifnextchar[{\uput@ii}{\uput@i}}
\def\uput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\uput@ii}{\uput@i}}} 
% DG/SR modification end
\def\uput@i#1{\addto@par{labelsep=#1}\uput@ii}
\def\uput@ii[#1]{%
\addto@par{refangle={#1}}%
\@ifnextchar({\uput@iv}{\uput@iii}}
\def\uput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\uput@iv}{\uput@iv(\z@,\z@)}}
\def\uput@iv(#1){\pst@killglue\pst@makebox{\uput@v{#1}}}
\def\uput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\uput@vi
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\uput@vi{%
\ifx\psk@uputref\@empty
\uput@vii\tx@UUput{}%
\else
\ifx\psk@rot\@empty
\expandafter\uput@viii\psk@uputref
\else
\uput@vii\tx@UUput{}%
\fi
\fi}
\def\uput@vii#1#2{%
\edef\pst@coor{%
\pst@number\pslabelsep
#2%
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\psk@refangle\space \ifx\psk@rot\@empty\else\psk@rot\space sub \fi
\tx@Uput #1}%
\setbox\pst@hbox=\hbox to\z@{\hss\vbox to\z@{\vss\box\pst@hbox\vss}\hss}%
\setbox\pst@hbox=\psput@special\pst@hbox
\ifx\psk@rot\@empty\else\pst@rotate\psk@rot\pst@hbox\fi}
\def\uput@viii#1#2{%
\ifnum#1>\z@\ifnum#2>\z@\pslabelsep=.707\pslabelsep\fi\fi
\setbox\pst@hbox=\vbox to\z@{%
\ifnum#2=1 \vskip\pslabelsep\else\vss\fi
\hbox to\z@{%
\ifnum#1=2 \hskip\pslabelsep\else\hss\fi
\box\pst@hbox
\ifnum#1=1 \hskip\pslabelsep\else\hss\fi}%
\ifnum#2=2 \vskip\pslabelsep\else\vss\fi}}
\def\tx@Uput{Uput }
\def\tx@UUput{UUput }
\def\Rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Rput@ii}{\Rput@i}}}
\def\Rput@i#1{\addto@par{labelsep=#1}\Rput@ii}
\def\Rput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Rput@iv}{\Rput@iii}}
\def\Rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\Rput@iv}{\Rput@iv(\z@,\z@)}}
\def\Rput@iv(#1){\pst@killglue\pst@makebox{\Rput@v{#1}}}
\def\Rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Rput@vi{%
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pslabelsep
\dp\pst@hbox=\pst@dimg
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg\pslabelsep
\ht\pst@hbox=\pst@dimg
\setbox\pst@hbox\hbox{\kern\pslabelsep\box\pst@hbox\kern\pslabelsep}}%
\def\oldpsput{%
\def\pst@par{}\pst@ifstar{\@ifnextchar[{\oldpsput@i}{\oldpsput@ii}}}
\def\oldpsput@i[#1]{\addto@par{ref={#1}}\oldpsput@ii}
\def\oldpsput@ii{\@ifnextchar<{\oldpsput@iii}{\oldpsput@iv}}
\def\oldpsput@iii<#1>{\rput@iii{#1}}
\def\OldPsput{\let\psput\oldpsput}
\def\NewPsput{\let\psput\rput}
\def\pspicture{\begingroup\pst@ifstar\pst@picture}
\def\pst@picture{%
\@ifnextchar[{\pst@@picture}{\pst@@picture[0]}}
\def\pst@@picture[#1]#2(#3,#4){%
\@ifnextchar({\pst@@@picture[#1](#3,#4)}%
{\pst@@@picture[#1](0,0)(#3,#4)}}
\def\pst@@@picture[#1](#2,#3)(#4,#5){%
\pssetxlength\pst@dima{#2}%
\pssetylength\pst@dimb{#3}%
\pssetxlength\pst@dimc{#4}%
\pssetylength\pst@dimd{#5}%
\ifdim\pst@dima>\pst@dimc
\pst@dimg=\pst@dima
\pst@dima=\pst@dimc
\pst@dimc=\pst@dimg
\fi
\ifdim\pst@dimb>\pst@dimd
\pst@dimg=\pst@dimb
\pst@dimb=\pst@dimd
\pst@dimd=\pst@dimg
\fi
\def\pst@tempa{#1}%
\setbox\pst@hbox=\hbox\bgroup
\begingroup\KillGlue
\@ifundefined{@latexerr}{}{\let\unitlength\psunit}%
\edef\pic@coor{(#2,#3)(#2,#3)(#4,#5)}\ignorespaces}
\def\pic@coor{(0,0)(0,0)(10,10)}
\def\endpspicture{%
\pst@killglue
\endgroup
\egroup
\ifdim\wd\pst@hbox=\z@\else
%\@pstrickserr{Extraneous space in the pspicture environment}%
%{Type \space <return> \space to procede.}%
\fi
\ht\pst@hbox=\pst@dimd
\dp\pst@hbox=-\pst@dimb
\setbox\pst@hbox=\hbox{%
\kern-\pst@dima
\ifx\pst@tempa\@empty\else
\advance\pst@dimd-\pst@dimb
\pst@dimd=\pst@tempa\pst@dimd
\advance\pst@dimd\pst@dimb
\lower\pst@dimd
\fi
\box\pst@hbox
\kern\pst@dimc}%
\if@star\setbox\pst@hbox=\hbox{\clipbox@@\z@}\fi
\leavevmode\box\pst@hbox
\endgroup}
\@namedef{pspicture*}{\pspicture*}
\@namedef{endpspicture*}{\endpspicture}
\def\tx@BeginOL{BeginOL }
\def\tx@InitOL{InitOL }
\def\pst@initoverlay#1{\pst@Verb{\tx@InitOL /TheOL (#1) def}}
\def\AltOverlayMode{%
\def\pst@initoverlay##1{%
\pst@Verb{%
\tx@InitOL
/Visible { initclip } def
/Invisible {
CP newpath OLUnit itransform moveto clip newpath moveto
} def
/TheOL (##1) def}}}
\def\pst@overlay#1{%
\edef\curr@overlay{#1}%
\pst@Verb{(#1) BOL}%
\aftergroup\pst@endoverlay}
\def\pst@endoverlay{%
\pst@Verb{(\curr@overlay) BOL}}
\def\curr@overlay{all}
\newbox\theoverlaybox
\def\overlaybox{%
\global\setbox\theoverlaybox=\hbox\bgroup
\begingroup
\let\psoverlay\pst@overlay
\def\overlaybox{%
\@pstrickserr{Overlays cannot be nested}\@eha}%
\def\putoverlaybox{%
\@pstrickserr{You must end the overlay box
before using \string\putoverlaybox}}%
\psoverlay{main}%
\ignorespaces}
\def\endoverlaybox{\endgroup\egroup}
\def\putoverlaybox#1{%
\hbox{\pst@initoverlay{#1}\copy\theoverlaybox}}
\def\psoverlay{\@pstrickserr{\string\psoverlay\space
can only be used after \string\overlaybox}}
\ifx\pstcustomize\relax \input pstricks.con \fi
\catcode`\@=\PstAtCode\relax
%
\endinput
%%
%% END: pstricks.tex

realcalc.tex






















\ifx\Radd\undefined \else \endinput \fi


\chardef\catamp=\the\catcode`\@
\catcode`@=11
 
\def\@Rversion{Version 1.0, Jan. 1993}
\message{`Real arithmetic', \@Rversion (C) Frank Buchholz}


\newcount\@ta
\newcount\@tb

\newcount\@xs	% Sign of 1st value
\newcount\@xi	% Integer part of 1st value
\newcount\@xf	% Fractional part of 1st value

\newcount\@ys	% Sign of 2nd value
\newcount\@yi	% Integer part of 2nd value
\newcount\@yf	% Fractional part of 2nd value

\newcount\@mil	\@mil=1000000000	% 10^9

\countdef\@xa240
\countdef\@xb241
\countdef\@xc242
\countdef\@xd243
\countdef\@xe244
\countdef\@ya245
\countdef\@yb246
\countdef\@yc247
\countdef\@yd248
\countdef\@ye249
\let\@f=\@tb
\let\@product=\@ta

\chardef\@zero=0


\def\Radd#1#2#3{\@callc\@Radd#1{#2}{#3}}


\def\Rsub#1#2#3{\@callc\@Radd#1{#2}{-#3}}

\def\@Radd#1#2.#3.#4\relax#5.#6.#7\relax{%
  % #1 Macro, witch gets the result
  % #2 integer part of 1st value 
  % #3 fractional part of 1st value
  % #4 dummy to swallow everthing after the 2nd '.'
  % #5 integer part of 2nd value 
  % #6 fractional part of 2nd value
  % #7 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#2}{#3}%
  \@readvalue\@ys\@yi\@yf{#5}{#6}%
  %
  % Add integer parts
  \@ta=\@xi \advance\@ta\@yi%
  %
  % Add fractional parts if they are not zero
  \ifnum\@xf=\@zero%
    \ifnum\@yf=\@zero%
      \@tb=\@zero%
    \else%
      \@longadd%
    \fi%
  \else%
    \@longadd%
  \fi%
  %
  % Store result
  \@store#1\@ta\@tb%
}

\def\@longadd{%
    % Propagate sign to fractional parts
    \multiply\@xf\@xs \multiply\@yf\@ys%
    %
    % Add fractional parts
    \@tb=\@xf \advance\@tb\@yf%
    %
    % Calculate carry
    \ifnum\@tb<\@zero% 
      \ifnum\@tb<-\@mil      \advance\@ta -\@ne \advance\@tb\@mil  \fi% 
    \else% 
      \ifnum\@tb<\@mil \else \advance\@ta \@ne	\advance\@tb-\@mil \fi% 
    \fi%
} 


\def\Rmul#1#2#3{\@callc\@Rmul#1{#2}{#3}}

\def\@Rmul#1#2.#3.#4\relax#5.#6.#7\relax{%
  % #1 Macro, witch gets the result
  % #2 integer part of 1st value 
  % #3 fractional part of 1st value
  % #4 dummy to swallow everthing after the 2nd '.'
  % #5 integer part of 2nd value 
  % #6 fractional part of 2nd value
  % #7 dummy to swallow everthing after the 2nd '.'
  %
  % How to do real multiplications:
  % Split values in various parts
  % x y = 1234 567890 . 123 456 789
  % ->	  xa   xb	xc  xd	xe
  % ->	  ya   yb	yc  yd	ye
  % Do 21 (!) integer multiplications if there are any fractional parts
  % r = x * Y
  % -> r =   xi*yi
  %	   + (xa*yc + xa*yc		     )*10^3 
  %	   + (xa*yd + xd*ya		     )*10^-0 
  %	   + (xa*ye + xe*ya  +	xb*yc + xc*yb)*10^-3 
  %	   + (xb*yd + xd*yb  +	xc*yc	     )*10^-6 
  %	   + (xb*ye + xe*yb  +	xc*yd + xd*yc)*10^-9 
  %	   + (xc*ye + xe*yc  +	xd*yd	     )*10^-12 
  %	   + (xd*ye + xe*yd		     )*10^-15 
  %	   + (xe*ye			     )*10^-18
  %
  % -> r = ((((( xe*ye				     / 1000 
  %		+ xd*ye + xe*yd 		  ) / 1000
  %	       + xc*ye + xe*yc	+  xd*yd	 ) / 1000
  %	      + xb*ye + xe*yb  +  xc*yd + xd*yc ) / 1000
  %	     + xb*yd + xd*yb  +  xc*yc	       ) / 1000
  %	    + xa*ye + ye*xa  +	xb*yc + xc*yb ) / 1000
  %	   + xa*yd + xd*ya + (xa*yc + ya*xc)*1000 + xi*yi
  % The last three digigs are saved just before the divisions.
  %
  % Init 
  %
  \@readvalue\@xs\@xi\@xf{#2}{#3}%
  \@readvalue\@ys\@yi\@yf{#5}{#6}%
  %
  % Sign
  \multiply\@xi\@xs%
  \multiply\@yi\@ys%
  \multiply\@xs\@ys%
  %
  \@product=\@zero%
  % 
  \ifnum\@xf=\@zero%
    \ifnum\@yf=\@zero%
      % No fractional parts
      \edef\@frac{000000000}	% digits of fractional part  
    \else%
      \@longmul			% Long multiplication		
    \fi%
  \else%
    \@longmul			% Long multiplication		
  \fi%
  %
  % Multiply integer parts
  \count@=\@xi \multiply\count@\@yi%
  \advance\@product\count@%
  %
  % Sign
  \multiply\@product\@xs%
  %
  % Store result
  \edef#1{\number\@product.\@frac}%
}


\def\@longmul{%
    % Split values in pieces
    \@f=1000000%
    \count@=\@xi%		
    \divide\count@\@f					\@xa=\count@%
    \multiply\count@-\@f	\advance\count@\@xi	\@xb=\count@%
    \count@=\@xf%		
    \divide\count@\@f					\@xc=\count@%
    \multiply\count@-\@f	\advance\count@\@xf%	
    \@f=1000%
    \@xe=\count@%
    \divide\count@\@f					\@xd=\count@%
    \multiply\count@-\@f	\advance\count@\@xe	\@xe=\count@%
    % 
    \@f=1000000%
    \count@=\@yi%		
    \divide\count@\@f					\@ya=\count@%
    \multiply\count@-\@f	\advance\count@\@yi	\@yb=\count@%
    \count@=\@yf%		
    \divide\count@\@f					\@yc=\count@%
    \multiply\count@-\@f	\advance\count@\@yf%	
    \@f=1000%
    \@ye=\count@%
    \divide\count@\@f					\@yd=\count@%
    \multiply\count@-\@f	\advance\count@\@ye	\@ye=\count@%
    %
    \edef\@frac{} 				% digits of fractional part
    % 
    \@mul ee	      \relax\@shift		% 10^-18
    \@mul de ed       \relax\@shift		% 10^-15
    \@mul ce ec dd    \relax\@shift		% 10^-12
    \@mul be eb cd dc \relax\@saveshift		% 10^-9
    \@mul bd db cc    \relax\@saveshift		% 10^-6
    \@mul ae ea bc cb \relax\@saveshift		% 10^-3
    \multiply\@xa\@f  \multiply\@xc\@f		% 10^3
    \@mul ad da ac ca \relax%			
}

\def\@mul#1#2#3{%
  \count@=\csname @x#1\endcsname%
  \multiply\count@\csname @y#2\endcsname%
  \advance\@product\count@%
  %
  \ifx#3\relax%
    \let\next=\relax% 
  \else%
    \let\next=\@mul%
  \fi%
  \next#3%
}

\def\@shift{%
  \divide\@product\@f%
}

\def\@saveshift{%
  % Save rightmost digits 
  \count@=\@product%
  \divide\@product\@f%
  \multiply\@product\@f%
  \advance\count@-\@product%
  \advance\count@\@f%
  \edef\@frac{\expandafter\@ignorenext\number\count@\@frac}%
  %
  \divide\@product\@f%
}


\def\Rdiv#1#2#3{\@callc\@Radd#1{#2}{#3}}

\def\@Rdiv#1#2.#3.#4\relax#5.#6.#7\relax{%
  % #1 Macro, witch gets the result
  % #2 integer part of 1st value 
  % #3 fractional part of 1st value
  % #4 dummy to swallow everthing after the 2nd '.'
  % #5 integer part of 2nd value 
  % #6 fractional part of 2nd value
  % #7 dummy to swallow everthing after the 2nd '.'
  %
  \message{Error: Rdiv not ready}
  %
  \@readvalue\@xs\@xi\@xf{#2}{#3}%
  \@readvalue\@ys\@yi\@yf{#5}{#6}%
  %
  \ifnum\@yi=\@zero
    \@xi=\@zero
  \else
    \divide\@xi\@yi
  \fi
  %
  \@store#1\@xi\@xf%
}


\def\Rneg#1#2{%
  % Expand the value and split it into the integer and the fractional part
  \edef\next{\noexpand\@Rneg\noexpand#1#2..\noexpand\relax}%
  \next%
}

\def\@Rneg#1#2.#3.#4\relax{
  % #1 Macro, witch gets the result
  % #2 Integer part of value
  % #3 Fractional part of value
  % #4 Remaining tokens
  %
  \@readvalue\@xs\@xi\@xf{#2}{#3}%
  %
  % Change sign
  \multiply\@xi-\@ne%
  \multiply\@xf-\@xs%
  % 
  % Store result
  \@store#1\@xi\@xf%
}



\def\Rtrunc#1#2#3{%
  % Expand parameter and split the value into the integer and fractional part 
  \edef\next{\noexpand\@Rtrunc\noexpand#1#2#3..\noexpand\relax}%
  \next%
}

\def\@Rtrunc#1#2#3.#4.#5\relax{%
  % #1 Macro, witch gets the result
  % #2 Number of decimal places
  % #3 Integer part of value
  % #4 Fractional part of value
  % #5 dummy to swallow everthing after the 2nd '.'
  %
  \count@=#2%
  \edef\next{\empty}%
  \ifnum\count@>\@zero%
    \expandafter\@@Rtrunc#4000000000\relax%
  \fi%
  \edef#1{#3\next}%
}

\def\@@Rtrunc#1#2#3#4#5#6#7#8#9{%
  % #1...#9 fractional part, padded with trailing zeros
  \edef\next{.#1%
    \ifnum\count@>1 #2\fi%
    \ifnum\count@>2 #3\fi%
    \ifnum\count@>3 #4\fi%
    \ifnum\count@>4 #5\fi%
    \ifnum\count@>5 #6\fi%
    \ifnum\count@>6 #7\fi%
    \ifnum\count@>7 #8\fi%
    \ifnum\count@>8 #9\fi%
  }%
  \@swallow%
}



\def\Rifle#1#2{\@callb\@Rifle{#1}{#2}}

\def\@Rifle#1.#2.#3\relax#4.#5.#6\relax{%
  % #1 integer part of 1st value 
  % #2 fractional part of 1st value
  % #3 dummy to swallow everthing after the 2nd '.'
  % #4 integer part of 2nd value 
  % #5 fractional part of 2nd value
  % #6 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  \@readvalue\@ys\@yi\@yf{#4}{#5}%
  %
  \ifnum\@xs<\@ys% 
    \Rtesttrue% 
  \else%
    \ifnum\@xs>\@ys% 
      \Rtestfalse%
    \else%
      \Rtestfalse%
      \ifnum\@xi<\@yi \Rtesttrue \fi%
      \ifnum\@xi=\@yi%
	\multiply\@xf\@xs \multiply\@yf\@ys%
	\ifnum\@xf<\@yf \Rtesttrue \fi% 
      \fi%
    \fi%
  \fi%
  %
  \ifRtest%
}


\def\Rifeq#1#2{\@callb\@Rifeq{#1}{#2}}

\def\@Rifeq#1.#2.#3\relax#4.#5.#6\relax{%
  % #1 integer part of 1st value 
  % #2 fractional part of 1st value
  % #3 dummy to swallow everthing after the 2nd '.'
  % #4 integer part of 2nd value 
  % #5 fractional part of 2nd value
  % #6 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  \@readvalue\@ys\@yi\@yf{#4}{#5}%
  %
  \Rtestfalse%
  \ifnum\@xi=\@yi\ifnum\@xf=\@yf \Rtesttrue \fi\fi%
  \ifRtest%
}


\def\Rifgt#1#2{\@callb\@Rifgt{#1}{#2}}

\def\@Rifgt#1.#2.#3\relax#4.#5.#6\relax{%
  % #1 integer part of 1st value 
  % #2 fractional part of 1st value
  % #3 dummy to swallow everthing after the 2nd '.'
  % #4 integer part of 2nd value 
  % #5 fractional part of 2nd value
  % #6 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  \@readvalue\@ys\@yi\@yf{#4}{#5}%
  %
  \ifnum\@xs>\@ys% 
    \Rtesttrue% 
  \else%
    \ifnum\@xs<\@ys% 
      \Rtestfalse% 
    \else%
      \Rtestfalse%
      \ifnum\@xi>\@yi \Rtesttrue \fi%
      \ifnum\@xi=\@yi% 
	\multiply\@xf\@xs \multiply\@yf\@ys%
	\ifnum\@xf>\@yf \Rtesttrue \fi% 
      \fi%
    \fi%
  \fi%
  %
  \ifRtest%
}


\def\Rifneg#1{\@calla\@Rifneg{#1}}

\def\@Rifneg#1.#2.#3\relax{%
  % #1 Integer part of value
  % #2 Fractional part of value
  % #3 dummy to swallow everthing after the 2nd '.'
   %
   \@readvalue\@xs\@xi\@xf{#1}{#2}%
   %
   \ifnum\@xs<0 \Rtesttrue \else \Rtestfalse \fi%
   \ifRtest%
 }


\def\Rifzero#1{\@calla\@Rifzero{#1}}

\def\@Rifzero#1.#2.#3\relax{%
  % #1 Integer part of value
  % #2 Fractional part of value
  % #3 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  %
  \Rtestfalse%
  \ifnum\@xi=\@zero \ifnum\@xf=\@zero \Rtesttrue \fi \fi%
  \ifRtest%
}



\def\Rifpos#1{\@calla\@Rifpos{#1}}

\def\@Rifpos#1.#2.#3\relax{%
  % #1 Integer part of value
  % #2 Fractional part of value
  % #3 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  %
  \ifnum\@xs<0 \Rtestfalse \else \Rtesttrue \fi%
  \ifRtest%
}



\def\Rifint#1{\@calla\@Rifint{#1}}

\def\@Rifint#1.#2.#3\relax{%
  % #1 Integer part of value
  % #2 Fractional part of value
  % #3 dummy to swallow everthing after the 2nd '.'
  %
  \@readvalue\@xs\@xi\@xf{#1}{#2}%
  %
  \ifnum\@xf=0 \Rtesttrue \else \Rtestfalse \fi%
  \ifRtest%
}



\def\@calla#1#2{%
  % #1 Macro to call
  % #2 Value
  % Expand the value and split them into the integer and the fractional part
  \edef\next{\noexpand#1#2..\noexpand\relax}%
  \next%
}

\def\@callb#1#2#3{%
  % #1 Macro to call
  % #2 1st value
  % #3 2nd value
  % Expand the values and split them into the integer and the fractional parts 
  \edef\next{\noexpand#1#2..\noexpand\relax#3..\noexpand\relax}%
  \next%
}

\def\@callc#1#2#3#4{%
  % #1 Macro to call
  % #2 Macro, witch gets the result
  % #3 1st value
  % #4 2nd value
  % Expand the values and split them into the integer and the fractional parts
  \edef\next{\noexpand#1\noexpand#2#3..\noexpand\relax#4..\noexpand\relax}%
  \next%
}


\newif\ifRtest




\def\@readvalue#1#2#3#4#5{%
  % #1	  macro to catch the sign ( -1 or 1 )
  % #2	  macro to catch the integer part (maybe negative)
  % #3	  macro to catch the fractional part (positive)
  % #4.#5 value
  %
  % Regular expression [-...d]d...["."[d...]]
  % Attention: There has to be at least one digit between "-" and "."!
  %
  % Integer part
  \if !#4! #2=\@zero \else #2=#4 \fi%
  %
  % Sign
  \ifnum#2<\@zero #1=-\@ne \else #1=\@ne \fi%
  \ifnum#2=\@zero \ifnum #4#5<\@zero #1=-\@ne \fi \fi%
  %
  % Fractional part
  \if !#5!% 
    #3=\@zero%
  \else%
    \@@setcount@#5000000000\relax%
    #3=\count@%
  \fi%
}


\def\@@setcount@#1#2#3#4#5#6#7#8#9{%
  % #1...#9 fractional part, padded with '0'
  \count@=#1#2#3#4#5#6#7#8#9%
  \@swallow%
}


\def\@swallow#1\relax{}




\def\@store#1#2#3{%
  % #1 marcro to catch the result
  % #2 counter with integer part (maybe negative)
  % #3 counter with fractional part (maybe negative}
  % 
  % Sign
  \edef#1{}%
  \count@=#3%
  \ifnum\count@<\@zero% 
    \count@=-\count@%
    \ifnum#2=\@zero% 
      \edef#1{-}%
    \fi%
  \fi%
  %
  % Pad fractional part with leading zeros
  \advance\count@\@mil%
  %
  % Store result 
  \edef#1{#1\number#2.\expandafter\@ignorenext\number\count@}%
}


\def\@ignorenext#1{}


\catcode`\@=\catamp

validity.tex


\section{Test Case  Validity}
\label{section:validity}

We now define the validity of a test case w.\,r.\,t.\ a well-formed test
purpose. Our definition is different from the available conformance relations
for labeled transition systems because it assigns different roles to
test case and SUT.  We show that the well-formedness conditions on
MSCs from the previous section suffice to guarantee the existence of a
valid test case.  Moreover, we give a simple decision procedure that
decides validity of a test case and prove its correctness.



First, we need to formalize the notion of a test case. Intuitively,
a test case interacts with the SUT by means of exchanging messages
and finally assigning a verdict.  Formally, we model a test case as
follows:

\paragraph*{Test Cases.} A \emph{test case} is a partial function $\TS : \ObsAlph^* \pfun
\ObsSend \mathrel{\dot \cup} \{ \delta \} \mathrel{\dot \cup}
\FinVerdicts$, where $\delta$ is a symbol that denotes
\emph{quiescence} of the test case.


A \emph{run} of a test case $\TS$ is a sequence $\sigma_0, \sigma_1, \ldots, \sigma_n$,
of words from $\ObsAlph^*$ such that $\sigma_0 = \epsilon$, 
and $\sigma_i \xrightarrow[\TS]{} \sigma_{i + 1}$ for $0 \leq i < n$, where the
relation $\xrightarrow[\TS]{}$ is defined by
\begin{gather*}
\sigma \xrightarrow[\TS]{} \sigma a \dfeq 
\TS(\sigma)\ \text{defined} \And \left(\TS(\sigma) = a \in \ObsSend \Or
  \TS(\sigma) = \delta \And a \in \ObsRec\right)
\end{gather*}
A run $\sigma_0, \sigma_1, \ldots, \sigma_n$ is called
\emph{complete} if $\TS(\sigma_n) \in \FinVerdicts$.
Note that it is indeed impossible to extend a complete run due to the
definition of $\xrightarrow[\TS]{}$.











In the following we will show how to model test case validity as a
certain language inclusion problem.

\paragraph*{Test Languages.} 
Both the runs of a test case and the tester observable traces of a
well-formed test purpose naturally induce \emph{test languages}, i.\,e.,
languages $L \subseteq \ObsAlph^*$ together with a verdict assignments $\ver_L$:

For a test case $\TS$, the test language $\<L_\TS, \ver_\TS>$ is
defined by $L_\TS \df \{ \sigma \in \ObsAlph^* : \epsilon
\xrightarrow[\TS]{}^* \sigma \}$ with verdict assignment $\ver_\TS$
defined by
$$\ver_\TS(\sigma) \df \begin{cases} \TS(\sigma), & \text{if}\ 
  \TS(\sigma)
  \in \FinVerdicts; \\
  \Vnone, & \text{otherwise}.
\end{cases}
$$

For a well-formed test purpose $\mathscr{M}$, the induced test
language $\<L_{\mathscr{M}}, \ver_{\mathscr{M}}>$ is defined by
setting $L_{\mathscr{M}} \df \obs(X_{\mathscr{M}})$ and, for $\sigma
\in L_{\mathscr{M}}$, $\ver_{\mathscr{M}}(\sigma) \df
\ver_{\mathscr{M}}(\mathbit{x})$ for the (due to \ref{enum:wf2} uniquely
defined) $\mathbit{x} \in X_{\mathscr{M}}$ with $\sigma \in
\obs(\mathbit{x})$.


It can easily be shown that $v_\TS$ and $v_{\mathscr{M}}$ are
well-defined and satisfy the requirements imposed on verdict
assignments.

What is the correct relation between $\<L_{\mathscr{M}},
\ver_{\mathscr{M}}>$ and $\<L_{\TS}, \ver_{\TS}>$ to define validity
of $\TS$ w.\,r.\,t.\ $\mathscr{M}$? Clearly, $\ver_{\mathscr{M}}$ and
$\ver_{\TS}$ should agree on $L_{\mathscr{M}} \cap L_{\TS}$. But what
is the right relations between $L_{\mathscr{M}}$ and $L_{\TS}$? None
of the ``obvious'' choices leads to a satisfactory notion of validity:
\begin{itemize}
\item if we would require $L_{\mathscr{M}} \subseteq L_{\TS}$ then
  there would be no valid test cases for any test purpose that allows
  (inessential) choice between two actions $a,b \in \ObsSend$ because
  $L_{\mathscr{M}}$ contains traces for both  choices while a
  deterministic test case would be limited to only a single choice.
\item requiring $L_{\TS} \subseteq L_{\mathscr{M}}$ would allow the
  test case to send arbitrary messages to the SUT even though these
  would not be specified in the test purpose
\item if we require $L_{\TS} \cap L_{\mathscr{M}} \neq \emptyset$ then
  the test case would only be required to react to one of the possible
  many (essential) choices that the SUT might have.
\end{itemize}


While the first option matches the intuitive meaning of test case
validity best, it needs to be modified to eliminate the influence of
inessential choice. This is done by means of the following equivalence
relation on strings:

Let $L \subseteq \ObsAlph^*$ be a language.  We define an equivalence
relation $\mathord\simeq_{L} \subseteq L \times L$ by setting
$\sigma \simeq_{L} \rho \dfeq \text{$\rho$ is a permutation of $\sigma$ such that 
$\sigma \res \ObsRec = \rho \res \ObsRec$}$.
The {\em equivalence class\/} w.\,r.\,t. $\simeq_{L}$ of $\sigma \in
L$ is denoted by $[\sigma]_{L} \df \{\rho \in L: \sigma \simeq_{L}
\rho\}$.









\paragraph*{Test Case Validity.} 
Let $\mathscr{M}$ be a well-formed  test purpose
and $\TS$ be a test case for $\mathscr{M}$. Then $\TS$ is called a
\emph{valid} test case w.\,r.\,t.\ $\mathscr{M}$ if
\begin{itemize}
\item for every $\sigma \in L_{\TS} \cap L_{\mathscr{M}}$,
  $\ver_{\TS}(v) = \ver_{\mathscr{M}}(v)$, and
\item for every $\sigma \in L_{\mathscr{M}}$ with
  $\ver_{\mathscr{M}}(\sigma) \in \FinVerdicts$,
  $[\sigma]_{L_{\mathscr{M}}} \cap L_{\TS} \neq \emptyset$.
\end{itemize}






Since we have given the definition both for well-formed test purposes
and test case validity, it would be futile to use one to justify the
other.  What can be shown formally though, is that these notions are
compatible in the following sense:

\begin{theorem}\label{theo:valid-tester-exists}
  Let $\mathscr{M}$ be a well-formed test purpose. Then there exists a
  test case $\TS$ that is valid w.\,r.\,t.\ $\mathscr{M}$. $\TS$ can be
  computed effectively from $\mathscr{M}$.
\end{theorem} 

Also, it is easy to see that there are MSCs that violate
one of the well-formedness conditions, for which no valid test case
exists.

\paragraph*{Deciding Validity.}

In the following we present an algorithm that decides validity of a
test case w.\,r.\,t.\ a well-formed test purpose and establish the
algorithm's correctness. Interestingly, the algorithm does not require
the calculation of the $\simeq_{L_{\MS}}$-classes but only refers to
$\obs(X_{\MS})$, $\ver_\MS$, and $L_\MS$, which can easily be derived
from $\MS$.


\medskip

\begin{algo}
\small
\begin{tabbing}
\quad\=\quad\=\quad\=\quad\=\quad\=\quad\=\quad\=\quad\=\quad\=\kill
\>{\bfseries valid}$(${\it test\_purpose}  $\mathscr{M}$; {\it test\_case} $\TS$; {\it string} $\rho)$ \{\\
\>\>    \textbf{if} $\TS(\rho)$ \textit{is undefined} \textbf{then fail};\\
\>\>    \textbf{if} $\TS(\rho) \in \FinVerdicts \And \TS(\rho) \neq \ver_{\mathscr{M}}(\rho)$ \textbf{then fail};\\
\>\>    \textbf{else if} $\TS(\rho) = \delta$ \textbf{then}\\
\>\>\>      \textbf{if} {\it en}$(\mathscr{M},\rho) \cap \ObsRec = \emptyset$ \textbf{then fail};\\
\>\>\>      \textbf{else foreach} $a \in$ {\it en}$(\mathscr{M},\rho) \cap \ObsRec$ \textbf{do} {\it valid}$(\MS, \TS, \rho \cdot a)$;\\
\>\>   \textbf{else if} $\rho \cdot \TS(\rho) \not\in L_{\mathscr{M}}$ \textbf{then fail};\\
\>\>    \textbf{else} {\it valid }$(\MS, \TS, \rho \cdot \TS(\rho))$;\\
\>\>    \textbf{success};\\
\>$\}$\\
\>where {\it en}$(\mathscr{M},\rho) \df \{ a \in \ObsAlph : \rho \cdot a \in \obs(X_{\mathscr{M}}) \}$
\end{tabbing}
\vspace*{-.5cm}
\caption{\label{algo:valid}Validation algorithm.}
\end{algo}


\begin{theorem}\label{theorem:alg-correct}
  Let $\mathscr{M}$ a well-formed test purpose and
  $\TS$ a test case for $\mathscr{M}$. Then $\TS$ is valid w.\,r.\,t.\
  $\mathscr{M}$ iff {\it valid}$(\mathscr{M}, \TS, \epsilon)$ does not
  fail.
\end{theorem}

















 \endinput







corr.bbl
\begin{thebibliography}{10}

\bibitem{benabdallah97syntactic}
H.~Ben-Abdallah and S.~Leue.
\newblock Syntactic detection of process divergence and non-local choice in
  message sequence charts.
\newblock In {E. Brinksma}, editor, {\em {T}ools and {A}lgorithms for the
  {C}onstruction and {A}nalysis of {S}ystems}, volume 1217 of {\em Lecture
  Notes in Computer Science}, pages 259--274. Springer Verlag, 1997.

\bibitem{deussen98a}
P.~Deussen.
\newblock Concurrent automata.
\newblock Technical Report 1-05/1998, Brandenburg Tech. Univ. Cottbus, 1998.

\bibitem{etsi01:TTCN3}
ETSI.
\newblock The tree and tabular combined notation version 3; part 1: {TTCN-3}
  core language.
\newblock Technical Report ES 201 873-1, ETSI, 2001.

\bibitem{grabowski81}
J.~Grabowski.
\newblock On partial languages.
\newblock {\em Fundamenta Informaticae}, 4(2):427--498, 1981.

\bibitem{grabowski00:_ttcn_sdl_msc_inap}
J.~Grabowski and D.~Hogrefe.
\newblock {TTCN} {SDL}- and {MSC}-based specification and automated test case
  generation for inap.
\newblock In {\em Proceedings of the 8th International Conference on
  Telecommunication Systems {(ICTS'2000)} - Modeling and Analysis}, Nashville,
  March 2000.

\bibitem{ITU-Z120}
ITU-T.
\newblock {ITU-T} recommendation z.120 message sequence chart ({MSC}).
\newblock Technical report, ITU-T, 1999.

\bibitem{jonsson01:_execut_seman_msc}
B.~Jonsson and G.~Padilla.
\newblock An execution semantics of {MSC-2000}.
\newblock In R.~Reed and J.~Reed, editors, {\em Proceedings of the 10th
  Internation {{SDL}-Forum}}, number 2078 in Lecture Notes in Computer Science.
  Springer Verlag, 2001.

\bibitem{kat-lam98}
J.-P. Katoen and L.~Lambert.
\newblock Pomsets for message sequence charts.
\newblock In {\em Proc. of 1st Workshop of the {SDL} Forum Society on {SDL} and
  {MSC}, {SAM98}}, Berlin, 1998.

\bibitem{mauw-reniers97}
S.~Mauw and M.~A. Reniers.
\newblock Operational semantics for {MSC'96}.
\newblock In A.~Cavalli and D.~Vincent, editors, {\em Tutorials of the Eighth
  {SDL} Forum SDl'97: Time for Testing - {SDL}, {MSC} and Trends}, pages
  135--152, Evry, France, 1997. Institut national des t�l�communications.

\bibitem{maz95}
A.~Mazurkiewicz.
\newblock Introduction to trace theory.
\newblock In V.~Diekert and G.~Rozenberg, editors, {\em The Book of Traces},
  chapter~1, pages 3 -- 42. World Scientific, Singapore --- New Jersey ---
  London --- Hong Kong, 1995.

\bibitem{pratt86}
V.~Pratt.
\newblock Modelling concurrency with partial orders.
\newblock {\em International Journal of Parallel Programming}, 15(1):33�--71,
  1986.

\bibitem{scheurer98:_revis_compar_autom_gener_manual}
R.~Scheurer, J.~Grabowski, and D.~Hogrefe.
\newblock Revised comparison of an automatically generated and a manually
  specified test suite for the {B-ISDN} protocol {SSCOP}.
\newblock In H.~K{\"o}nig and P.~Langend{\"o}rfer, editors, {\em {FBT'98} -
  Formale Beschreibungstechniken f�r verteilte Systeme}. Shaker Verlag, Aachen,
  1998.
\newblock Available online from \url{http://www.itm.mu-luebeck.de/}.

\bibitem{schhulz02:_implem_ttcn_test_system_tri}
S.~Schhulz and T.~Vassiliou-Gioles.
\newblock Implementation of {TTCN-3} test systems using the {TRI}.
\newblock In I.~Schieferdecker, K.~H, and A.~Wolisz, editors, {\em Testing of
  Communication Systems {XIV}, Proc. of {TestCom-2002}}, pages 425--442,
  Berlin, Germany, 2002. Kluwer Academic Publishers.

\bibitem{schmitt00:_test_gener_autol_testc}
M.~Schmitt, M.~Ebner, and J.~Grabowski.
\newblock Test generation with autolink and testcomposer.
\newblock In {\em Proceedings of the 2nd Workshop of the {SDL} Forum Society on
  {{SDL}} and {MSC} ({SAM'2000})}. {SDL} Forum Society, 2000.
\newblock Proceedings available online from
  \url{http://www.irisa.fr/manifestations/2000/sam2000/}.

\end{thebibliography}
