
\def    \d      {\delta}
\def    \D      {\Delta}
\def    \e      {\varepsilon}
\def    \ee     {\varepsilon}
\def    \f      {\varphi}
\def    \Ga     {\Gamma}
\def	\gets	{\leftarrow}
\def	\hra	{\hookrightarrow}
\def    \se     {\subseteq}
\def	\y	{\gamma}

\def    \A      {{\cal A}}
\def    \B      {{\cal B}}
\def	\BA	{{\cal B}\!{\cal A}}
\def	\BP	{\mbox{{\bf P}}}
\def    \C      {{\cal C}}
\def	\gb	{{g_{\cal B}}}
\def	\gp	{{g_{\cal P}}}
\def	\Gr	{{\cal G}}
\def	\E	{E}
\def	\P	{{\cal P}}
\def	\RH	{{\it R}}


\def	\rel	{{\it rel}}
\def	\trans	{{\it trans}}
\def	\eps	{{\it eps}}
\def	\pre	{{\it pre}}
\def	\prestar{{\pre^*}}
\def	\post	{{\it post}}
\def	\poststar{{\post^*}}

\def	\inter	{{\it inter}}
\def	\llbr	{{\rm \{}}
\def	\rrbr	{{\rm \}}}
\def	\bebop  {Bebop}

\def  \Act  {{\it Act}}
\def \Lab  {{\it Lab}}
\def   \CP    {{\it CP}}
\def \Nat {{\bf N}}


% Transition relations

\def	\imp	{\Rightarrow}
\def	\flc	{\rightarrow}

\newcommand{\longimp}{\Longrightarrow}
\newcommand{\impp}[2]{\mathop{\Longrightarrow}\limits^{\smash{#1}}_{\smash{#2}}}
\newcommand{\impr}{\mathrel{\smash{\stackrel{r}{\Longrightarrow}}}}
\newcommand{\impplus}{\mathrel{\smash{\stackrel{+}{\Longrightarrow}}}}

\def	\longhookrightarrow{\lhook\joinrel\relbar\joinrel\rightarrow}
\def	\Longhookrightarrow{\lhook\joinrel\relbar\joinrel\relbar\joinrel\rightarrow}
\def	\Longlonghookrightarrow{\lhook\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow}
\def\tup#1{\langle #1 \rangle}
\def\Rule#1#2{\langle#1\rangle\hookrightarrow\langle#2\rangle}
\def\Ruleh#1#2#3{\langle#1\rangle\;{\buildrel#2\over\longhookrightarrow}\
		\langle#3\rangle}
\def\RuleA#1#2#3{\langle#1\rangle\;{\buildrel#2\over\longhookrightarrow}\
		\langle#3\rangle}
\def\Rulesh#1#2#3{\langle#1\rangle\;{\buildrel{\smash{#2}}\over\longhookrightarrow}\
		\langle#3\rangle}
\def\RuleH#1#2#3{\mathop{%
\hbox{\setbox0=\hbox{$\scriptstyle{#1\quad}$}{$%
\langle#1\rangle%
\mathrel{\smash{\mathop{\setbox1=\hbox to \wd0{$\lhook\kern-2pt$\rightarrowfill}\ht1=3pt\dp1=-2pt\box1}\limits^{#2}}}%
                 \langle#3\rangle$}}}}
\def\RuleSH#1#2#3{\langle#1\rangle\;{\buildrel\smash{#2}\over\Longhookrightarrow}\
                 \langle#3\rangle}
\def\RuleFH#1#2#3{\langle#1\rangle\;{\buildrel\smash{#2}\over{\mathrel{\setbox0=\hbox{$\Longhookrightarrow$}\ht0=3pt\box0}}}\langle#3\rangle}
\def\RuleLH#1#2#3{\langle#1\rangle\;{\buildrel\smash{#2}\over{\mathrel{\setbox0=\hbox{$\Longlonghookrightarrow$}\ht0=3pt\box0}}}\langle#3\rangle}

\def	\overrel#1#2{\mathrel{\mathop{\kern0pt #2}\limits^{#1}}}
\def	\underrel#1#2{\mathrel{\mathop{\kern0pt #1}\limits_{#2}}}
\def	\bothrel#1#2#3{\mathrel{\mathop{\kern0pt #2}\limits^{#1}_{#3}}}

\def\by#1{\mathop{{\hbox{\setbox0=\hbox{$\scriptstyle{#1\quad}$}{$%
\mathrel{\mathop{\setbox1=\hbox to \wd0{\rightarrowfill}\ht1=3pt\dp1=-2pt\box1}\limits^{#1}}%
$}}}}}

\def\newarrow#1{\mathop{{\hbox{\setbox0=\hbox{$\scriptstyle{#1\quad}$}{$%
\mathrel{\mathop{\setbox1=\hbox to \wd0{\rightarrowfill}\ht1=3pt\dp1=-2pt\box1}\limits^{#1}}%
$}}}}}

\def\snewarrow#1{\mathop{{\hbox{\setbox0=\hbox{$\scriptstyle{#1\quad}$}{$%
\mathrel{\smash{\mathop{\setbox1=\hbox to \wd0{\rightarrowfill}\ht1=3pt\dp1=-2pt\box1}\limits^{#1}}}%
$}}}}}

\def\fnewarrow#1{\mathop{{\hbox{\setbox0=\hbox{$\scriptscriptstyle{#1\quad}$}{$\buildrel{\smash{\>\scriptscriptstyle{#1}\>}}\over{\hbox to \wd0{\rightarrowfill}}$}}}}}

\def\smallarrow#1{\mathop{{\hbox{\setbox0=\hbox{$\scriptstyle{#1\quad}$}{$\buildrel{\,#1\>}\over{\hbox to \wd0{\rightarrowfill}}$}}}}}

\def\Newarrow#1#2{%
\setbox0=\hbox{$\scriptstyle{#1\quad}$}%
\mathrel{\mathop{\hbox to \wd0{\rightarrowfill}}\limits^{#1}_{#2}}%
}

\def\SNewarrow#1#2{%
\setbox0=\hbox{$\scriptstyle{#1\quad}$}%
\mathrel{\smash{\mathop{\setbox1=\hbox to \wd0{\rightarrowfill}\ht1=3pt\dp1=-2pt\box1}\limits^{#1}_{#2}}}%
}

% Boldface gamma

\def\pmb#1{\setbox0=\hbox{#1}%
        \kern-0.05em\copy0\kern-\wd0
        \kern.05em\copy0\kern-\wd0
        \kern-.025em\raise.0433em\box0}
\def\bfgamma{{\mathord{\hbox{\pmb{$\scriptstyle\gamma$}}}}}

% Algorithms

\newcounter{Zeile}
\newbox\kasten
\setbox\kasten=\hbox{00}
\let\graph=\par
{\catcode`\[=\active\catcode`\>=\active
\gdef	\addto#1#2{$#1\leftarrow#1\cup\{#2\}$}
\gdef	\addtrans{{\it add\_trans}}
\gdef	\fordo#1{[for all] $#1$ [do]}
\gdef	\while#1{[while] $#1$ [do]}
\gdef	\ifthen#1{[if] $#1$ [then]}
\gdef	\endif{[f{}i]}
\gdef	\od{[od]}
\gdef\algo{\catcode`\~=\active
	\catcode`\[=\active\catcode`\>=\active\setcounter{Zeile}{0}
	\def\par{\refstepcounter{Zeile}\graph\noindent\kern\wd\kasten%
		\llap{{\small\theZeile}}\quad}
	\def[##1]{{\bf##1}}\def~##1~{\mathchar"405B##1\mathchar"505D}
	\def>{\quad}\obeylines}}

\newcommand{\ol}{\overline}



% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{proposition}{Proposition}[section]
% \newtheorem{corollary}{Corollary}[section]
% \newtheorem{lemma}{Lemma}[section]
 %\newtheorem{remark}{Remark}[section]
 %\newtheorem{notation}{Notation}[section]
%\newtheorem{note}{Note}[section]
 %\newtheorem{convention}{Convention}[section]
% \newtheorem{definition}{Definition}[section]
% \newtheorem{example}{Example}[section]
% %
%\newenvironment{proof}{\noindent {\bf Proof:\,}}{\hfill$\;\;\Box$ \\[1ex]}
%\newenvironment{proofsketch}{\noindent {\bf Proof (Sketch):\,}}{\hfill$\;\;\Box$ \\[1ex]}
\newfam\cyrfam
\font\tencyr=wncyr10    \font\ninecyr=wncyr9
\font\eightcyr=wncyr8   \font\sevencyr=wncyr7
\font\sixcyr=wncyr6     \font\fivecyr=wncyr5

\textfont\cyrfam=\tencyr
\scriptfont\cyrfam=\sevencyr
\scriptscriptfont\cyrfam=\fivecyr
\def\cyr{\fam\cyrfam\tencyr}

\newcommand{\po}{\langle}
\newcommand{\pf}{\rangle}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\shu}{\amalg\hspace{-1.3mm}\amalg}
\newcommand{\open}{\mbox{$[\![$}}
\newcommand{\close}{\mbox{$]\!]$}}
\newcommand{\sh}{\mathrel{\hbox{\ninecyr X}}}
\newcommand{\shuffle}{\mbox{$\sqcup \! \! \, \, \! \sqcup$}}
\newcommand{\mg}{{\mathcal{G}}}
\newcommand{\me}{{\mathcal{E}}}
\newcommand{\ma}{{\mathcal{A}}}
\newcommand{\mP}{{\mathcal{P}}}
\newcommand{\1}{\bar{1}}
\newcommand{\0}{\bar{0}}
\newcommand{\cra}{\longhookrightarrow}
\newcommand{\m} [1]{{\mathcal{#1}}}
\newcommand{\elt} [1]{v_{#1}}

\newcommand{\PDA}{\mbox{${\cal P}$}}
\newcommand{\co}{\langle}
\newcommand{\cf}{\rangle}
%\newcommand{\llt}[1]{\stackrel{#1}{\longrightarrow}}
