\documentclass[koi8-r]{psiras}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage[T2A]{fontenc}
\usepackage{fancyvrb}
\usepackage{color}

% 2004-01-25 00:02
% DONE: ЧЩТБЧОСФШ УФЙМШ ОБРЙУБОЙС ТЕЖБМ ЙМЙ тЕЖБМ

% DONE: ЙУРПМШЪХЕН МЙ НЩ ВХЛЧХ `Ј'?

% DONE: "ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ" ЙМЙ "ОЕ УПДЕТЦЙФ РЕТЕНЕООЩЕ"?

\newcommand{\E}[1]{{\color{green}{#1}}}
\newcommand{\ignore}[1]{{}}
\newcommand{\is}{\mathrel{\ ::=\ }}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\l}{\bigl}
\renewcommand{\r}{\bigr}
\newcommand{\length}[1]{\ensuremath{|{#1}|}}
\newcommand{\subexpr}[3]{\ensuremath{{#1}\langle{#2}, {#3}\rangle}}
\newcommand{\Subexpr}[3]{\ensuremath{{#1}\l\langle{#2}, {#3}\r\rangle}}
\newcommand{\subterm}[2]{\ensuremath{{#1}[{#2}]}}
\newcommand{\Subterm}[2]{\ensuremath{{#1}\l[{#2}\r]}}
\newcommand{\CSC}{\textbf{CSC}}
\newcommand{\EqB}{\textbf{EqB}}
\newcommand{\EqA}{\textbf{EqA}}
\newcommand{\EqG}{\textbf{EqG}}
\newcommand{\EqN}{\textbf{EqS}}
\newcommand{\ChkEq}{\textbf{ChkEq}}
\newcommand{\ChkBnd}{\textbf{ChkBnd}}
\newcommand{\ChkHard}{\textbf{ChkHard}}
\newcommand{\VMinMax}{\textbf{VMinMax}}
\newcommand{\THard}{\textbf{THard}}
\newcommand{\ClA}{\textbf{ClA}}
\newcommand{\Min}{\mathbf{min}}
\newcommand{\Max}{\mathbf{max}}
\newcommand{\Pe}{\mathit{Pe}}
\newcommand{\Pt}{\mathit{Pt}}
\newcommand{\Oe}{\mathit{Oe}}
\newcommand{\Os}{\mathit{Os}}
\newcommand{\He}{\mathit{He}}
\newcommand{\Eq}{\mathit{Eq}}
\newcommand{\len}{\mathit{len}}
\newcommand{\Seq}{S_\mathit{eq}}
\newcommand{\Scl}{S_\mathit{cl}}
\newcommand{\Req}{R_\mathit{eq}}
\newcommand{\Fail}{L_\mathit{fail}}
\newcommand{\Next}{L_\mathit{next}}
\newcommand{\Old}{T_\mathit{old}}
\newcommand{\Hard}{T_\mathit{hard}}
\newcommand{\Cond}{T_\mathit{cond}}
\newcommand{\Amin}{\mathit{Min}}
\newcommand{\Amax}{\mathit{Max}}

\DefineVerbatimEnvironment{ASAIL}{Verbatim}{
  gobble=2,
	frame=single,
%  numbers=left,
  commandchars=\\\{\},
  codes={\catcode`\^=7\catcode`\_=8\catcode`\$=3}
}

\newlength{\asailbaseline}

\newcommand{\asail}[1]{%
	\Verb[commandchars=\\\{\},codes={\catcode`\^=7\catcode`\_=8}]@\fbox{#1}@%
	\setlength{\asailbaseline}{\baselineskip}%
	\addtolength{\asailbaseline}{1pt}%
	\rule{0pt}{\asailbaseline}%
	\vadjust{\kern 1pt}%
}

%\newcommand{\out}{\(\to\)}
\newcommand{\IF}{{\bf if}}
\newcommand{\THEN}{{\bf then}}
\newcommand{\OR}{{\bf or}}
\newcommand{\GOTO}{{\bf goto}}
%\newcommand{\BREAK}{{\bf break}}
%\newcommand{\CONT}{{\bf continue}}
%\newcommand{\FAIL}{\(current\_label\_if\_fail\)}
\newcommand{\SYMB}{{\bf is\_symbol}}
\newcommand{\PARENTH}{{\bf is\_parenth}}
%\newcommand{\DEREF}{{\bf dereference}}
\newcommand{\FUNCTION}{{\bf function}}
\newcommand{\INT}{{\bf int}}
\newcommand{\EXPR}{{\bf expr}}
\newcommand{\FOR}{{\bf for}}
\newcommand{\MOD}{{\bf mod}}
\newcommand{\DIV}{\ensuremath{/}}
%\newcommand{\DIV}{{\bf div}}
\newcommand{\RETURN}{{\bf return}}
%\newcommand{\WHILE}{{\bf while}}
%\newcommand{\DO}{{\bf do}}
%\newcommand{\DONE}{{\bf done}}

\newcounter{algoi}
\newenvironment{algo}{
	\begin{list}{\textbf{ыБЗ \arabic{algoi}.}}{
		\usecounter{algoi}
	}
}
{
	\end{list}
}

%\newtheorem{cons}{\textnormal{уМЕДУФЧЙЕ}}
%\newtheorem{pr}{уЧПКУФЧП}[subsection]
\newtheorem{prop}{хФЧЕТЦДЕОЙЕ}[section]
\newtheorem{cons}[prop]{уМЕДУФЧЙЕ}
\newtheorem{thm}[prop]{фЕПТЕНБ}
\newtheorem{lem}[prop]{мЕННБ}

\subjclass[UDK]{519.68}

\selectlanguage{english}

\title[Compilation of Refal pattern matching]{%
Compilation of Refal pattern matching to imperative languages}

\author[S.~M.~Abramov]{Abramov, Sergei M.}
\address{Program Systems Institute, Russian Academy of~Sciences}
% \curraddr{}
\email{abram@botik.ru}
\thanks{}

\author[A.~Yu.~Orlov]{Orlov, Anton Yu.}
\address{Program Systems Institute, Russian Academy of~Sciences}
\email{orlov@mccme.ru}
\thanks{}


\begin{document}
\begin{abstract}
Pattern matching is one of the main operation in Refal language.
%
This paper describes new approach in compilation of
refal pattern matching into an imperative language.
%
The app\-ro\-ach allows to essentially reduce 
search space of variants during pattern 
matching by cutting a lot of variants for
which positive result of pattern matching is impossible.
%
Optimizations described in this paper are clear enough but
produce essential win in effici\-ency. 
%
However they were not used in Refal implementations up to now.
\par
The authors are supposed that the reader is familiar to 
Refal.  Only basic concepts of Refal common for all 
Refal dialects~\cites{bib:Refal-5, bib:Refal+, bib:Refal-2, 
bib:K03, bib:KK03} are discussed in the paper.
\end{abstract}

\selectlanguage{russian}

\title[лПНРЙМСГЙС УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС]{%
лПНРЙМСГЙС Ч~ЙНРЕТБФЙЧОЩЕ СЪЩЛЙ\\ УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС СЪЩЛБ тЕЖБМ
}

\author[у.~н.~бВТБНПЧ]{бВТБНПЧ, уЕТЗЕК нЙИБКМПЧЙЮ}
\address{йОУФЙФХФ РТПЗТБННОЩИ УЙУФЕН тПУУЙКУЛПК БЛБДЕНЙЙ ОБХЛ}
\email{abram@bbotik.ru}
\thanks{тБВПФБ ЧЩРПМОЕОБ РТЙ РПДДЕТЦЛЕ уХРЕТЛПНРШАФЕТОПК РТПЗТБННЩ
<<улйж>> уПАЪОПЗП ЗПУХДБТУФЧБ Й РТЙ РПДДЕТЦЛЕ тжжй, РТПЕЛФ \No~02-07-90126}

\author[б.~а.~пТМПЧ]{пТМПЧ, бОФПО аТШЕЧЙЮ}
\address{йУУМЕДПЧБФЕМШУЛЙК ГЕОФТ НХМШФЙРТПГЕУУПТОЩИ УЙУФЕН йру тбо}
\email{orlov@mccme.ru}
\thanks{}

\keywords{тЕЖБМ, тЕЖБМ рМАУ, УЙОФБЛУЙЮЕУЛПЕ ПФПЦДЕУФЧМЕОЙЕ,
УПРПУФБЧМЕОЙЕ У ПВТБЪГПН, ЛПНРЙМСГЙС Ч ЙНРЕТБФЙЧОЩК СЪЩЛ}

\begin{abstract}

уЙОФБЛУЙЮЕУЛПЕ ПФПЦДЕУФЧМЕОЙЕ (ЙМЙ УПРПУФБЧМЕОЙЕ У ПВТБЪГПН) СЧМСЕФУС
ПДОЙН ЙЪ ПУОПЧОЩИ ЙЪПВТБЪЙФЕМШОЩИ УТЕДУФЧ СЪЩЛБ тЕЖБМ.  
%
дБООБС ТБВПФБ РПУЧСЭЕОБ ОПЧПНХ РПДИПДХ Л ЛПНРЙМСГЙЙ УЙОФБЛУЙЮЕУЛПЗП 
ПФПЦДЕУФЧМЕОЙС Ч ЙНРЕТБФЙЧОЩЕ СЪЩЛЙ.
%
рПДИПД РПЪЧПМСЕФ ЧП ЧТЕНС РПДВПТБ ЪОБЮЕОЙК ТЕЖБМ-РЕТЕНЕООЩИ 
ЬЖЖЕЛФЙЧОП (ГЕМЩНЙ ПВМБУФСНЙ) ПФУЕЮШ  ЧБТЙБОФЩ, ОБ ЛПФПТЩИ ЪБЧЕДПНП 
ОЕ НПЦЕФ ВЩФШ РПМПЦЙФЕМШОПЗП ТЕЪХМШФБФБ ПФПЦДЕУФЧМЕОЙС.
%
пРЙУЩЧБЕНЩЕ Ч ДБООПК ТБВПФЕ ПРФЙНЙЪБГЙЙ ДПУФБФПЮОП ПЮЕЧЙДОЩ Й, РТЙ 
ЬФПН, ПОЙ ДБАФ УХЭЕУФЧЕООЩК ЧЩЙЗТЩЫ Ч ЬЖЖЕЛФЙЧОПУФЙ.  пДОБЛП ДП УЙИ 
РПТ ПОЙ ОЕ ЙУРПМШЪПЧБМЙУШ Ч ТЕБМЙЪБГЙСИ СЪЩЛБ тЕЖБМ.

пФ ЮЙФБФЕМС ПЦЙДБЕФУС ЪОБЛПНУФЧП У СЪЩЛПН тЕЖБМ,
Ч ТБВПФЕ ПВУХЦДБАФУС УБНЩЕ ВБЪПЧЩЕ РПОСФЙС СЪЩЛБ, ПВЭЙЕ ДМС ЧУЕИ 
ДЙБМЕЛФПЧ тЕЖБМБ~\cites{bib:Refal-5, bib:Refal+, bib:Refal-2, bib:K03, bib:KK03}.

\end{abstract}

\maketitle

\section{чЧЕДЕОЙЕ}
\label{s:intro}

сЪЩЛ РТПЗТБННЙТПЧБОЙС тЕЖБМ ТБЪТБВПФБО ч.~ж.~фХТЮЙОЩН Ч ЫЕУФЙДЕУСФЩЕ
ЗПДЩ РТПЫМПЗП УФПМЕФЙС ЛБЛ ЖХОЛГЙПОБМШОЩК СЪЩЛ, ПТЙЕОФЙТПЧБООЩК ОБ 
ЪБДБЮЙ, УЧСЪБООЩЕ У РТЕПВТБЪПЧБОЙЕН УЙНЧПМШОПК ЙОЖПТНБГЙЙ (symbol 
manipulation).  пДОЙН ЙЪ ВБЪПЧЩИ РПОСФЙК СЪЩЛБ тЕЖБМ СЧМСЕФУС 
УЙОФБЛУЙЮЕУЛПЕ ПФПЦДЕУФЧМЕОЙЕ, УПРПУФБЧМЕОЙЕ У ПВТБЪГПН.  ч ДБООПК ТБВПФЕ
ЙЪМБЗБЕФУС ОПЧЩК РПДИПД Л ЛПНРЙМСГЙЙ УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС Ч
ЙНРЕТБФЙЧОЩЕ СЪЩЛЙ, ПУОПЧБООЩК ОБ ХЮЕФЕ УППФОПЫЕОЙК НЕЦДХ ДМЙОБНЙ
ЧЩТБЦЕОЙК Й РЕТЕНЕООЩИ, ХЮБУФЧХАЭЙИ Ч УЙОФБЛУЙЮЕУЛПН ПФПЦДЕУФЧМЕОЙЙ.

оПЧЩК РПДИПД Л ЬЖЖЕЛФЙЧОПК ТЕБМЙЪБГЙЙ УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС ВХДЕФ
РТПЙММАУФТЙТПЧБО ОБ РТЙНЕТБИ (ТБЪДЕМ~\ref{sec:IntroExamples}), ЪБФЕН ПВУХЦДЕО
ВПМЕЕ ДЕФБМШОП.

ч УФБФШЕ ВХДЕФ РТЕДРПМБЗБФШУС, ЮФП ЮЙФБФЕМШ ЪОБЛПН У СЪЩЛПН РТПЗТБННЙТПЧБОЙС
тЕЖБМ.  рТЙ ЬФПН ПВУХЦДБФШУС ВХДХФ УБНЩЕ ВБЪПЧЩЕ РПОСФЙС, ПВЭЙЕ ДМС ЧУЕИ
ДЙБМЕЛФПЧ~\cites{bib:Refal-5, bib:Refal+, bib:Refal-2, bib:K03, bib:KK03} тЕЖБМБ.

ч УФБФШЕ РТЕДРПМБЗБЕФУС, ЮФП Ч ТЕБМЙЪБГЙЙ тЕЖБМБ ЙУРПМШЪХЕФУС ФБЛПЕ РТЕДУФБЧМЕОЙЕ ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК, ЮФП ПРЕТБГЙЙ ЧЩЮЙУМЕОЙС ДМЙОЩ (\length{e_x}) ЧЩТБЦЕОЙС Й ЛПОУФТХЙТПЧБОЙС РПДЧЩТБЦЕОЙС (\(\subexpr{e_x}{i}{L}\))\footnote{
		ч ЛПОУФТХЛГЙЙ \(e_y = \subexpr{e_x}{i}{L}\) ЖТБЗНЕОФЩ $i$ Й $L$ НПЗХФ ВЩФШ ЧЩТБЦЕОЙСНЙ, ЧЩТБВБФЩЧБАЭЙНЙ ОЕПФТЙГБФЕМШОЩЕ ГЕМЩЕ ЪОБЮЕОЙС \--- ОПНЕТ ФЕТНБ Ч $e_x$, У ЛПФПТПЗП ВХДЕФ ОБЮЙОБФШУС РПДЧЩТБЦЕОЙЕ $e_y$, Й ДМЙОХ РПДЧЩТБЦЕОЙС $e_y$, УППФЧЕФУФЧЕООП.  фЕТНЩ ОХНЕТХАФУС УМЕЧБ ОБРТБЧП ОБЮЙОБС У 0, ОПНЕТ РПУМЕДОЕЗП ФЕТНБ \--- $(\length{e_x}-1)$.
	} ЧЩРПМОСАФУС ЪБ ЛПОУФБОФОПЕ (ОЕ ЪБЧЙУСЭЕЕ ПФ ЧЩТБЦЕОЙС) ЧТЕНС.  ьФП РТЕДРПМПЦЕОЙЕ ЧЩРПМОЕОП ДМС ВПМШЫЙОУФЧБ УПЧТЕНЕООЩИ ТЕБМЙЪБГЙК ДЙБМЕЛФПЧ СЪЩЛБ тЕЖБМ~\cites{bib:vector-exps,bib:Refal+,bib:Web:New-Refal+,bib:KK03}.

\subsection{йММАУФТБГЙС ЙДЕЙ ОБ РТЙНЕТБИ}
\label{sec:IntroExamples}

\subsubsection{рТЙНЕТ ОБ ФЕНХ <<ЛТБФОЩЕ ДМЙОЩ>>.}
\label{sec:IntroExampleDiv}

тБУУНПФТЙН РТПУФХА ЖХОЛГЙА ОБ СЪЩЛЕ тЕЖБМ\footnote{
		рТЙЧЕДЕОБ ЪБРЙУШ ЖХОЛГЙЙ ОБ СЪЩЛЕ тЕЖБМ рМАУ.  бОБМПЗЙЮОЩК
		РТЙНЕТ НПЦЕФ ВЩФШ ЪБРЙУБО ОБ МАВПН ЙОПН ДЙБМЕЛФЕ СЪЩЛБ тЕЖБМ,
		РТЙЮЕН ЪБРЙУШ ВХДЕФ ЧЕУШНБ ВМЙЪЛБ Л РТЙЧЕДЕООПНХ ФЕЛУФХ.
}:
\begin{quote}
\begin{ASAIL}[frame=single]
  IsTriplet \(e_x\) = \{
     \rlap{\(e_x : e_1\,e_1\,e_1\)}\hphantom{/* otherwise */} = True;
     /* otherwise */ = False;
  \};
\end{ASAIL}
\end{quote}
%
чП ЧФПТПК УФТПЛЕ ДБООПЗП ПРЙУБОЙС УФПЙФ \emph{РЕТЕУФТПКЛБ} $e_x : e_1\,e_1\,e_1,$
ЧЩРПМОСАЭБС УМЕДХАЭХА РТПЧЕТЛХ: <<ЧЕТОП МЙ, ЮФП БТЗХНЕОФ ЖХОЛГЙЙ $e_x$
НПЦЕФ ВЩФШ РТЕДУФБЧМЕО ЛБЛ ЛПОЛБФЕОБГЙС ФТЕИ ЛПРЙК
ПДОПЗП Й ФПЗП ЦЕ ЧЩТБЦЕОЙС $e_1$?>>.  еУМЙ ЬФП ЧЕТОП, ФП Ч ЛБЮЕУФЧЕ
ТЕЪХМШФБФБ ЧЩЮЙУМЕОЙС ЖХОЛГЙЙ ЧПЪЧТБЭБЕФУС \Verb"True", ЕУМЙ ОЕ ЧЕТОП \--- ФП
\Verb"False".  ч УППФЧЕФУФЧЙЙ У ДБООЩН ПРЙУБОЙЕН:
\begin{enumerate}
%DONE AO- рП-НПЕНХ, РТБЧЙМШОП ЗПЧПТЙФШ: "УФТПЛХ ДМЙОЩ ...".
%DONE SA- лПТТЕЛФПТ ЧЕМЕМ ЗПЧПТЙФШ: "УФТПЛХ ДМЙОПК ...".
	\item еУМЙ ЧЩЪЧБФШ ДБООХА ЖХОЛГЙА, РЕТЕДБЧ ЕК Ч ЛБЮЕУФЧЕ БТЗХНЕОФБ
	$e_x = \mbox{\Verb|'ббб|\ldots\Verb|ббб'|}$ УФТПЛХ ДМЙОПК
	$51\,000 = 3 \cdot 17\,000$ УЙНЧПМПЧ, УПДЕТЦБЭХА ФПМШЛП МЙФЕТЩ
	\Verb"'A'", ФП Ч ЛБЮЕУФЧЕ ТЕЪХМШФБФБ ЖХОЛГЙС ЧЕТОЕФ \Verb"True", ФБЛ
	ЛБЛ Ч ДБООПН УМХЮБЕ УФТПЛБ $e_x$ НПЦЕФ ВЩФШ РТЕДУФБЧМЕОБ ЛБЛ
	ЛПОЛБФЕОБГЙС ЙЪ ФТЕИ ЛПРЙК УФТПЛЙ 	$e_1 = \mbox{\Verb|'ббб|\ldots\Verb|ббб'|}$
	ДМЙОПК $17\,000$ УЙНЧПМПЧ, УПДЕТЦБЭЕК ФПМШЛП МЙФЕТЩ \Verb"'A'".

%DONE AO- рП-НПЕНХ, РТБЧЙМШОП ЗПЧПТЙФШ: "УФТПЛХ ДМЙОЩ ...".
%DONE SA- лПТТЕЛФПТ ЧЕМЕМ ЗПЧПТЙФШ: "УФТПЛХ ДМЙОПК ...".
	\item еУМЙ ЧЩЪЧБФШ ДБООХА ЖХОЛГЙА, РЕТЕДБЧ ЕК Ч ЛБЮЕУФЧЕ БТЗХНЕОФБ
	$e_x = \mbox{\Verb|'ббб|\ldots\Verb|ббб'|}$ УФТПЛХ ДМЙОПК
	${50\,999 = 3 \cdot 17\,000 - 1}$ УЙНЧПМПЧ, УПДЕТЦБЭХА ФПМШЛП МЙФЕТЩ
	\Verb"'A'", ФП Ч ЛБЮЕУФЧЕ ТЕЪХМШФБФБ ЖХОЛГЙС ЧЕТОЕФ \Verb"False", ФБЛ
	ЛБЛ Ч ДБООПН УМХЮБЕ ОЙ ДМС ЛБЛЙИ ЪОБЮЕОЙК $e_1$ УФТПЛБ $e_x$ ОЕ
	НПЦЕФ ВЩФШ РТЕДУФБЧМЕОБ ЛБЛ ЛПОЛБФЕОБГЙС ЙЪ ФТЕИ ЛПРЙК $e_1$.
\end{enumerate}
чП ЧУЕИ УХЭЕУФЧПЧБЧЫЙИ ТБОЕЕ
ТЕБМЙЪБГЙСИ ДЙБМЕЛФПЧ тЕЖБМБ ЧЩЮЙУМЕОЙЕ ФБЛПК ОЕУМПЦОПК
ЖХОЛГЙЙ (ЧУЕЗП ПДЙО ЫБЗ <<РТПЧЕТЛБ\--ЪБНЕОБ>>) ДБЦЕ ОБ УПЧТЕНЕООЩИ рьчн
ЪБОЙНБЕФ ДПУФБФПЮОП ДМЙФЕМШОПЕ ЧТЕНС (УН. фБВМЙГХ~\ref{tab:IsTripletTime}).
рТЙЮЙОПК ЬФПЗП СЧМСЕФУС ОЕЬЖЖЕЛФЙЧОБС УИЕНБ (УН. тЙУ.~\ref{pic:isTripletOld})
ТЕБМЙЪБГЙЙ РЕТЕУФТПКЛЙ $e_x : e_1\,e_1\,e_1$ Ч ЖХОЛГЙЙ \Verb"IsTriplet": РТЙ
ФБЛПК УИЕНЕ ТЕБМЙЪБГЙЙ УМПЦОПУФШ ЧЩЮЙУМЕОЙС ЖХОЛГЙЙ УПУФБЧМСЕФ $O({A_x}^2)$, ЗДЕ
${A_x = \length{e_x}}$ \--- ДМЙОБ ЧИПДОЩИ ДБООЩИ.

%
\begin{table}
	\begin{center}
		\begin{tabular}{|l|c|c|c|c|c|c|}\hline
    & Refal & Refal  & Refal    & Refal     & Refal & Refal \\
    &   6   & 6/Java & Plus (32) & Plus (16) & 5 (A) &  5 (B) \\\hline
$t_{True}$ & 2.8 & 5.0 & 17.8 & 59.4 & 72.7 & 74.7 \\\hline
$t_{False}$ & 8.7 & 11.2 & 33.8 & 133.1 & 228.9 & 230.7 \\\hline
$\frac{t_{False}}{t_{True}}$ & 3.1 & 2.2 & 1.9 & 2.2 & 3.1 & 3.1 \\\hline
\multicolumn{7}{|l|}{$t_{True}$ \--- ЧТЕНС (УЕЛ.) ЧЩРПМОЕОЙС ЧЩЮЙУМЕОЙС:}\\
\multicolumn{7}{|c|}{
		{\Verb|IsTriplet|
		'\(\underbrace{\mbox{\normalfont{\Verb|AAA|}\ldots{\Verb|AAA|}}}_{51\,000}\)'
		= True}
}\\
\multicolumn{7}{|l|}{$t_{False}$ \--- ЧТЕНС (УЕЛ.) ЧЩРПМОЕОЙС ЧЩЮЙУМЕОЙС:}\\
\multicolumn{7}{|c|}{
		{\Verb|IsTriplet|
		'\(\underbrace{\mbox{\normalfont{\Verb|AAA|}\ldots{\Verb|AAA|}}}_{50\,999}\)'
		= False}
}\\
\multicolumn{7}{|l|}{чЩЮЙУМЕОЙС ЧЩРПМОСМЙУШ ОБ рьчн У РТПГЕУУПТПН}\\
\multicolumn{7}{|l|}{Intel Pentium IV 2GHz.}\\\hline
		\end{tabular}
	\end{center}
	\caption{рТЕДЩДХЭЙЕ ТЕБМЙЪБГЙЙ СЪЩЛБ ТЕЖБМ: ЧТЕНС ЧЩЮЙУМЕОЙС ЖХОЛГЙЙ \ttfamily{IsTriplet}
		}
	\label{tab:IsTripletTime}
\end{table}
%
\begin{figure}
%\begin{quote}
\begin{ASAIL}[frame=single]
  \FUNCTION IsTriplet(\EXPR \(e_x\)) \{
    \EXPR \(e_1\)
    \INT \(X_1\)
    /* \textnormal{ГЙЛМ ХДМЙОЕОЙС \(e_1\), РЕТЕВПТ ЧБТЙБОФПЧ} */
    \FOR ($X_1 = 0$; $X_1 \leq \length{e_x}$; $X_1\mathclose{++}$) \{
      /* \textnormal{Ч ЛБЮЕУФЧЕ \(e_1\) ВЕТЕН РТЕЖЙЛУ ДМЙОЩ \(X_1\) ПФ \(e_x\)} */
      \(e_1\) = \subexpr{e_x}{0}{X_1}
      /* \textnormal{Ч \(e_x\) ЪБ 1-ПК ЛПРЙЕК \(e_1\) УМЕДХЕФ ЕЭЕ ЛПРЙС \(e_1\)?} */
      \IF \(e_1 \neq \subexpr{e_x}{X_1}{X_1}\) \THEN \GOTO next
      /* \textnormal{Ч \(e_x\) ЪБ 2-ПК ЛПРЙЕК \(e_1\) УМЕДХЕФ ЕЭЕ ЛПРЙС \(e_1\)?} */
      \IF \(e_1 \neq \subexpr{e_x}{2 \cdot X_1}{X_1}\) \THEN \GOTO next
      /* \textnormal{Ч \(e_x\) ЪБ 3-ЕК ЛПРЙЕК \(e_1\) ВПМШЫЕ ОЙЮЕЗП ОЕФ?} */
      \IF \(\length{e_x} \neq 3 \cdot X_1\) \THEN \GOTO next
      \RETURN True
    next:
    \}
    \RETURN False
  \}
\end{ASAIL}
%\end{quote}
	\caption{оЕЬЖЖЕЛФЙЧОБС УИЕНБ ТЕБМЙЪБГЙЙ ЖХОЛГЙЙ \ttfamily{IsTriplet}}
	\label{pic:isTripletOld}
\end{figure}
%
\begin{figure}
%\begin{quote}
\begin{ASAIL}[frame=single]
  \FUNCTION IsTriplet(\EXPR $e_x$) \{
    \EXPR $e_1$
    \INT $A_x$, $X_1$
    $A_x = \length{e_x}$
    \IF $A_x$ \MOD $3$ $\neq$ $0$ \THEN \GOTO branch2
    $X_1 = A_x\,\DIV\,3$
    $e_1 = \subexpr{e_x}{0}{X_1}$
    /* \textnormal{Ч $e_x$ ЪБ 1-ПК ЛПРЙЕК $e_1$ УМЕДХЕФ ЕЭЕ ЛПРЙС $e_1$?} */
    \IF $e_1 \neq \subexpr{e_x}{X_1}{X_1}$ \THEN \GOTO branch2
    /* \textnormal{Ч $e_x$ ЪБ 2-ПК ЛПРЙЕК $e_1$ УМЕДХЕФ ЕЭЕ ЛПРЙС $e_1$?} */
    \IF $e_1 \neq \subexpr{e_x}{2 \cdot X_1}{X_1}$ \THEN \GOTO branch2
    \RETURN True
  branch2:
    \RETURN False
  \}
\end{ASAIL}
%\end{quote}
	\caption{оПЧБС УИЕНБ ЧЩЮЙУМЕОЙС ЖХОЛГЙЙ \ttfamily{IsTriplet}}
	\label{pic:isTripletNew}
\end{figure}

уХФШ ТЕБМЙЪБГЙЙ ДБООПК РЕТЕУФТПКЛЙ Ч УМЕДХАЭЕН: \emph{Ч ЛБЮЕУФЧЕ ЧПЪНПЦОЩИ
ЧБТЙБОФПЧ ДМС ЪОБЮЕОЙС РЕТЕНЕООПК} $e_1$ ТБУУНБФТЙЧБАФУС \emph{ЧУЕ ЧПЪНПЦОЩЕ
РТЕЖЙЛУЩ} ДМЙОЩ $X_1$, РТЕЖЙЛУЩ ТБУУНБФТЙЧБАФУС РППЮЕТЕДОП, Ч УМЕДХАЭЕН
РПТСДЛЕ: $X_1\!= 0,\ldots,A_x$. дМС ЛБЦДПЗП ЪОБЮЕОЙС $e_1$ ДЕМБЕФУС РТПЧЕТЛБ,
ОЕ УПЧРБДБЕФ МЙ $e_x$ У ЛПОЛБФЕОБГЙЕК $e_1\,e_1\,e_1$ ФТЕИ ЛПРЙК $e_1$.

лПТОЙ ОЕЬЖЖЕЛФЙЧОПУФЙ Ч ФПН, ЮФП Ч ЛБЮЕУФЧЕ ЧПЪНПЦОЩИ ЪОБЮЕОЙК ДМС ОЕЙЪЧЕУФОПК
$e_1$ РЕТЕВЙТБАФУС \emph{ЧУЕ} РТЕЖЙЛУЩ $e_x$.  б ЬФПЗП НПЦОП ЙЪВЕЦБФШ.
дЕКУФЧЙФЕМШОП, РТЕДРПМПЦЙН, ОБН ХДБМПУШ РПДПВТБФШ ФБЛПЕ ЪОБЮЕОЙЕ $e_1$
ОЕЛПФПТПК ДМЙООЩ $X_1$, ЮФП $e_x$ УПЧРБДБЕФ У ЛПОЛБФЕОБГЙЕК $e_1\,e_1\,e_1$
ФТЕИ ЛПРЙК $e_1$.  фПЗДБ НЩ НПЦЕН ХФЧЕТЦДБФШ, ЮФП:
\begin{itemize}
	\item ЧЩРПМОЕОП УМЕДХАЭЕЕ УППФОПЫЕОЙЕ НЕЦДХ ДМЙОБНЙ $e_x$ Й
		$e_1$: $A_x = 3 \cdot X_1$, ФП ЕУФШ $A_x$ ДЕМЙФУС ОБ ФТЙ ОБГЕМП;
	\item $e_1$ СЧМСЕФУС РТЕЖЙЛУПН ДМЙОЩ $A_x/3$ ЧЩТБЦЕОЙС $e_x$.
\end{itemize}
фЕН УБНЩН ОБКДЕО ОПЧЩК ЬЖЖЕЛФЙЧОЩК УРПУПВ ЧЩЮЙУМЕОЙС ЖХОЛГЙЙ \Verb|IsTriplet|
(УН. тЙУ.~\ref{pic:isTripletNew}).  уРПУПВ ЙНЕЕФ ЧЩЮЙУМЙФЕМШОХА УМПЦОПУФШ ОЕ
$O({A_x}^2)$, a $O(A_x)$.  ч ОЕН ОЕ ТБУУНБФТЙЧБЕФУС (ПФУЕЛБЕФУС) НОПЦЕУФЧП ЧБТЙБОФПЧ
ЪОБЮЕОЙК ДМС $e_1$, ЛПФПТЩЕ ОЕ ЙНЕАФ ОЙЛБЛЙИ ЫБОУПЧ ВЩФШ ТЕЫЕОЙЕН
РЕТЕУФТПКЛЙ, ЧНЕУФП $A_x$ ЧБТЙБОФПЧ ТБУУНБФТЙЧБЕФУС ТПЧОП ПДЙО ЧБТЙБОФ:
$e_1 = \Subexpr{e_x}{0}{\length{eX}/3}$.  фБЛБС ТЕБМЙЪБГЙС ЖХОЛГЙЙ
\Verb|IsTriplet| ПВЕУРЕЮЙЧБЕФ \emph{ХУЛПТЕОЙЕ РТЙНЕТОП Ч $8\,500$ ТБЪ}\footnote{
	пФОПЫЕОЙЕ ЮЙУМБ УТБЧОЕОЙК УЙНЧПМПЧ: $17\,000 \cdot 17\,001 / (2 \cdot 17\,000) =  8\,500.5$.
} ЧЩЮЙУМЕОЙК, ХРПНСОХФЩИ Ч фБВМЙГЕ~\ref{tab:IsTripletTime}.

\subsubsection{рТЙНЕТ ОБ ФЕНХ <<ХЮЕФ ПЗТБОЙЮЕОЙК ОБ ДМЙОЩ>>}
\label{sec:IntroExampleLim}

тБУУНПФТЙН РТЙНЕТ ТЕЖБМ\-/ЖХОЛГЙЙ \Verb|IsSubexp|:
\begin{quote}
\begin{ASAIL}[frame=single]
  IsSubexp $e_x$ $e_y$ = \{
     \rlap{$e_x : e_1\,e_y\,e_2$}\hphantom{/* otherwise */} = True;
     /* otherwise */ = False;
  \};
\end{ASAIL}
\end{quote}
чП ЧУЕИ УХЭЕУФЧПЧБЧЫЙИ ТБОЕЕ ТЕБМЙЪБГЙСИ ДЙБМЕЛФПЧ тЕЖБМБ ЧЩЮЙУМЕОЙЕ ФБЛПК ЖХОЛГЙЙ
ЧЩРПМОСЕФУС РП УМЕДХАЭЕК УИЕНЕ:
\begin{itemize}
	\item Ч ГЙЛМЕ РППЮЕТЕДОП ТБУУНБФТЙЧБАФУС ЧУЕ РТЕЖЙЛУЩ $e_1$ ЧЩТБЦЕОЙС $e_x$, У ДМЙОБНЙ ПФ $0$ ДП $A_x = \length{e_x}$;
	\item РТПЧЕТСЕФУС, ЧЕТОП МЙ, ЮФП ЪБ РТЕЖЙЛУПН $e_1$ Ч ЧЩТБЦЕОЙЙ $e_x$ ЙНЕЕФУС ЧЩТБЦЕОЙЕ, ТБЧОПЕ $e_y$.  еУМЙ РТПЧЕТЛБ ОЕ ХУРЕЫОБС, ФП Ч ЛБЮЕУФЧЕ $e_1$ ТБУУНБФТЙЧБЕФУС УМЕДХАЭЙК РТЕЖЙЛУ $e_x$ (ХДМЙОЕОЙЕ РЕТЕНЕООПК $e_1$).  еУМЙ РТПЧЕТЛБ ХУРЕЫОБС, ФП ЖХОЛГЙС ЧЩЮЙУМЕОБ, ТЕЪХМШФБФ \Verb|True|;
	\item ЕУМЙ ЧУЕ РТЕЖЙЛУЩ $e_1$ ЧЩТБЦЕОЙС $e_x$ ТБУУНПФТЕОЩ Й ОЕЧПЪНПЦОП ПЮЕТЕДОПЕ ХДМЙОЕОЙЕ РЕТЕНЕООПК $e_1$, ФП ЖХОЛГЙС ЧЩЮЙУМЕОБ, ТЕЪХМШФБФ \Verb|False|.
\end{itemize}

пЮЕЧЙДОП, ЮФП РТЙ ФБЛПК УИЕНЕ ТЕБМЙЪБГЙЙ ЧЩРПМОСАФУС МЙЫОЙЕ ЙФЕТБГЙЙ: СУОП, ЮФП ОБДП ТБУУНБФТЙЧБФШ \emph{ОЕ ЧУЕ} РТЕЖЙЛУЩ $e_1$ ЧЩТБЦЕОЙС $e_x$, У ДМЙОБНЙ ПФ $0$ ДП $A_x = \length{e_x}$, Б ФПМШЛП РТЕЖЙЛУЩ У ДМЙОБНЙ ПФ $0$ ДП $(A_x - A_y)$, ЗДЕ $A_y = \length{e_y}$.

\begin{figure}
%\begin{quote}
\begin{ASAIL}[frame=single]
  \FUNCTION IsSubexp(\EXPR $e_x$, \EXPR $e_y$) \{
    \INT $A_x = \length{e_x}$
    \INT $A_y = \length{e_y}$
    \EXPR $e_1$, $e_2$
    \INT $X_1$
    /* \textnormal{ГЙЛМ ХДМЙОЕОЙС $e_1$, РЕТЕВПТ ЧБТЙБОФПЧ} */
    \FOR ($X_1 = 0$; $X_1 \leq (A_x - A_y)$; $X_1\mathclose{++}$) \{
      /* \textnormal{Ч ЛБЮЕУФЧЕ $e_1$ ВЕТЕН РТЕЖЙЛУ ДМЙОПК $X_1$ ПФ $e_x$} */
      $e_1 = \subexpr{e_x}{0}{X_1}$
      /* \textnormal{Ч $e_x$ ЪБ $e_1$ УМЕДХЕФ $e_y$?} */
      \IF $e_y \neq \subexpr{e_x}{X_1}{A_y}$ \THEN \GOTO next
      /* \textnormal{ЪБЛТЩФБС РЕТЕНЕООБС $e_2$} */
      $e_2 = \subexpr{e_x}{X_1 + A_y}{A_x - A_y - X_1}$
      \RETURN True
    next:
    \}
    \RETURN False
  \}
\end{ASAIL}
%\end{quote}
	\caption{ьЖЖЕЛФЙЧОБС УИЕНБ ТЕБМЙЪБГЙЙ ЖХОЛГЙЙ \ttfamily{IsSubexp}}
	\label{pic:IsSubexp}
\end{figure}

жПТНБМШОП ЬФП МЕЗЛП РПМХЮЙФШ ЙЪ УМЕДХАЭЕЗП БОБМЙЪБ: РЕТЕУФТПКЛЕ $e_x : e_1\,e_y\,e_2$ НПЦОП РПУФБЧЙФШ Ч УППФЧЕФУФЧЙЕ ХТБЧОЕОЙЕ \[ A_x = X_1 + A_y + X_2 \]
\begin{itemize}
	\item \emph{У РБТБНЕФТБНЙ} $A_x$ Й $A_y$, ПВПЪОБЮБАЭЙНЙ ДМЙОЩ РЕТЕНЕООЩИ $e_x$ Й $e_y$, ЬФЙ ДМЙОЩ ВХДХФ ЙЪЧЕУФОЩ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ Ч НПНЕОФ ОБЮБМБ ЧЩЮЙУМЕОЙС РЕТЕУФТПКЛЙ $e_x : e_1\,e_y\,e_2$;

	\item \emph{У ОЕЙЪЧЕУФОЩНЙ} $X_1$ Й $X_2$, ПВПЪОБЮБАЭЙНЙ ДМЙОЩ РЕТЕНЕООЩИ $e_1$ Й $e_2$, ЬФЙ ДМЙОЩ ВХДХФ ОЕЙЪЧЕУФОЩ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ Ч НПНЕОФ ОБЮБМБ ЧЩЮЙУМЕОЙС РЕТЕУФТПКЛЙ $e_x : e_1\,e_y\,e_2$.

\end{itemize}
ьФП ХТБЧОЕОЙЕ Ч ОЕПФТЙГБФЕМШОЩИ ЮЙУМБИ ЙНЕЕФ ПЮЕЧЙДОПЕ ТЕЫЕОЙЕ:
\[
	\left\{
	\begin{array}{l}
	X_1 \in \mathbb{Z}[0..A_x - A_y] \\
	X_2 = A_x - A_y - X_1
	\end{array}
	\right.
\]
ЮФП РПЪЧПМСЕФ ЧЩРЙУБФШ ВПМЕЕ ЬЖЖЕЛФЙЧОХА (ЮЕН ПРЙУБООХА ЧЩЫЕ) УИЕНХ ТЕБМЙЪБГЙЙ ЖХОЛГЙЙ \Verb|IsSubexp| (УН. тЙУ.~\ref{pic:IsSubexp}).

\subsubsection{рТЙНЕТ ОБ ФЕНХ <<ГЕРПЮЛБ РЕТЕУФТПЕЛ>>}
\label{sec:IntroExampleSystem}

оБ РТЙНЕТЕ УМЕДХАЭЕК ЖХОЛГЙЙ:
\begin{quote}
\begin{ASAIL}[frame=single]
  AreSymmetric $e_x$ $e_y$ = \{
     $e_x : e_1\,e_2,\,\,e_y : e_3\,e_4,\,\,e_1\,e_4 : e_3\,e_2$ = True;
     \rlap{/* otherwise */}\hphantom{$e_x : e_1\,e_2,\,\,e_y : e_3\,e_4,\,\,e_1\,e_4 : e_3\,e_2$} = False;
  \};
\end{ASAIL}
\end{quote}
РПЛБЦЕН, ЛБЛ ТБУУНПФТЕОЙЕ ОЕ ПДЙОПЮОПК РЕТЕУФТПКЛЙ, Б \emph{ГЕРПЮЛЙ РЕТЕУФТПЕЛ\footnote{
	оЕУМПЦОП РПЛБЪБФШ, ЮФП ГЕРПЮЛБ РЕТЕУФТПЕЛ ЙЪ ЖХОЛГЙЙ \Verb|AreSymmetric| ЙНЕЕФ ТЕЫЕОЙЕ ФПМШЛП Ч УМЕДХАЭЙИ УМХЮБСИ:
\begin{itemize}
	\item ЕУМЙ $e_x : e_3\,e_0\,e_0\,e_4$ Й $e_y : e_3\,e_4$ (ФПЗДБ $e_1 = e_3\,e_0$, $e_2 = e_0\,e_4$);
	\item ЕУМЙ $e_x : e_1\,e_2$ Й $e_y : e_1\,e_0\,e_0\,e_2$ (ФПЗДБ $e_3 = e_1\,e_0$, $e_4 = e_0\,e_2$).
\end{itemize}%
}}, Й БЛЛХТБФОБС ТБВПФБ У ХТБЧОЕОЙСНЙ Й ОЕТБЧЕОУФЧБНЙ ОБД ДМЙОБНЙ РЕТЕНЕООЩИ РПЪЧПМСЕФ УФТПЙФШ ЬЖЖЕЛФЙЧОЩК ЙНРЕТБФЙЧОЩК ЛПД.

дМЙОЩ ЪОБЮЕОЙК РЕТЕНЕООЩИ $e_x$, $e_y$, $e_1$, $e_2$,
$e_3$, $e_4$ ПВПЪОБЮЙН ФБЛ: РБТБНЕФТЩ $A_x$, $A_y$; ОЕЙЪЧЕУФОЩЕ $X_1$, $X_2$,
$X_3$, $X_4$.  рП ГЕРПЮЛЕ РЕТЕУФТПЕЛ ($e_x : e_1\,e_2,\,\,e_y : e_3\,e_4,\,\,e_1\,e_4 : e_3\,e_2$)
ПЮЕЧЙДОЩН ПВТБЪПН ЧЩРЙУЩЧБЕФУС УЙУФЕНБ ЙЪ ФТЕИ ХТБЧОЕОЙК:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
A_x & = & X_1 + X_2 \\
A_y & = & X_3 + X_4 \\
X_1 + X_4 & = & X_3 + X_2
	\end{array}
	\right.
	\label{eq:sysI}
\end{equation}
рЕТЕОПУЙН ЧУЕ ЮМЕОЩ Ч МЕЧХА ЮБУФШ:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
A_x - X_1 - X_2 & = & 0 \\
A_y - X_3 - X_4 & = & 0 \\
X_1 + X_4 - X_3 - X_2& = & 0
	\end{array}
	\right.
	\label{eq:sysII}
\end{equation}
йЪ РЕТЧПЗП ХТБЧОЕОЙС ЧЩТБЦБЕН РЕТЧХА РЕТЕНЕООХА ($X_1$) Й РПДУФБЧМСЕН ЧП ЧУЕ ПУФБМШОЩЕ ХТБЧОЕОЙС:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
X_1 & = & A_x - X_2 \\
A_y - X_3 - X_4 & = & 0 \\
A_x + X_4 - X_3 - 2 \cdot X_2& = & 0
	\end{array}
	\right.
	\label{eq:sysIII}
\end{equation}
фЕРЕТШ НЩ ВЕТЕН ЙЪ ЧЩТБЦЕОЙС ДМС $X_1$ РЕТЧХА РП РПТСДЛХ РЕТЕНЕООХА ($X_2$), ОБИПДЙН ХТБЧОЕОЙЕ, РПЪЧПМСАЭЕЕ ЕЕ ЧЩТБЪЙФШ (ФТЕФШЕ ХТБЧОЕОЙЕ), ЧЩТБЦБЕН ЬФХ РЕТЕНЕООХА ($2 \cdot X_2 =  A_x + X_4 - X_3$) Й РПДУФБЧМСЕН ЧП ЧУЕ ПУФБМШОЩЕ ХТБЧОЕОЙС, ЗДЕ ПОБ УПДЕТЦЙФУС (РТЕДЧБТЙФЕМШОП ХНОПЦЙЧ ЙИ ОБ ДЧБ):
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
2 \cdot X_1 & = & A_x - X_4 + X_3 \\
2 \cdot X_2& = & A_x + X_4 - X_3 \\
A_y - X_3 - X_4 & = & 0
	\end{array}
	\right.
	\label{eq:sysIV}
\end{equation}
фЕРЕТШ НЩ ВЕТЕН ЙЪ ЧЩТБЦЕОЙС ДМС $X_2$ РЕТЧХА РП РПТСДЛХ РЕТЕНЕООХА ($X_4$), ЧЩТБЦБЕН ЕЕ ЙЪ РПУМЕДОЕЗП\footnote{рЕТЧЩЕ ДЧБ ХТБЧОЕОЙС НЩ ХЦЕ ЙУРПМШЪПЧБМЙ.} ХТБЧОЕОЙС ($X_4 = A_y - X_3$) Й РПДУФБЧМСЕН ЧП ЧУЕ ПУФБМШОЩЕ ХТБЧОЕОЙС, ЗДЕ ПОБ УПДЕТЦЙФУС:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
2 \cdot X_1 & = & A_x - A_y + 2 \cdot X_3 \\
2 \cdot X_2& = & A_x  + A_y - 2 \cdot X_3 \\
X_4 & = & A_y - X_3
	\end{array}
	\right.
	\label{eq:sysV}
\end{equation}
нЩ ЧЩТБЪЙМЙ РЕТЕНЕООЩЕ $X_1$, $X_2$ Й $X_4$ ЮЕТЕЪ РБТБНЕФТЩ Й УЧПВПДОХА РЕТЕНЕООХА $X_3$.  фБЛ ЛБЛ ЧУЕ $X_i$ ОЕ НПЗХФ ВЩФШ ПФТЙГБФЕМШОЩНЙ, ФП ЙЪ УЙУФЕНЩ (\ref{eq:sysV}) РПМХЮБЕН УМЕДХАЭЙЕ ПЗТБОЙЮЕОЙС ОБ ЪОБЮЕОЙС УЧПВПДОПК РЕТЕНЕООПК $X_3$:
\begin{equation}
  \max{\left(\left\lceil(A_y-A_x)/2\right\rceil, 0\right)} \leq X_3 \leq \min{\left(A_y, \left\lfloor(A_y+A_x)/2\right\rfloor\right)}
	\label{eq:limI}
\end{equation}
йЪ ПЗТБОЙЮЕОЙС ОБ ЪОБЮЕОЙС $X_3$ Й ЙЪ РЕТЧПЗП ХТБЧОЕОЙС УЙУФЕНЩ (\ref{eq:sysV}) РПМХЮБЕН ХФПЮОЕООЩЕ ЗТБОЙГЩ ДМС РЕТЕНЕООПК $X_1$:
\begin{equation}
  \max{\left(\left\lceil {(A_x - A_y)/2}\right\rceil, 0\right)} \leq X_1 \leq \min{\left(A_x, \left\lfloor{(A_x + A_y)/2}\right\rfloor\right)} 
	\label{eq:limII}
\end{equation}
йФБЛ, НЩ РПМХЮЙМЙ ХФПЮОЕООЩЕ ЗТБОЙГЩ ДМС ГЙЛМБ РП РБТБНЕФТХ $X_1$, ЛПФПТЩК СЧМСЕФУС ДМЙОПК РЕТЕНЕООПК $e_1$.  чОХФТЙ ДБООПЗП ГЙЛМБ РЕТЕНЕООБС $X_1$ ВХДЕФ ЙЪЧЕУФОПК, ПЪОБЮЕООПК РЕТЕНЕООПК, ФП ЕУФШ РБТБНЕФТПН \--- РЕТЕПВПЪОБЮЙН ЕЗП $A_1 = X_1$.  й ДМС ФЕМБ ГЙЛМБ УЙУФЕНБ~(\ref{eq:sysII}) РТЙНЕФ УМЕДХАЭЙК ЧЙД:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
A_x - A_1 - X_2 & = & 0 \\
A_y - X_3 - X_4 & = & 0 \\
A_1 + X_4 - X_3 - X_2& = & 0
	\end{array}
	\right.
	\label{eq:sysVI}
\end{equation}
ч УЙУФЕНЕ~(\ref{eq:sysVI}) НЩ ТБЪТЕЫБЕН ПДОХ РЕТЕНЕООХА ЪБ ДТХЗПК:
\begin{equation}
	\left\{
	\begin{array}{r@{\,}c@{\,}l}
X_2 & = & A_x - A_1 \\
X_3 & = & A_y - X_4 \\
2 \cdot X_4 & = & A_y + A_x - 2 \cdot A_1
	\end{array}
	\right.
	\label{eq:sysVII}
\end{equation}
рПУМЕ ЬФПЗП МЕЗЛП РПУФТПЙФШ УИЕНХ ЧЩЮЙУМЕОЙС (УН. тЙУ.~\ref{pic:AreSymmetric}) ЖХОЛГЙЙ \Verb|AreSymmetric|.  пФНЕФЙН, ЮФП ЪБ УЮЕФ ТЕЫЕОЙС УЙУФЕНЩ ХТБЧОЕОЙК ОБ ДМЙОЩ РЕТЕНЕООЩИ, РПМХЮЕООЩК БМЗПТЙФН ЙНЕЕФ ОЕ ДЧБ ЧМПЦЕООЩИ ГЙЛМБ, Б ПДЙО ГЙЛМ, Й ТБВПФБЕФ ПО Ч УТЕДОЕН Ч $\length{e_y}$ ТБЪ ВЩУФТЕЕ, ЮЕН ЬФП ЕУФШ ДМС ЛМБУУЙЮЕУЛЙИ УРПУПВПЧ ЛПНРЙМСГЙЙ ДБООПК ЖХОЛГЙЙ.

\begin{figure}
%\begin{quote}
\begin{ASAIL}[frame=single]
  \FUNCTION AreSymmetric(\EXPR $e_x$, \EXPR $e_y$) \{
    \INT $A_x = \length{e_x}$
    \INT $A_y = \length{e_y}$
    \EXPR $e_1$, $e_2$, $e_3$, $e_4$
    \INT $X_1$, $X_2$, $X_3$, $X_4$
    /* \textnormal{ГЙЛМ ХДМЙОЕОЙС РЕТЕНЕОПК $e_1$, РЕТЕВПТ ЧБТЙБОФПЧ} */
    \INT $min_1 = \Max{(0, \left\lfloor {(A_x - A_y)/2}\right\rfloor)}$    
    \INT $max_1 = \Min{(A_x, \left\lceil{(A_x + A_y)/2}\right\rceil)}$    
    \FOR ($X_1 = min_1$; $X_1 \leq max_1$; $X_1\mathclose{++}$) \{
       $X_2 = A_x - X_1$
       /* $2 \cdot X_4 = A_y + A_x - 2 \cdot X_1$ */
       \IF $(A_y + A_x - 2\cdot X_1)$ \MOD $2$ $\neq$ $0$ \THEN \GOTO next
       $X_4 = (A_y + A_x - 2 \cdot X_1)/2$
       $X_3 = A_y - X_4$
       $e_1 = \subexpr{e_x}{0}{X_1}$
       $e_2 = \subexpr{e_x}{X_1}{X_2}$
       $e_3 = \subexpr{e_y}{0}{X_3}$
       $e_4 = \subexpr{e_y}{X_3}{X_4}$
       \IF $e_1 \mathop{++} e_4$ $\neq$ $e_3 \mathop{++} e_2$ \THEN \GOTO next
       \RETURN True
    next:
    \}
    \RETURN False
  \}
\end{ASAIL}
%\end{quote}
	\caption{ьЖЖЕЛФЙЧОБС УИЕНБ ТЕБМЙЪБГЙЙ ЖХОЛГЙЙ \ttfamily{AreSymmetric}}
	\label{pic:AreSymmetric}
\end{figure}

\subsection{пФ ЙДЕЙ Л ТЕБМЙЪБГЙЙ}
\label{sec:Intro:Finish}

ч РТЕДЩДХЭЙИ ТБЪДЕМБИ РПЛБЪБОЩ РТЙНЕТЩ ЬЖЖЕЛФЙЧОПК ЛПНРЙМСГЙЙ
УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС Ч БВУФТБЛФОЩК ЙНРЕТБФЙЧОЩК СЪЩЛ, ДПРХУЛБАЭЙК
РТПУФХА Й ЬЖЖЕЛФЙЧОХА ТЕБМЙЪБГЙА ОБ УПЧТЕНЕООЩИ ьчн.  рТЙ ЬФПН РТЕДРПМБЗБМПУШ,
ЮФП ПРЕТБГЙЙ ЧЩЮЙУМЕОЙС ДМЙОЩ ЧЩТБЦЕОЙС Й ЛПОУФТХЙТПЧБОЙС РПДЧЩТБЦЕОЙС
ЧЩРПМОСАФУС ЪБ ЛПОУФБОФОПЕ (ОЕ ЪБЧЙУСЭЕЕ ПФ ЧЩТБЦЕОЙС) ЧТЕНС.  ьФП 
РТЕДРПМПЦЕОЙЕ ЧЕТОП ДМС ЧУЕИ УПЧТЕНЕООЩИ ТЕБМЙЪБГЙК СЪЩЛБ тЕЖБМ.

ъБ УЮЕФ ДЕЫЕЧЙЪОЩ ЬФЙИ ПРЕТБГЙК Ч РТПГЕУУЕ УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС
НПЦОП ЧЕУФЙ УПЧНЕУФОЩК БОБМЙЪ ДМЙО ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК Й ХУМПЧЙК ОБ 
ДМЙОЩ УЧПВПДОЩИ РЕТЕНЕООЩИ.  ъБЮБУФХА ФБЛПК БОБМЙЪ РПЪЧПМСЕФ ВЩУФТП
(ВЕЪ РПУЙНЧПМШОПЗП УТБЧОЕОЙС ЧЩТБЦЕОЙК) ПФУЕЮШ ГЕМЩЕ ПВМБУФЙ ЪОБЮЕОЙК
УЧПВПДОЩИ РЕТЕНЕООЩИ, ОБ ЛПФПТЩИ ПФПЦДЕУФЧМЕОЙЕ ЪБЧЕДПНП ОЕ НПЦЕФ ДБФШ
РПМПЦЙФЕМШОПЗП ТЕЪХМШФБФБ.

пФНЕФЙН ФБЛЦЕ, ЮФП ДЕЫЕЧБС ПРЕТБГЙС ЛПОУФТХЙТПЧБОЙС РПДЧЩТБЦЕОЙС 
ЙУРПМШЪХЕФУС ДМС ДТПВМЕОЙС УПРПУФБЧМЕОЙК ОБ ЮБУФЙ, ЮФП РПЪЧПМСЕФ 
ЧЩОЕУФЙ ЪБ РТЕДЕМЩ ГЙЛМПЧ НБЛУЙНБМШОПЕ ЛПМЙЮЕУФЧП ПРЕТБГЙК.

тБУУНБФТЙЧБЕНЩЕ Ч ТБВПФЕ ПРФЙНЙЪБГЙЙ ДПУФБФПЮОП ПЮЕЧЙДОЩ Й, РТЙ ЬФПН, 
ПОЙ ДБАФ УХЭЕУФЧЕООЩК ЧЩЙЗТЩЫ Ч ЬЖЖЕЛФЙЧОПУФЙ.  пДОБЛП ДП УЙИ РПТ ПОЙ 
ОЕ ЙУРПМШЪПЧБМЙУШ Ч ТЕБМЙЪБГЙСИ СЪЩЛБ тЕЖБМ.

\section{уЙОФБЛУЙЮЕУЛПЕ ПФПЦДЕУФЧМЕОЙЕ: ПУОПЧОЩЕ РПОСФЙС}
%\section{пФПЦДЕУФЧМЕОЙЕ У ПВЯЕЛФОЩН ЧЩТБЦЕОЙЕН}

\subsection{пУОПЧОЩЕ РПОСФЙС Й ПВПЪОБЮЕОЙС} пУОПЧОЩЕ РПОСФЙС СЪЩЛБ тЕЖБМ
Й ПУОПЧОЩЕ ПВПЪОБЮЕОЙС НЩ ЪБЙНУФЧХЕН ЙЪ ТБВПФЩ~\cite{bib:Refal+}.  ч ФПН ЮЙУМЕ
ЪБЙНУФЧХЕН УМЕДХАЭЙЕ РПОСФЙС Й ПВПЪОБЮЕОЙС ДМС ОЙИ:
\begin{itemize}
	\item $\Oe$ \--- ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ;
	\item $\Os$ \--- ПВЯЕЛФОЩК УЙНЧПМ;
	\item $\Pe$ \--- ПВТБЪГПЧПЕ (Ф.~Е. ЧПЪНПЦОП УПДЕТЦБЭЕЕ РЕТЕНЕООЩЕ) ЧЩТБЦЕОЙЕ;
	\item $\Pt$ \--- ПВТБЪГПЧЩК ФЕТН (Ф.~Е. ПВЯЕЛФОЩК УЙНЧПМ, РЕТЕНЕООБС ЙМЙ
		ПВТБЪГПЧПЕ ЧЩТБЦЕОЙЕ Ч УЛПВЛБИ);
	\item $\He$ \--- ЦЕУФЛПЕ ЧЩТБЦЕОЙЕ.
	% DONE: Ant: ДПВБЧЙФШ ЧУЕ (ЙМЙ РПЮФЙ ЧУЕ) ЙУРПМШЪХЕНПЕ
\end{itemize}
нЩ ТБУЫЙТСЕН РПОСФЙЕ ФЙРБ ТЕЖБМ\-/РЕТЕНЕООПК УМЕДХАЭЙН ПВТБЪПН: ЮЕТЕЪ $V[m,n]$,
ЗДЕ $m\in\mathbb{Z}$ \--- ГЕМПЕ ЮЙУМП, $n\in\tilde{\mathbb{Z}}$ \--- ГЕМПЕ
ЮЙУМП ЙМЙ~$\infty$, НЩ ПВПЪОБЮБЕН ТЕЖБМ\-/РЕТЕНЕООХА, ДПРХУФЙНЩЕ ЪОБЮЕОЙС ЛПФПТПК
НПЗХФ ЙНЕФШ ДМЙОЩ ЙЪ ПФТЕЪЛБ $[m,n]$.  рТЙЧЩЮОЩЕ РЕТЕНЕООЩЕ тЕЖБМБ Ч ФБЛПК
ОПФБГЙЙ ВХДХФ ЪБРЙУБОЩ УМЕДХАЭЙН ПВТБЪПН:
\begin{itemize}
	\item $s$\=/РЕТЕНЕООЩЕ: $s[1,1]$;
	\item $t$\=/РЕТЕНЕООЩЕ: $t[1,1]$;
	\item $e$\=/РЕТЕНЕООЩЕ: $t[0,\infty]$;
	\item $v$\=/РЕТЕНЕООЩЕ: $t[1,\infty]$;
\end{itemize}

\subsection{вБЪПЧЩК УМХЮБК: ПФПЦДЕУФЧМЕОЙЕ ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС У ПВТБЪГПН}

\emph{вБЪПЧЩН ЛМЬЫЕН} (ПФ БОЗМЙКУЛПЗП clash) ВХДЕН ОБЪЩЧБФШ ЛПОУФТХЛГЙА ЧЙДБ
${\Oe : \Pe}$, ЗДЕ $\Oe$ \--- ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ, Б $\Pe$ \--- ПВТБЪГПЧПЕ
\ignore{(Ф.~Е. ЧПЪНПЦОП УПДЕТЦБЭЕЕ РЕТЕНЕООЩЕ) }ЧЩТБЦЕОЙЕ.

\emph{тЕЫЕОЙЕН ВБЪПЧПЗП ЛМЬЫБ} ОБЪЩЧБЕФУС ХРПТСДПЮЕООПЕ НОПЦЕУФЧП
$[\sigma_1,\ldots,\sigma_n]$ РПДУФБОПЧПЛ
$\sigma_i = \{V_j \to \Oe_{ij} \mid V_j\mbox{ \--- РЕТЕНЕООБС ЙЪ }\Pe\}$,
РТЙ ЛПФПТЩИ $\Pe$ ТЕДХГЙТХЕФУС Л $\Oe$: $\Pe/{\sigma_i} = \Oe$.

чП ЧТЕНС ЧЩРПМОЕОЙС ТЕЖБМ\-/РТПЗТБНН ОЕПВИПДЙНП ХНЕФШ ОБИПДЙФШ ТЕЫЕОЙС,
ХДПЧМЕФЧПТСАЭЙЕ ПРТЕДЕМЕООПНХ ПФОПЫЕОЙА РПТСДЛБ ОБ РПДУФБОПЧЛБИ.
уХЭЕУФЧХАЭЙЕ ДЙБМЕЛФЩ тЕЖБМБ ПРТЕДЕМСАФ ФПМШЛП ДЧБ РТПФЙЧПРПМПЦОЩИ ПФОПЫЕОЙС
РПТСДЛБ, ОБЪЩЧБЕНЩИ~\cite{bib:Refal+} УПРПУФБЧМЕОЙСНЙ \emph{УМЕЧБ ОБРТБЧП} Й
\emph{УРТБЧБ ОБМЕЧП}.

рПУЛПМШЛХ ЧБТЙБОФЩ ЧУЕИ ОЙЦЕПРЙУБООЩИ
БМЗПТЙФНПЧ ДМС ЬФЙИ ДЧХИ УМХЮБЕЧ БВУПМАФОП БОБМПЗЙЮОЩ, НЩ ПЗТБОЙЮЙНУС
ТБУУНПФТЕОЙЕН УПРПУФБЧМЕОЙС УМЕЧБ ОБРТБЧП, ЛПФПТПЕ ЪБДБЕФУС УМЕДХАЭЙН ПВТБЪПН.
рХУФШ $\sigma_1,\, \sigma_2$ \--- РПДУФБОПЧЛЙ\-/ТЕЫЕОЙС ВБЪПЧПЗП ЛМЬЫБ 
${\Oe : \Pe}$, ФПЗДБ ЗПЧПТСФ, ЮФП РПДУФБОПЧЛБ $\sigma_1$ РТЕДЫЕУФЧХЕФ РПДУФБОПЧЛЕ 
$\sigma_2$, ЕУМЙ $V/{\sigma_1}$ ЛПТПЮЕ, ЮЕН $V/{\sigma_2}$, ЗДЕ $V$ \--- 
РЕТЧБС (УМЕЧБ ОБРТБЧП) РЕТЕНЕООБС ЙЪ $\Pe$, ФБЛБС, ЮФП
$V/{\sigma_1} \ne V/{\sigma_2}$. 

\subsection{рЕТЕУФТПКЛБ}
ч ТЕЖБМ\-/РТПЗТБННЕ ВХДЕН ОБЪЩЧБФШ \emph{РЕТЕУФТПКЛПК} ЛПОУФТХЛГЙА
${\Pe_L : \Pe_R}$, ЗДЕ Й МЕЧБС, Й РТБЧБС ЮБУФЙ СЧМСАФУС ПВТБЪГПЧЩНЙ ЧЩТБЦЕОЙСНЙ,
РТЙЮЕН $\Pe_L$ СЧМСЕФУС \emph{ЙУФПЮОЙЛПН}, ФП ЕУФШ, $\Pe_L$ СЧМСЕФУС ЧЩТБЦЕОЙЕН,
УПДЕТЦБЭЙН ФПМШЛП \emph{УФБТЩЕ РЕТЕНЕООЩЕ\footnote{
	 уФБТЩЕ РЕТЕНЕООЩЕ \--- ПЪОБЮЕООЩЕ РЕТЕНЕООЩЕ, РЕТЕНЕООЩЕ, ЮШЙ ЪОБЮЕОЙС ВЩМЙ
	 ПРТЕДЕМЕОЩ Ч ТЕЖБМ\-/РТПЗТБННЕ ТБОЕЕ.  чУЕ ПУФБМШОЩЕ РЕТЕНЕООЩЕ ОБЪЩЧБАФУС \emph{ОПЧЩНЙ}.
}} \--- РЕТЕНЕООЩЕ, ЙНЕАЭЙЕ ЪОБЮЕОЙЕ Л НПНЕОФХ ЧЩЮЙУМЕОЙС ДБООПЗП ЧЩТБЦЕОЙС.

\subsection{чЩРПМОЕОЙЕ Й ЛПНРЙМСГЙС РЕТЕУФТПКЛЙ}

чЩТБЦЕОЙС\-/ЙУФПЮОЙЛЙ Л НПНЕОФХ ЧЩРПМОЕОЙС РЕТЕУФТПКЛЙ ЧУЕЗДБ ТЕДХГЙТХАФУС ДП
ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК.  фБЛЙН ПВТБЪПН, Ч ЛПТТЕЛФОП УПУФБЧМЕООПК РТПЗТБННЕ
РЕТЕУФТПКЛБ ${\Pe_L : \Pe_R}$ Ч НПНЕОФ УЧПЕЗП ЧЩРПМОЕОЙС ТЕДХГЙТХЕФУС ДП ВБЪПЧПЗП
ЛМЬЫБ, Й ЕЕ ЧЩРПМОЕОЙЕ УЧПДЙФУС Л ТЕЫЕОЙА ЬФПЗП ВБЪПЧПЗП ЛМЬЫБ.  б ЧП ЧТЕНС
ЛПНРЙМСГЙЙ ЛПНРЙМСФПТ ДПМЦЕО РП ЪБДБООПК РЕТЕУФТПКЛЕ ${\Pe_L : \Pe_R}$ ЧЩРЙУБФШ
ЙНРЕТБФЙЧОЩК БМЗПТЙФН ДМС ТЕЫЕОЙС МАВЩИ ВБЪПЧЩИ ЛМЬЫЕК, ЛПФПТЩЕ НПЗХФ
РПМХЮЙФШУС ЙЪ ДБООПК РЕТЕУФТПКЛЙ РТЙ ТБЪОЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ.

\subsection{гЕРПЮЛЙ РЕТЕУФТПЕЛ}

лБЛ ВЩМП РПЛБЪБОП Ч ТБЪДЕМЕ~\ref{s:intro}, БМЗПТЙФН РПЙУЛБ ТЕЫЕОЙС НПЦОП УДЕМБФШ
ВПМЕЕ ЬЖЖЕЛФЙЧОЩН, ЕУМЙ ЧНЕУФП ПДОПК РЕТЕУФТПКЛЙ ТБУУНБФТЙЧБФШ ГЕРПЮЛХ 
РПДТСД ЙДХЭЙИ РЕТЕУФТПЕЛ.
ьФП УЧСЪБОП У ФЕН, ЮФП РПУМЕДХАЭЙЕ РЕТЕУФТПКЛЙ НПЗХФ ОБЛМБДЩЧБФШ ПЗТБОЙЮЕОЙС ОБ
РЕТЕНЕООЩЕ, ЧУФТЕЮБАЭЙЕУС Ч ТБОЕЕ ЙДХЭЙИ РЕТЕУФТПКЛБИ, УПЛТБЭБС, ФЕН УБНЩН, ПВМБУФШ
РЕТЕВПТБ ЧБТЙБОФПЧ.

рПЬФПНХ НЩ ЧЕЪДЕ ДБМЕЕ ВХДЕН ТБВПФБФШ У ГЕРПЮЛПК РЕТЕУФТПЕЛ
\[
\langle \Pe_L^1 : \Pe_R^1, \ldots, \Pe_L^n : \Pe_R^n \rangle,
\]
Ч РТЕДРПМПЦЕОЙЙ, ЮФП
ЛПНРЙМСФПТ РПЪБВПФЙМУС П ОБИПЦДЕОЙЙ НБЛУЙНБМШОП ДМЙООПК ГЕРПЮЛЙ РПДТСД ЙДХЭЙИ
РЕТЕУФТПЕЛ.

рТЙ ЖЙЛУЙТПЧБООЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ \emph{ТЕЫЕОЙЕ ГЕРПЮЛЙ РЕТЕУФТПЕЛ} УФТПЙФУС УМЕДХАЭЙН ПВТБЪПН.

рХУФШ $[\sigma_1,\ldots,\sigma_k]$ \--- ТЕЫЕОЙЕ ГЕРПЮЛЙ
\[
\langle \Pe_L^1 : \Pe_R^1, \ldots, \Pe_L^{n-1} : \Pe_R^{n-1} \rangle.
\]
фПЗДБ ТЕЫЕОЙЕ ГЕРПЮЛЙ
\[
\langle \Pe_L^1 : \Pe_R^1, \ldots, \Pe_L^n : \Pe_R^n \rangle
\]
ЕУФШ ПВЯЕДЙОЕОЙЕ (У УПИТБОЕОЙЕН РПТСДЛБ ЬМЕНЕОФПЧ) $S_1\cup\ldots\cup S_k$ ХРПТСДПЮЕООЩИ ОБВПТПЧ РПДУФБОПЧПЛ, ЗДЕ ЛБЦДЩК ОБВПТ $S_i$ РПМХЮБЕФУС ПВЯЕДЙОЕОЙЕН РПДУФБОПЧЛЙ $\sigma_i$ РППЮЕТЕДОП У ЛБЦДПК РПДУФБОПЧЛПК ЙЪ ТЕЫЕОЙС РЕТЕУФТПКЛЙ ${\Pe_L^n/\sigma_i : \Pe_R^n/\sigma_i}$ (ЕУМЙ ТЕЫЕОЙЕ ЬФПК РЕТЕУФТПКЛЙ РХУФПЕ, ФП Й ОБВПТ $S_i$ ВХДЕФ РХУФЩН).

\section{лПНРЙМСГЙС ГЕРПЮЛЙ РЕТЕУФТПЕЛ}
\label{sec:ClashesSeqCompilation}

ч ДБООПН ТБЪДЕМЕ НЩ ТБУУНПФТЙН ПУОПЧОЩЕ РПОСФЙС Й ДЕФБМЙ ТЕБМЙЪБГЙЙ БМЗПТЙФНБ
ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ, ЙУРПМШЪХЕНПЗП Ч ОПЧПК
ТЕБМЙЪБГЙЙ~\cites{bib:Web:New-Refal+, bib:Refal-Plus-04} СЪЩЛБ тЕЖБМ рМАУ.

лБЛ ХЦЕ ВЩМП УЛБЪБОП, ЛПНРЙМСФПТ ВХДЕФ ТБВПФБФШ УП УМЕДХАЭЙНЙ ПВЯЕЛФБНЙ:
ТЕЖБМ\-/РЕТЕНЕООЩЕ $V$, ПВЯЕЛФОЩЕ ЧЩТБЦЕОЙС $\Oe$, ПВТБЪГПЧЩЕ ЧЩТБЦЕОЙС $\Pe$,
РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$, ГЕРПЮЛЙ РЕТЕУФТПЕЛ
\(
\Scl=\langle \Pe_L^1 : \Pe_R^1, \ldots, \Pe_L^n : \Pe_R^n \rangle
\).
% DONE: ТЕЫЙФШ, ЛБЛ РТБЧЙМШОП: УЙУФЕНБ РЕТЕУФТПЕЛ, ЙМЙ ГЕРПЮЛБ РЕТЕУФТПЕЛ.
% й ЧЩРТБЧЙФШ ЬФП РП ЧУЕНХ ФЕЛУФХ.

лПНРЙМСФПТ УФТПЙФ ЛПД ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ЧЩРПМОСАЭЕК ЪБДБООХА ГЕРПЮЛХ
РЕТЕУФТПЕЛ $\Scl$.  ч РТПГЕУУЕ ЧЩРПМОЕОЙС ЬФПК ГЕРПЮЛЙ ЧУЕ ВПМШЫЕ ОПЧЩИ
РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч $\Scl$, РПМХЮБАФ ЪОБЮЕОЙС \--- УФБОПЧСФУС
УФБТЩНЙ РЕТЕНЕООЩНЙ.  дМС ФПЗП ЮФПВЩ ИТБОЙФШ ЙОЖПТНБГЙА П ФПН, ЛБЛЙЕ
РЕТЕНЕООЩЕ ВХДХФ ЙНЕФШ ЪОБЮЕОЙС РПУМЕ ЙУРПМОЕОЙС ЛПДБ, РПУФТПЕООПЗП ОБ ДБООЩК
НПНЕОФ, ЛПНРЙМСФПТ ЙУРПМШЪХЕФ УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ $\Old$.

\subsection{зЕОЕТЙТХЕНБС ЙНРЕТБФЙЧОБС РТПЗТБННБ}

рТЙ ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ Ч ЧЩИПДОПК РТПЗТБННЕ
ЙУРПМШЪХАФУС УМЕДХАЭЙЕ ЛПОУФТХЛГЙЙ ЙНРЕТБФЙЧОПЗП СЪЩЛБ:
\begin{itemize}
	\item РЕТЕНЕООЩЕ ЙНРЕТБФЙЧОПЗП СЪЩЛБ ДЧХИ ФЙРПЧ:
	
\begin{itemize}
	\item
      \EXPR\-/РЕТЕНЕООЩЕ, ЪОБЮЕОЙСНЙ ЛПФПТЩИ СЧМСАФУС ПВЯЕЛФОЩЕ ТЕЖБМ\-/ЧЩТБЦЕОЙС;
	\item
      \INT\-/РЕТЕНЕООЩЕ, ЪОБЮЕОЙСНЙ ЛПФПТЩИ СЧМСАФУС ОЕПФТЙГБФЕМШОЩЕ ГЕМЩЕ ЮЙУМБ (ДМЙОЩ ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК) Й ПУПВПЕ ЪОБЮЕОЙЕ\footnote{
			ъОБЮЕОЙЕ $\infty$ ВХДЕФ ЧУФТЕЮБФШУС ФПМШЛП Ч ФБЛПН ЛПОФЕЛУФЕ, ЮФП ТЕЪХМШФБФ ПРЕТБГЙК У ОЙН ПРТЕДЕМСЕФУС ЙОФХЙФЙЧОП РПОСФОЩН, ПДОПЪОБЮОЩН ПВТБЪПН: ${\infty + \infty = \infty}$, ${\infty + x = \infty}$, ${\Min(\infty,x) = x}$ Й Ф.~Р. (ЪДЕУШ $x$ \--- ОЕПФТЙГБФЕМШОПЕ ГЕМПЕ ЮЙУМП).
	} $\infty$;
\end{itemize}
	\item ЧЩТБЦЕОЙС ДЧХИ ФЙРПЧ (\EXPR{} Й \INT\footnote{
			ъОБЮЕОЙСНЙ ЧЩТБЦЕОЙК ФЙРБ \INT{} НПЗХФ СЧМСФШУС МАВЩЕ ГЕМЩЕ ЮЙУМБ, $\infty$ Й~$-\infty$.
		}), РПУФТПЕООЩЕ ОБД ЬФЙНЙ РЕТЕНЕООЩНЙ Й ЛПОУФБОФБНЙ РТЙ РПНПЭЙ УППФЧЕФУФЧХАЭЙИ ОБВПТПЧ ПРЕТБГЙК (УН. тЙУ.~\ref{fig:Syntax});
	\item МПЗЙЮЕУЛЙЕ ЧЩТБЦЕОЙС, ЙУРПМШЪХЕНЩЕ Ч ХУМПЧЙСИ ПРЕТБФПТПЧ \IF\ Й \FOR\ (УН. тЙУ.~\ref{fig:Syntax});
	\item ПРЕТБФПТЩ (УН. тЙУ.~\ref{fig:Syntax}).
\end{itemize}
рПДЮЕТЛОЕН, ЮФП ЪДЕУШ ТБУУНБФТЙЧБЕФУС РПДНОПЦЕУФЧП ЙНРЕТБФЙЧОПЗП
СЪЩЛБ\footnote{
     ч ТБВПФЕ~\cite{bib:Refal-Plus-04} ЙНРЕТБФЙЧОЩК СЪЩЛ, ЙУРПМШЪХЕНЩК ДМС ЛПНРЙМСГЙЙ
ТЕЖБМ\-/РТПЗТБНН Ч РТПЕЛФЕ~\cite{bib:Web:New-Refal+}, ПРЙУБО РПМОЕЕ.
}, ДПУФБФПЮОПЕ ДМС ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ.

уЕНБОФЙЛБ ЧЩТБЦЕОЙК Й ПРЕТБФПТПЧ ДПУФБФПЮОБ ПЮЕЧЙДОБ.  рПЬФПНХ ДБДЙН РПСУОЕОЙС ФПМШЛП РП РПЧПДХ ПРЕТБФПТБ \FOR, ЛПФПТЩК Ч ДБООПК ТБВПФЕ ЧУЕЗДБ ЙНЕЕФ УМЕДХАЭЙК ЧЙД:
\begin{quote}
\begin{ASAIL}
   \FOR\ ($i = a_1$; $i \leq a_2$; $i\mathclose{++}$) \{
       $\mathit{op}$
   $\mathit{label}$:
   \}
\end{ASAIL}
\end{quote}
ЗДЕ $i$\---\INT\-/РЕТЕНЕООБС; $a_1$ Й $a_2$ \---\INT\-/ЧЩТБЦЕОЙС; $\mathit{op}$\---ПРЕТБФПТ (ЧПЪНПЦОП УПУФБЧОПК), ФЕМП ГЙЛМБ; $\mathit{label}$ \--- НЕФЛБ, РЕТЕИПД ОБ ЛПФПТХА (Ч ОБЫЕН УМХЮБЕ НПЦЕФ ВЩФШ ФПМШЛП ЙЪ ФЕМБ ГЙЛМБ) ЧЩЪЩЧБЕФ ЧЩРПМОЕОЙЕ УМЕДХАЭЕК РП ПЮЕТЕДЙ ЙФЕТБГЙЙ ГЙЛМБ.  ч ОБЫЕН УМХЮБЕ, ЧЩТБЦЕОЙС $a_1$ Й $a_2$ ОЕ ВХДХФ ЪБЧЙУЕФШ ПФ РЕТЕНЕООЩИ, ЙЪНЕОСЕНЩИ Ч ФЕМЕ ГЙЛМБ, РПЬФПНХ ЪОБЮЕОЙС ($i_1$ Й $i_2$) ЬФЙИ ЧЩТБЦЕОЙК НПЦОП РПУЮЙФБФШ ЪБТБОЕЕ, ДП ЧИПДБ Ч ГЙЛМ Й Ч ОБЫЕН УМХЮБЕ ЬФЙ ЪОБЮЕОЙС ВХДХФ ОЕПФТЙГБФЕМШОЩНЙ ЮЙУМБНЙ.  чЩРПМОЕОЙЕ ТБУУНБФТЙЧБЕНПЗП ПРЕТБФПТБ \FOR\ УПУФПЙФ Ч ЧЩРПМОЕОЙЙ ФЕМБ ГЙЛМБ ДМС ЧУЕИ ГЕМПЮЙУМЕООЩИ ЪОБЮЕОЙК РЕТЕНЕООЩИ $i$ ПФ $i_1$ ДП $i_2$ ЧЛМАЮЙФЕМШОП.  еУМЙ $i_1 > i_2$, ФП ФЕМП ГЙЛМБ ОЕ ВХДЕФ ЧЩРПМОЕОП ОЙ ТБЪХ, ЧП ЧУЕИ ПУФБМШОЩИ УМХЮБСИ ФЕМП ГЙЛМБ ВХДЕФ ЧЩРПМОЕОП $(i_2 - i_1 +1)$ ТБЪ.

%=======================================================================
\begin{figure}
\begin{center}\small
\newcommand{\ie}{\ensuremath{\mathit{ie}}}
\newcommand{\iv}{\ensuremath{\mathit{iv}}}
\newcommand{\ic}{\ensuremath{\mathit{ic}}}
\newcommand{\ee}{\ensuremath{\mathit{ee}}}
\newcommand{\ev}{\ensuremath{\mathit{ev}}}
\newcommand{\ec}{\ensuremath{\mathit{ec}}}
\newcommand{\be}{\ensuremath{\mathit{be}}}
\newcommand{\ci}{\ensuremath{\mathit{ci}}}
\newcommand{\op}{\ensuremath{\mathit{op}}}
\newcommand{\lb}{\ensuremath{\mathit{lb}}}
\newcommand{\IS}{\ensuremath{\is}}
\newcommand{\VL}{\ensuremath{|}}

\begin{tabular}{|l@{~}r@{~}l@{~}l|}%
\hline&&&\\[-2ex]

    &     &                                & \emph{\INT{}\-/ЧЩТБЦЕОЙС} \\
\ie & \IS & \iv\ {\VL} \ic                 & \--- РЕТЕНЕООЩЕ Й ЛПОУФБОФЩ \\
    & \VL & $\Min(\ie, \ie)$
     {\VL}  $\Max(\ie, \ie)$               & \--- НЙОЙНХН Й НБЛУЙНХН \\
    & \VL & $\lceil \ie \DIV \ie \rceil$
     {\VL}  $\lfloor \ie \DIV \ie \rfloor$ & \--- ДЕМЕОЙЕ У ПЛТХЗМЕОЙЕН (ЧЧЕТИ/ЧОЙЪ)\\
    & \VL & $\ie \DIV \ie$
     {\VL}  \ie\ $\MOD$ \ie                 & \--- ДЕМЕОЙЕ ОБГЕМП, ПУФБФПЛ ПФ ДЕМЕОЙС \\
    & \VL & $\ie \cdot \ie$
     {\VL}  $\ie + \ie$
     {\VL}  $\ie - \ie$                    & \--- ХНОПЦЕОЙЕ, УМПЦЕОЙЕ, ЧЩЮЙФБОЙЕ \\
    & \VL & $\length{\ee}$                 & \--- ДМЙОБ ЧЩТБЦЕОЙС 
    
\\[1ex]\hline&&&\\[-2ex]    
    
    &     &                                & \emph{\EXPR{}\-/ЧЩТБЦЕОЙС} \\
\ee & \IS & \ev{}
     {\VL}  \ec                            & \--- РЕТЕНЕООЩЕ Й ЛПОУФБОФЩ \\
    & \VL & $\ee \mathop{++} \ee$          & \--- ЛПОЛБФЕОБГЙС \\
    & \VL & $(\ee)$
     {\VL}  $*\ee$                         & \--- ЧЪСФЙЕ Ч УЛПВЛЙ Й УОСФЙЕ УЛПВПЛ \\
    & \VL & $\subexpr{\ee}{\ie}{\ie}$
     {\VL}  $\subterm{\ee}{\ie}$           & \--- ЧЪСФЙЕ РПДЧЩТБЦЕОЙС Й ФЕТНБ

\\[1ex]\hline&&&\\[-2ex]    

    &     &                                & \emph{МПЗЙЮЕУЛЙЕ ЧЩТБЦЕОЙС}\\

\be & \IS & \Verb|true| {\VL} \Verb|false| & \--- МПЗЙЮЕУЛЙЕ ЛПОУФБОФЩ\\
    & \VL & \be\ \OR\ \be                  & \--- МПЗЙЮЕУЛПЕ <<ЙМЙ>>\\
    & \VL & $\SYMB(\ee)$                   & \--- ЪОБЮЕОЙЕ \ee\ \--- УЙНЧПМ?\\
    & \VL & $\PARENTH(\ee)$                & \--- ЪОБЮЕОЙЕ \ee\ \--- УЛПВПЮОЩК ФЕТН?\\
    & \VL & $\ee = \ee$
     {\VL}  $\ee \neq \ee$                 & \--- УТБЧОЕОЙС \EXPR\-/ЪОБЮЕОЙК\\
    & \VL & \ie\ $\nabla$ \ie           & \--- УТБЧОЕОЙЕ \INT{}\-/ЪОБЮЕОЙК, ЗДЕ:\\
$\nabla$ & \IS & $<$ {\VL} $>$ {\VL} $\leq$ 
     {\VL} $\geq$ {\VL} $\neq$ {\VL} $=$   & \--- ПРЕТБГЙЙ УТБЧОЕОЙС \INT{}\-/ЪОБЮЕОЙК

\\[1ex]\hline&&&\\[-2ex]    

    &     &                                & \emph{ПРЕТБФПТЩ}\\
\op & \IS & \EXPR\ $\ev,\ldots \ev$        & \--- ПРТЕДЕМЕОЙЕ \EXPR{}\-/РЕТЕНЕООЩИ\\
    & \VL & \INT\ $\iv,\ldots \iv$         & \--- ПРТЕДЕМЕОЙЕ \INT{}\-/РЕТЕНЕООЩИ\\
    & \VL & \op; \op                       & \--- РПУМЕДПЧБФЕМШОПУФШ ПРЕТБФПТПЧ\\
    & \VL & \IF\ \be\ \THEN\ \GOTO\ \lb    & \--- ХУМПЧОЩК РЕТЕИПД ОБ НЕФЛХ \lb\\
    & \VL & \iv\ $=$ \ie\ {\VL} \ev\ $=$ \ee& \--- \INT{}- Й \EXPR{}-РТЙУЧБЙЧБОЙС\\
    & \VL & \FOR\ (\iv\ $=$ \ie; \be; $\iv\mathclose{++}$) & \\
    &     & \hspace*{2ex}\{\op; \lb:\}     & \--- ГЙЛМ РП \INT{}\-/РЕТЕНЕООПК
\\[1ex]\hline
\end{tabular}
\end{center}
\caption{лПОУФТХЛГЙЙ ЙНРЕТБФЙЧОПЗП СЪЩЛБ, ЙУРПМШЪХЕНЩЕ РТЙ ЛПНРЙМСГЙЙ ГЕРПЮЕЛ РЕТЕУФТПЕЛ}
\label{fig:Syntax}
\end{figure}
%=======================================================================

\subsection{уПУФПСОЙЕ ЛПНРЙМСФПТБ}
\label{sec:comp-params}

лПНРЙМСФПТ НПЦОП ТБУУНБФТЙЧБФШ ЛБЛ ТЕЛХТУЙЧОХА ЖХОЛГЙА УП УМЕДХАЭЙН БТЗХНЕОФПН
(УПУФПСОЙЕ ЛПНРЙМСФПТБ) 
	\[(\Scl, \Old, \Fail)~,\]
ЗДЕ 
\begin{itemize}
	\item $\Scl$ \--- ГЕРПЮЛБ РЕТЕУФТПЕЛ;
	\item $\Old$ \--- УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ;
	\item $\Fail$ \---  НЕФЛБ Ч ТБОЕЕ РПУФТПЕООПН ЛПДЕ ЙНРЕТБФЙЧОПК
		РТПЗТБННЩ, РЕТЕИПД ОБ ЛПФПТХА ПВЩЮОП УППФЧЕФУФЧХЕФ ЧЩРПМОЕОЙА УМЕДХАЭЕК РПРЩФЛЙ
		ХДМЙОЕОЙС ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК.
\end{itemize}

лТПНЕ ФПЗП, ОЕСЧОП РТЕДРПМБЗБЕФУС, ЮФП Ч РТПГЕУУЕ ТБВПФЩ РТПЙУИПДЙФ НЕНПЙЪБГЙС
РПМХЮЕООЩИ УПУФПСОЙК Й РТПНЕЦХФПЮОЩИ ЧЩЮЙУМЕОЙК.  ьФП ЙУРПМШЪХЕФУС ДМС ФПЗП,
ЮФПВЩ ОЕ ЗЕОЕТЙТПЧБФШ Ч ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ МЙЫОЙИ РТПЧЕТПЛ
(УН.~ЫБЗ~\ref{lst:EQ-conds} БМЗПТЙФНБ \EqA, ТБЪДЕМ~\ref{sec:EqA},
Й~ЫБЗ~\ref{lst:CL-symbols} БМЗПТЙФНБ \ClA, ТБЪДЕМ~\ref{sec:ClA}).

ч ОБЮБМШОЩК НПНЕОФ ЧТЕНЕОЙ УРЙУПЛ $\Old$ УПДЕТЦЙФ РЕТЕНЕООЩЕ ЙЪ $\Scl$, ЪОБЮЕОЙС ЛПФПТЩИ ЙЪЧЕУФОЩ ДП ОБЮБМБ ЧЩРПМОЕОЙС ДБООПК ГЕРПЮЛЙ РЕТЕУФТПЕЛ.

нЕФЛБ $\Fail$ ЙЪОБЮБМШОП УППФЧЕФУФЧХЕФ ЖТБЗНЕОФХ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ЙУРПМОСЕНПНХ Ч УМХЮБЕ, ЛПЗДБ ЧЩРПМОЕОЙЕ ГЕРПЮЛЙ РЕТЕУФТПЕЛ ЪБЛБОЮЙЧБЕФУС ОЕХУРЕИПН.


\subsection{\CSC: БМЗПТЙФН ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ}
\label{sec:CSC}
бМЗПТЙФН ЛПНРЙМСГЙЙ \CSC{} ДМС ФЕЛХЭЕЗП УПУФПСОЙС
% TeX-hack -- РПДБЧЙМ bad-box ЪБ УЮЕФ "\,"
\((\Scl,\, \Old,\, \Fail)\) НПЦОП ПРЙУБФШ УМЕДХАЭЙН ПВТБЪПН:
\begin{algo}
	\item еУМЙ ГЕРПЮЛБ $\Scl$ РХУФБС, ФП ЪБЧЕТЫЙФШ ТБВПФХ БМЗПТЙФНБ\footnote{%
		бМЗПТЙФНЩ ЛПНРЙМСГЙЙ ПУФБФЛБ ТЕЖБМ\-/РТЕДМПЦЕОЙС, УМЕДХАЭЕЗП ЪБ
		УЛПНРЙМЙТПЧБООПК ГЕРПЮЛПК РЕТЕУФТПЕЛ, ВХДХФ ЧЩЧПДЙФШ ЛПД
		ЙНРЕТБФЙЧОПК РТПЗТБННЩ Ч РПЪЙГЙА, ПВПЪОБЮЕООХА $\blacksquare$.}.
			%DONE: ЧУФБЧЙФШ Ч ЛБЦДЩК item йНЕОБ БМЗПТЙФНПЧ
	\item ч РТПФЙЧОПН УМХЮБЕ ЧЩРПМОСЕФУС:
		\begin{enumerate}
			\item рПУФТПЕОЙЕ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq^\vartriangle$, УППФЧЕФУФЧХАЭЕК	ГЕРПЮЛЕ $\Scl$ (УН.~ТБЪДЕМЩ~\ref{sec:EQ-building}\--\ref{sec:EqB}, БМЗПТЙФН~\EqB).
			\item бОБМЙЪ УЙУФЕНЩ \ignore{ХТБЧОЕОЙК }$\Seq^\vartriangle$ (УН.~ТБЪДЕМ~\ref{sec:EQ-analysis}, БМЗПТЙФН \EqA), РПУФТПЕОЙЕ Ч ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ
				МЙОЕКОПК РПУМЕДПЧБФЕМШОПУФЙ РТПЧЕТПЛ ХУМПЧЙК ОБ ДМЙОЩ:
				\begin{itemize}
					\item РТПЧЕТЛЙ ТБЧЕОУФЧБ ДМЙО
						(УН.~ТБЪДЕМ~\ref{sec:ChkEq}, БМЗПТЙФН~\ChkEq);
					\item РТПЧЕТЛЙ ПЗТБОЙЮЕОЙК Й ЛТБФОПУФЙ 
					  ДМС ДМЙО ОПЧЩИ ЦЕУФЛЙИ РЕТЕНЕООЩИ
						(УН.~ТБЪДЕМ~\ref{sec:ChkHard}, 
						БМЗПТЙФН \ChkHard);
					\item РТПЧЕТЛЙ ОЕТБЧЕОУФЧ ДМС ЗТБОЙГ ДМЙО
						(УН. ТБЪДЕМЩ~\ref{sec:ChkBnd} Й \ref{sec:VMinMax},
						БМЗПТЙФН~\ChkBnd{}). % Й БМЗПТЙФН~\VMinMax{}).
				\end{itemize}
			\item бОБМЙЪ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$ (УН.~ТБЪДЕМ~\ref{sec:CL-analysis},
			  БМЗПТЙФН~\ClA), РПУФТПЕОЙЕ ЖТБЗНЕОФБ ЛПДБ
				ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ЙЪНЕОЕОЙЕ УПУФПСОЙС ЛПНРЙМСФПТБ:
				\begin{quote}
					$(\Scl, \Old, \Fail) \rightarrow (\Scl', \Old', \Fail')~.$
				\end{quote}
			\item тЕЛХТУЙЧОЩК ЧЩЪПЧ БМЗПТЙФНБ \CSC{} ДМС ОПЧПЗП УПУФПСОЙС.
		\end{enumerate}
\end{algo}

\subsection{уЙУФЕНБ ХТБЧОЕОЙК, УППФЧЕФУФЧХАЭБС ГЕРПЮЛЕ РЕТЕУФТПЕЛ}
\label{sec:EQ-building}

\emph{уЙУФЕНБ ХТБЧОЕОЙК ОБ ДМЙОЩ РЕТЕНЕООЩИ} \--- ЬФП ОЕХРПТСДПЮЕООЩК ОБВПТ
$\Seq = \langle \Eq_1, \ldots, \Eq_n \rangle$, ЬМЕНЕОФЩ ЛПФПТПЗП ОБЪЩЧБАФУС
\emph{ХТБЧОЕОЙСНЙ ОБ ДМЙОЩ РЕТЕНЕООЩИ} Й ЙНЕАФ УМЕДХАЭЙК ЧЙД:
\begin{quote}
\begin{tabular}{rll}
	$\Eq$     & $\is$ & $\Sigma_L = \Sigma_R$\\
	$\Sigma$ & $\is$ & $c_1 I_1 + \cdots + c_k I_k$\\
	$I$      & $\is$ & $1 \mid A \mid X$
\end{tabular}
\end{quote}
ЗДЕ 
	$c \in \mathbb{Z}$ \--- ГЕМПЕ ЮЙУМП, 
	$A$ \--- ЛПОУФТХЛГЙС ЙНРЕТБФЙЧОПЗП СЪЩЛБ, ТЕДХГЙТХЕНБС ЧП ЧТЕНС ЙУРПМОЕОЙС Л
		ОЕПФТЙГБФЕМШОПНХ ГЕМПНХ ЮЙУМХ,
	$X$ \--- РЕТЕНЕООБС.

уЙУФЕНХ ХТБЧОЕОЙК ОБ ДМЙОЩ РЕТЕНЕООЩИ $\Seq$ НПЦОП ТБУУНБФТЙЧБФШ ЛБЛ ПВЩЮОХА
БМЗЕВТБЙЮЕУЛХА УЙУФЕНХ ХТБЧОЕОЙК ПФОПУЙФЕМШОП ГЕМПЮЙУМЕООЩИ РЕТЕНЕООЩИ $X_j$,
ЗДЕ ЧЩТБЦЕОЙС $A_j$ СЧМСАФУС РБТБНЕФТБНЙ.  чП ЧТЕНС ЧЩРПМОЕОЙС РТПЗТБННЩ ЬФЙ
РБТБНЕФТЩ ($A_j$) РПМХЮБАФ ЛПОЛТЕФОЩЕ ЪОБЮЕОЙС, Й ФПЗДБ НПЦОП ЗПЧПТЙФШ П ТЕЫЕОЙЙ
УЙУФЕНЩ.

\emph{тЕЫЕОЙЕН УЙУФЕНЩ ХТБЧОЕОЙК} $\Seq$, РТЙ ЪБДБООЩИ ЪОБЮЕОЙСИ РБТБНЕФТПЧ
$A_j$, ОБЪЩЧБЕФУС НОПЦЕУФЧП
%ОЕХРПТСДПЮЕООПЕ НОПЦЕУФЧП
%\Delta = 
$\{\delta_1,\ldots,\delta_m\}$ ЧУЕИ ФБЛЙИ РПДУФБОПЧПЛ
$\delta_i = \{X_j \to n_{ij} \mid X_j \mbox{ \--- РЕТЕНЕООБС ЙЪ } \Seq\}$,\; ${n_{ij} \in \mathbb{Z}}$,\; ${n_{ij} \geq 0}$,
РТЙ ЛПФПТЩИ ЛБЦДПЕ ХТБЧОЕОЙЕ $\Eq_k$ ЙЪ $\Seq$ ПВТБЭБЕФУС Ч ЧЕТОПЕ ТБЧЕОУФЧП, ФП
ЕУФШ ДМС МАВЩИ $k,\,i$, УМЕДХАЭЙК ЙНРЕТБФЙЧОЩК ЛПД ЧЩЮЙУМЙФУС Ч \Verb|true|:
%\begin{quote}
	\(\Sigma_L^k/{\delta_i}=\Sigma_R^k/{\delta_i}\)
%\end{quote}

дЧЕ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$ Й $\Seq'$ ОБЪЩЧБАФУС
\emph{ЬЛЧЙЧБМЕОФОЩНЙ}, ЕУМЙ РТЙ МАВЩИ \ignore{ДПРХУФЙНЩИ}ЪОБЮЕОЙСИ РБТБНЕФТПЧ
$A_j$ ЙИ ТЕЫЕОЙС УПЧРБДБАФ.

вХДЕН ЗПЧПТЙФШ, ЮФП УЙУФЕНБ ХТБЧОЕОЙК $\Seq$ \emph{УППФЧЕФУФЧХЕФ ГЕРПЮЛЕ
РЕТЕУФТПЕЛ} $\Scl$, ЕУМЙ ПОБ ЬЛЧЙЧБМЕОФОБ УЙУФЕНЕ $\Seq^\vartriangle$, ЛПФПТБС
УФТПЙФУС ЙЪ $\Scl$ БМЗПТЙФНПН \EqB.

\subsection{\EqB: БМЗПТЙФН РПУФТПЕОЙС УЙУФЕНЩ ХТБЧОЕОЙК $\Seq^\vartriangle$%
% ОБ ДМЙОЩ
}
\label{sec:EqB}
бМЗПТЙФН \EqB{} РП ЪБДБООПК ГЕРПЮЛЕ РЕТЕУФТПЕЛ РПТПЦДБЕФ УЙУФЕНХ
$\Seq^\vartriangle$ ХТБЧОЕОЙК ОБ ДМЙОЩ РП УМЕДХАЭЙН РТБЧЙМБН:
\begin{itemize}
	\item ЙЪ ЛБЦДПК РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ РПМХЮБЕФУС ПДОП ХТБЧОЕОЙЕ
		${\Sigma_L = \Sigma_R}$, РТЙЮЕН $\Sigma_L$ УФТПЙФУС Ч ТЕЪХМШФБФЕ БОБМЙЪБ ЧЕТИОЕЗП ХТПЧОС
		ЧЩТБЦЕОЙС $\Pe_L$, Б $\Sigma_R$ \--- Ч ТЕЪХМШФБФЕ БОБМЙЪБ ЧЕТИОЕЗП ХТПЧОС ЧЩТБЦЕОЙС $\Pe_R$;
  \item ПВЯЕЛФОЩК УЙНЧПМ $\Os$ ЪБНЕОСЕФУС ОБ 1;
  \item ЧЩТБЦЕОЙЕ Ч УЛПВЛБИ $(\Pe)$ ЪБНЕОСЕФУС ОБ 1;
  \item УФБТБС РЕТЕНЕООБС $V_j$ ЪБНЕОСЕФУС ОБ $A_j=|V_j|$;
	\item ОПЧБС РЕТЕНЕООБС $V_j[m,m]$ ЪБНЕОСЕФУС ОБ $m$;
  \item ОПЧБС РЕТЕНЕООБС $V_j[m,n]$, ЗДЕ $m \ne n$, ЪБНЕОСЕФУС ОБ $X_j$ 
  (Ч ЬФПН УМХЮБЕ, ФБЛ ЦЕ НЩ ВХДЕН ЙУРПМШЪПЧБФШ ДМС $X_j$ 
  ПВПЪОБЮЕОЙЕ $X_j[m,n]$).
\end{itemize}

рТЙНЕТ РПУФТПЕОЙС УЙУФЕНЩ ХТБЧОЕОЙК ОБ ДМЙОЩ РП ЪБДБООПК ГЕРПЮЛЕ РЕТЕУФТПЕЛ
РТЙЧЕДЕО Ч ТБЪДЕМЕ~\ref{sec:IntroExampleSystem}.

оБУ ВХДХФ ЙОФЕТЕУПЧБФШ ФПМШЛП ФБЛЙЕ РПДУФБОПЧЛЙ $\{X_j \to k_j\}$ $(k \in \mathbb{Z})$, ТЕЫБАЭЙЕ УЙУФЕНХ ХТБЧОЕОЙК ОБ ДМЙОЩ, ЮФП ДМС ЧУСЛПК РЕТЕНЕООПК $X_j$, УППФЧЕФУФЧХАЭЕК ТЕЖБМ\-/РЕТЕНЕООПК $V_j[m,n]$, ЧЩРПМОЕОП: $m \leq k_j \leq n$.  рПЬФПНХ НЩ ЧЕЪДЕ ДБМЕЕ ВХДЕН ЗПЧПТЙФШ, ЮФП УЙУФЕНБ ХТБЧОЕОЙК ОБ ДМЙОЩ \emph{УПЧНЕУФОБ}, ЕУМЙ НОПЦЕУФЧП РПДУФБОПЧПЛ, ПВМБДБАЭЙИ ХЛБЪБООЩН УЧПКУФЧПН, ОЕ РХУФП.  йОБЮЕ, НЩ ВХДЕН ОБЪЧБФШ УЙУФЕНХ \emph{ОЕУПЧНЕУФОПК}.

\subsection{пУОПЧОЩЕ УЧПКУФЧБ УЙУФЕН ХТБЧОЕОЙК, УППФЧЕФУФЧХАЭЙИ
ГЕРПЮЛБН РЕТЕУФТПЕЛ}
еУМЙ УЙУФЕНБ ХТБЧОЕОЙК $\Seq$ УППФЧЕФУФЧХЕФ ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$, ФП
ЧЕТОЩ УМЕДХАЭЙЕ ХФЧЕТЦДЕОЙС.

\begin{prop}
\label{prop:sysII}
		лБЦДПК ОПЧПК РЕТЕНЕООПК $V[m,n]$, ${m \ne n}$, ЙЪ ГЕРПЮЛЙ $\Scl$
		УППФЧЕФУФЧХЕФ ТПЧОП ПДОБ РЕТЕНЕООБС $X$ УЙУФЕНЩ $\Seq$.
\end{prop}
%\begin{proof}
		дЕКУФЧЙФЕМШОП, ЬФП ЧЕТОП РП РПУФТПЕОЙА ДМС УЙУФЕНЩ
		$\Seq^\vartriangle$, Б УМЕДПЧБФЕМШОП, Й ДМС ЧУЕИ ЬЛЧЙЧБМЕОФОЩИ ЕК УЙУФЕН.
%\end{proof}

%IGNORE: ТБУУНПФТЕФШ ЧБТЙБОФ У \sigma_0 -- ПЪОБЮЙЧБОЙЕ РБТБНЕФТПЧ.
\begin{thm}
\label{thm:sys}
		рХУФШ $[\sigma_1,\ldots,\sigma_n]$ \--- ТЕЫЕОЙЕ ГЕРПЮЛЙ $\Scl$ РТЙ
		ЖЙЛУЙТПЧБООЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ,
		%\par
		%рХУФШ 
		$\Delta = \{\delta_1,\ldots,\delta_n\}$ \--- НОПЦЕУФЧП
		РПДУФБОПЧПЛ $\delta_i = \{X_j \to \left|V_j[m,n]/{\sigma_i}\right|\}$, ЗДЕ
		$j$ РТПВЕЗБЕФ ЙОДЕЛУЩ ОПЧЩИ РЕТЕНЕООЩИ ЙЪ ГЕРПЮЛЙ $\Scl$, ДМС ЛПФПТЩИ
		$m \ne n$.
		
		фПЗДБ, $\Delta$ СЧМСЕФУС РПДНОПЦЕУФЧПН ТЕЫЕОЙС УЙУФЕНЩ
		$\Seq$ РТЙ УППФЧЕФУФЧХАЭЙИ ЪОБЮЕОЙСИ РБТБНЕФТПЧ.  рТЙ ЬФПН, ДМС ЧУЕИ
		$\delta_i$ Й ЧУЕИ $X_j[m,n]$ ЧЩРПМОЕОП $n \leq X_j/\delta_i \leq  m$.
\end{thm}

		ъБНЕФЙН, ЮФП ДМС
		МАВПК ЙЪ РПДУФБОПЧПЛ $\delta_i$,
		ДМС МАВПЗП ХТБЧОЕОЙС $\Sigma_L^j=\Sigma_R^j$ УЙУФЕНЩ $\Seq^\vartriangle$,
		$\Sigma_L^j/{\delta_i}$
		ТЕДХГЙТХЕФУС Л ДМЙОЕ $\Pe_L^j/{\sigma_i}$, Б $\Sigma_R^j/{\delta_i}$
		ТЕДХГЙТХЕФУС Л ДМЙОЕ $\Pe_R^j/{\sigma_i}$.  оП $\Pe_L^j/{\sigma_i}$
		УПЧРБДБЕФ У $\Pe_R^j/{\sigma_i}$, ФБЛ ЛБЛ РПДУФБОПЧЛБ $\sigma_i$
		РТЙОБДМЕЦЙФ ТЕЫЕОЙА ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$.
		фЕН УБНЩН, ФЕПТЕНБ ЧЕТОБ ДМС УЙУФЕНЩ $\Seq^\vartriangle$. лБЛ УМЕДУФЧЙЕ,
		ФЕПТЕНБ ЧЕТОБ Й ДМС ЧУЕИ
		ЬЛЧЙЧБМЕОФОЩИ ЕК УЙУФЕН ХТБЧОЕОЙК.

фЕПТЕНБ~\ref{thm:sys} РПЪЧПМСЕФ ХФЧЕТЦДБФШ, ЮФП Ч ЛБЮЕУФЧЕ РПФЕОГЙБМШОЩИ ТЕЫЕОЙК
ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$ ЙНЕЕФ УНЩУМ ТБУУНБФТЙЧБФШ ФПМШЛП ФБЛЙЕ РПДУФБОПЧЛЙ
$\{V_j \to \Oe_j\}$, ЮФП ДМЙОЩ ЧЩТБЦЕОЙК $\Oe_j$ ХДПЧМЕФЧПТСАФ УЙУФЕНЕ ХТБЧОЕОЙК
$\Seq$, УППФЧЕФУФЧХАЭЕК ГЕРПЮЛЕ $\Scl$.

\subsection{\EqA: БМЗПТЙФН БОБМЙЪБ УЙУФЕНЩ ХТБЧОЕОЙК ОБ ДМЙОЩ}
\label{sec:EqA}
\label{sec:EQ-analysis}

бОБМЙЪ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$, УППФЧЕФУФЧХАЭЕК ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$,
РТПЙЪЧПДЙФУС У ГЕМША ЧЩРЙУЩЧБОЙС ХУМПЧЙК ОБ РБТБНЕФТЩ $A$ Й РЕТЕНЕООЩЕ $X$,
ЧЩРПМОЕОЙЕ ЛПФПТЩИ \emph{ОЕПВИПДЙНП}, ЮФПВЩ УЙУФЕНa $\Seq$ ВЩМБ УПЧНЕУФОПК.
уППФЧЕФУФЧЕООП, ЕУМЙ ЛБЛЙЕ-МЙВП ЙЪ ЬФЙИ ХУМПЧЙК ОЕ ЧЩРПМОЕОЩ, ФП УЙУФЕНБ
$\Seq$ ВХДЕФ ОЕУПЧНЕУФОПК, Й, Ч УЙМХ ФЕПТЕНЩ~\ref{thm:sys}, ОЕ ВХДЕФ 
РПДУФБОПЧПЛ, ТЕЫБАЭЙИ ГЕРПЮЛХ $\Scl$.

оЕРПУТЕДУФЧЕООП ЙЪ ПРТЕДЕМЕОЙС ЬЛЧЙЧБМЕОФОЩИ УЙУФЕН УМЕДХЕФ, ЮФП ЧУЕ ПВЩЮОЩЕ
БМЗЕВТБЙЮЕУЛЙЕ РТЕПВТБЪПЧБОЙС УЙУФЕН ХТБЧОЕОЙК, ЛПФПТЩЕ ЧЕДХФ Л ЬЛЧЙЧБМЕОФОЩН Ч
БМЗЕВТБЙЮЕУЛПН УНЩУМЕ УЙУФЕНБН, ВХДХФ ЧЕУФЙ Л ЬЛЧЙЧБМЕОФОЩН УЙУФЕНБН Й Ч ОБЫЕН
УМХЮБЕ.  ч ЮБУФОПУФЙ, ХНОПЦЕОЙЕ ПВЕЙИ ЮБУФЕК ХТБЧОЕОЙС ОБ ЮЙУМП, РЕТЕОПУ ЮМЕОПЧ
ХТБЧОЕОЙС Ч ДТХЗХА ЮБУФШ (УП УНЕОПК ЪОБЛБ) Й РПДУФБОПЧЛБ РЕТЕНЕООПК, ЧЩТБЦЕООПК
ЙЪ ЛБЛПЗП-МЙВП ХТБЧОЕОЙС, Ч ДТХЗЙЕ ХТБЧОЕОЙС УЙУФЕНЩ ОЕ ЧМЙСАФ ОБ УППФЧЕФУФЧЙЕ
УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$ ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$.

%\subsubsection{уИЕНБ БМЗПТЙФНБ \EqA}
% ъБЛПННЕОФЙТПЧБМ, ФБЛ ЛБЛ ДТХЗЙИ \subsubsection Ч \subsection ОЕФХ

бМЗПТЙФН \EqA{} РТЙОЙНБЕФ ОБ ЧИПД УМЕДХАЭЙЕ РБТБНЕФТЩ (ОБЮБМШОПЕ УПУФПСОЙЕ БМЗПТЙФНБ):
\[(\Seq, \Scl, \Fail)~,\]
ЗДЕ $\Scl$ Й $\Fail$ СЧМСАФУС РБТБНЕФТБНЙ ЛПНРЙМСФПТБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ
(УН.~ТБЪДЕМ~\ref{sec:comp-params}), Б $\Seq$ \--- УЙУФЕНБ ХТБЧОЕОЙК,
УППФЧЕФУФЧХАЭБС ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$ (УН.~ТБЪДЕМ~\ref{sec:EqB}, 
БМЗПТЙФН~\EqB).

ч ТЕЪХМШФБФЕ ТБВПФЩ БМЗПТЙФНБ $\EqA$ ЗЕОЕТЙТХЕФУС ЖТБЗНЕОФ ЛПДБ РТПЗТБННЩ ОБ
ЙНРЕТБФЙЧОПН СЪЩЛЕ, Б ФБЛЦЕ УМЕДХАЭЙЕ ЧЩИПДОЩЕ РБТБНЕФТЩ:
\[(\Hard, \Amin, \Amax)~,\]
ЗДЕ
\begin{itemize}
	\item $\Hard$ \--- УРЙУПЛ РЕТЕНЕООЩИ ЙЪ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$, ДМЙОБ ЛПФПТЩИ ВХДЕФ
		ЙЪЧЕУФОБ РПУМЕ ЙУРПМОЕОЙС ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ, УЗЕОЕТЙТПЧБООПЗП Л
		НПНЕОФХ ПЛПОЮБОЙС ТБВПФЩ БМЗПТЙФНБ;
	\item $\Amin, \Amax$ \--- ЧЩТБЦЕОЙС ЙНРЕТБФЙЧОПЗП СЪЩЛБ, ТЕДХГЙТХЕНЩЕ ЧП ЧТЕНС
		ЙУРПМОЕОЙС УППФЧЕФУФЧЕООП Л НЙОЙНБМШОПНХ Й НБЛУЙНБМШОПНХ ЧПЪНПЦОЩН
		ЪОБЮЕОЙСН ДМЙОЩ РЕТЕНЕООПК, СЧМСАЭЕКУС ЛБОДЙДБФПН ОБ НЕУФП ФЕЛХЭЕК
		ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК.
\end{itemize}

%DONE: ЗМПВБМШОП--ЗДЕ НПЦОП ХВТБФШ ЙОДЕЛУЩ.
бМЗПТЙФН \EqA{} НПЦОП РТЕДУФБЧЙФШ Ч ЧЙДЕ (МЙОЕКОПК) РПУМЕДПЧБФЕМШОПУФЙ УМЕДХАЭЙИ ЫБЗПЧ:
\begin{algo}
	\item хРТПЭЕОЙЕ УЙУФЕНЩ $\Seq$ РХФЕН РТЙЧЕДЕОЙС РПДПВОЩИ ЮМЕОПЧ Ч
		ЕЕ ХТБЧОЕОЙСИ (УН.~ТБЪДЕМ~\ref{sec:EQ-normalize}, БМЗПТЙФН~\EqN{}).
	\item рПУФТПЕОЙЕ ХРПТСДПЮЕООЩИ ОЕРЕТЕУЕЛБАЭЙИУС ЗТХРР ХТБЧОЕОЙК $G_0, G_1,\ldots,G_k$
	ПВМБДБАЭЙИ УМЕДХАЭЙНЙ УЧПКУФЧБНЙ (УН.~ТБЪДЕМ~\ref{sec:EQ-make-groups}, 
	БМЗПТЙФН~\EqG{}):
		\begin{itemize}
			\item УЙУФЕНБ $\Seq' = G_0 \cup G_1 \cup \cdots \cup G_k$
			ЬЛЧЙЧБМЕОФОБ УЙУФЕНЕ $\Seq$;
			\item ЛБЦДПЕ ХТБЧОЕОЙЕ ЙЪ $G_0$ ОЕ
				УПДЕТЦЙФ РЕТЕНЕООЩИ $X$;
			\item ЛБЦДПЕ ХТБЧОЕОЙЕ ЙЪ $G_p$ (ЗДЕ $p>0$) ЙНЕЕФ ЧЙД
				$c \cdot X = \Sigma$, ЗДЕ $\Sigma$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ ЙЪ МЕЧЩИ
				ЮБУФЕК ХТБЧОЕОЙК ЗТХРРЩ $G_p$, Й $c \ne 0$;
			\item НОПЦЕУФЧП РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч ОЕЛПФПТХА ЗТХРРХ, ОЕ РЕТЕУЕЛБЕФУС
				У НОПЦЕУФЧПН РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч МАВХА ДТХЗХА ЗТХРРХ.
%			\item еУМЙ ХТБЧОЕОЙЕ $c \cdot X = \Sigma$ РТЙОБДМЕЦЙФ ЗТХРРЕ
%			$G$ Й ОЕ СЧМСЕФУС РЕТЧЩН ХТБЧОЕОЙЕН ЬФПК ЗТХРРЩ, ФП РП ЛТБКОЕК
%			НЕТЕ ПДОП ЙЪ РТЕДЫЕУФЧХАЭЙИ ХТБЧОЕОЙК ЗТХРРЩ УПДЕТЦЙФ РЕТЕНЕООХА $X$.
%			\item еУМЙ ХТБЧОЕОЙЕ $c \cdot X = \Sigma$ РТЙОБДМЕЦЙФ ЗТХРРЕ 
%			$G$, ФП ОЙЛБЛПЕ ЙЪ РПУМЕДХАЭЙИ ХТБЧОЕОЙК ЬФПК ЗТХРРЩ ОЕ
%			УПДЕТЦЙФ РЕТЕНЕООХА $X$.
		\end{itemize}
		фБЛЙН ПВТБЪПН, УЙУФЕНБ $\Seq$ ТБЪВЙЧБЕФУС ОБ ОЕРЕТЕУЕЛБАЭЙЕУС РП НОПЦЕУФЧБН
		УПДЕТЦБЭЙИУС РЕТЕНЕООЩИ ЗТХРРЩ ХТБЧОЕОЙК, Й Ч ЛБЦДПК ЙЪ ФБЛЙИ ЗТХРР ОЕЛПФПТЩК
		ОБВПТ РЕТЕНЕООЩИ ЧЩТБЦБЕФУС ЮЕТЕЪ РБТБНЕФТЩ Й ПУФБМШОЩЕ РЕТЕНЕООЩЕ, ЛПФПТЩЕ
		НЩ ВХДЕН ОБЪЩЧБФШ \emph{УЧПВПДОЩНЙ} РЕТЕНЕООЩНЙ.
		\par
		ч ЛБЦДПК ЗТХРРЕ $G_p$ (ЗДЕ $p>0$) РЕТЕНЕООХА $X$ ЙЪ РЕТЧПЗП ХТБЧОЕОЙС
		$c \cdot X = \Sigma$ ФБЛПЗП, ЮФП $\Sigma$ УПДЕТЦЙФ РЕТЕНЕООЩЕ, ВХДЕН ОБЪЩЧБФШ
		\emph{ЧЕДХЭЕК} РЕТЕНЕООПК ЗТХРРЩ $G_p$.
	\item \label{lst:EQ-hard}
		жПТНЙТПЧБОЙЕ УРЙУЛБ $\Hard$ РЕТЕНЕООЩИ ЙЪ ГЕРПЮЛЙ $\Scl$,
		ДМЙОБ ЛПФПТЩИ НПЦЕФ ВЩФШ ЧЩЮЙУМЕОБ РПУМЕ ЙУРПМОЕОЙС ЛПДБ ЙНРЕТБФЙЧОПК
		РТПЗТБННЩ, УЗЕОЕТЙТПЧБООПЗП Л НПНЕОФХ ПЛПОЮБОЙС ТБВПФЩ БМЗПТЙФНБ \EqA{} (УН.~ТБЪДЕМ~\ref{sec:var-hard}, БМЗПТЙФН~\THard{}).
	\item \label{lst:EQ-conds}
		бОБМЙЪ УЙУФЕНЩ $\Seq' = G_0 \cup G_1 \cup \cdots \cup G_k$ Й РПУФТПЕОЙЕ Ч
		ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ МЙОЕКОПК РПУМЕДПЧБФЕМШОПУФЙ УМЕДХАЭЙИ РТПЧЕТПЛ:
		\begin{enumerate}
			\item ДМС ЛБЦДПЗП ХТБЧОЕОЙС $\Eq$ ЙЪ ЗТХРРЩ $G_0$ ЧЩРЙУЩЧБЕФУС РТПЧЕТЛБ
				ХУМПЧЙС, ЛПФПТПЕ $\Eq$ ОБЛМБДЩЧБЕФ ОБ РБТБНЕФТЩ $A$
				(УН.~ТБЪДЕМ~\ref{sec:cond-eq}, БМЗПТЙФН~\ChkEq);
			\item ДМС ЛБЦДПЗП ХТБЧОЕОЙС $c \cdot X[m,n] = \Sigma$ УЙУФЕНЩ
				$\Seq'$, ЗДЕ $\Sigma$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ, ЧЩРЙУЩЧБАФУС
				РТПЧЕТЛЙ ДЕМЙНПУФЙ $\Sigma$ ОБ $c$ ОБГЕМП Й ОЕТБЧЕОУФЧ
				${c \cdot m \leq \Sigma \leq c \cdot n}$
        (УН.~ТБЪДЕМ~\ref{sec:ChkHard}, БМЗПТЙФН~\ChkHard);
			\item ДМС ЛБЦДПК УЧПВПДОПК РЕТЕНЕООПК ЛБЦДПК ЗТХРРЩ $G_p$, $p>0$,
				ЧЩРЙУЩЧБЕФУС\footnote{
					рТЙ ЗТБНПФОПК ТЕБМЙЪБГЙЙ БМЗПТЙФНБ РТПЧЕТЛЙ ПЗТБОЙЮЕОЙК ОБ УЧПВПДОЩЕ
					РЕТЕНЕООЩЕ ДПМЦОЩ ЧЩРЙУЩЧБФШУС ФПМШЛП Ч ФПН УМХЮБЕ, ЛПЗДБ ОЕФ
					<<ДЕЫЕЧПЗП>> УРПУПВБ ЬФЙ ПЗТБОЙЮЕОЙС ХМХЮЫЙФШ.  оБРТЙНЕТ, ЕУМЙ,
					ЙУИПДС ЙЪ УПУФБЧМЕООПЗП УРЙУЛБ $\Hard$, СУОП, ЮФП НПЦОП (ОЕ ЙУРПМШЪХС
					ЛПОЛБФЕОБГЙК ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК) УПУФБЧЙФШ ОПЧХА РЕТЕУФТПКЛХ ЙЪ
					УПДЕТЦЙНПЗП УЛПВПЛ, ЧИПДСЭЙИ Ч ПДОХ ЙЪ УФБТЩИ РЕТЕУФТПЕЛ
					(УН.~ТБЪДЕМ~\ref{sec:ClA}, ЫБЗ~\ref{lst:CL-deref} БМЗПТЙФНБ \ClA), Й
					ЬФБ ОПЧБС РЕТЕУФТПКЛБ ВХДЕФ УПДЕТЦБФШ РЕТЕНЕООЩЕ ЙЪ ЗТХРРЩ $G_p$, ФП
					ЧЩРЙУЩЧБОЙЕ ХУМПЧЙК ОБ УЧПВПДОЩЕ РЕТЕНЕООЩЕ ЙЪ ЗТХРРЩ $G_p$ МХЮЫЕ
					ПФМПЦЙФШ ДП УМЕДХАЭЙИ ЧЩЪПЧПЧ БМЗПТЙФНБ \EqA.
				}
				РТПЧЕТЛБ ХУМПЧЙС,
				ОЕПВИПДЙНПЗП, ЮФПВЩ НОПЦЕУФЧП ЧПЪНПЦОЩИ ЪОБЮЕОЙК ЬФПК РЕТЕНЕООПК ВЩМП
				ОЕ РХУФП (УН.~ТБЪДЕМ~\ref{sec:cond-min-max}, БМЗПТЙФН~\ChkBnd).
		\end{enumerate}
		чЩЧПД ОЕЛПФПТПК РТПЧЕТЛЙ Ч ЛПД ЙНРЕТБФЙЧОПК РТПЗТБННЩ ВМПЛЙТХЕФУС, ЕУМЙ ЬФБ
		РТПЧЕТЛБ ВЩМБ РПУФТПЕОБ БМЗПТЙФНПН~\EqA{} ТБОЕЕ.
	\item \label{lst:EQ-Min-Max}
		рПЙУЛ Ч ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$ РЕТЧПК (УМЕЧБ) РЕТЕНЕООПК $V$, ОЕ
		УПДЕТЦБЭЕКУС Ч УРЙУЛЕ $\Hard$.
		\par
		еУМЙ Ч ТЕЪХМШФБФЕ РПУМЕДХАЭЕЗП БОБМЙЪБ
		ГЕРПЮЛЙ $\Scl$ (ТБЪДЕМ~\ref{sec:CL-analysis}) Ч ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ
		ВХДЕФ РПУФТПЕО ГЙЛМ (УН.~ЫБЗ~\ref{lst:CL-cycle} БМЗПТЙФНБ~\ClA),
		ФП ЬФП ВХДЕФ ГЙЛМ ХДМЙОЕОЙС ЙНЕООП РЕТЕНЕООПК $V$, Й ПОБ УФБОЕФ ФЕЛХЭЕК
		ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК.  рТЙ ЬФПН, ДМЙОБ $V$ Ч ГЙЛМЕ ВХДЕФ 
		ЙЪНЕОСФШУС Ч ОЕЛПФПТЩИ РТЕДЕМБИ: ПФ $\Amin$ ДП $\Amax$.
		\par
		нПЦОП РПЛБЪБФШ, ЮФП РЕТЕНЕООБС $X$, УППФЧЕФУФЧХАЭБС РЕТЕНЕООПК $V$,
		СЧМСЕФУС ЧЕДХЭЕК РЕТЕНЕООПК ЗТХРРЩ $G_1$.  пЗТБОЙЮЕОЙС УОЙЪХ Й 
		УЧЕТИХ ($\Amin$ Й $\Amax$) ОБ
		ЧЕДХЭХА РЕТЕНЕООХА $V$ УФТПСФУС РТЙ РПНПЭЙ БМЗПТЙФНБ \VMinMax{}
		(УН.~ТБЪДЕМ~\ref{sec:VMinMax}).
		\par
		еУМЙ ХЛБЪБООПК РЕТЕНЕООПК $V$ ОЕ УХЭЕУФЧХЕФ, ФП РБТБНЕФТЩ $\Amin$ Й $\Amax$
		ОЕ ПРТЕДЕМЕОЩ.
\end{algo}
%DONE: ЪБНЕОЙФШ НОПЗПВХЛЧЕООЩЕ ПВПЪОБЮЕОЙС Ч НБФ.НПДЕ (ОБРТЙНЕТ Max) ОБ ЮФП-ФП...

ч УМЕДХАЭЙИ ТБЪДЕМБИ РПДТПВОП ТБУУНПФТЕОЩ ЧУЕ БМЗПТЙФНЩ, 
ЧЩЪЩЧБЕНЩЕ ЙЪ БМЗПТЙФНБ $\EqA$.

\subsection{\EqN: БМЗПТЙФН РТЙЧЕДЕОЙС РПДПВОЩИ ЮМЕОПЧ}
\label{sec:EqN}
\label{sec:EQ-normalize}

лБЦДПЕ ХТБЧОЕОЙЕ $\Sigma_L = \Sigma_R$ УЙУФЕНЩ $\Seq$ ЪБНЕОСЕФУС ОБ
ХТБЧОЕОЙЕ $\Sigma = 0$, ЗДЕ $\Sigma$ РПМХЮБЕФУС РЕТЕОПУПН ЧУЕИ ЮМЕОПЧ
$\Sigma_R$ Ч МЕЧХА ЮБУФШ (УП ЪОБЛПН НЙОХУ), Й РТЙЧЕДЕОЙЕН РПДПВОЩИ ЮМЕОПЧ.
уМБЗБЕНЩЕ ЧЙДБ $0 \cdot X$ ХДБМСАФУС ЙЪ УХННЩ $\Sigma$.

\subsection{\EqG: БМЗПТЙФН ТБЪВЙЕОЙС УЙУФЕНЩ ОБ ЗТХРРЩ}
\label{sec:EqG}
\label{sec:EQ-make-groups}

бМЗПТЙФН \EqG{} ТБЪВЙЧБЕФ УЙУФЕНХ ХТБЧОЕОЙК $\Seq$ ОБ 
ХРПТСДПЮЕООЩЕ ОЕРЕТЕУЕЛБАЭЙЕУС ЗТХРРЩ ХТБЧОЕОЙК $G_0, G_1,\ldots,G_k$
ПВМБДБАЭЙЕ ОБВПТПН УЧПКУФЧ (УН. ОЙЦЕ),
РПЪЧПМСАЭЙИ ЧЩРЙУБФШ ХУМПЧЙС, ОЕПВИПДЙНЩЕ, ЮФПВЩ УЙУФЕНБ $\Seq$ ВЩМБ
УПЧНЕУФОБ.

уПУФПСОЙЕН (БТЗХНЕОФПН) БМЗПТЙФНБ \EqG{} ТБЪВЙЕОЙС УЙУФЕНЩ ОБ ЗТХРРЩ СЧМСЕФУС ЮЕФЧЕТЛБ $(S, T, G_0, Gs)$, ЗДЕ
\begin{itemize}
	\item $S$ \--- УЙУФЕНБ ХТБЧОЕОЙК, ЙЪОБЮБМШОП ТБЧОБС $\Seq$;
	\item $T$ \--- УРЙУПЛ РЕТЕНЕООЩИ, ЧУФТЕЮБАЭЙИУС Ч ТБУУНПФТЕООЩИ ХТБЧОЕОЙСИ,
		ЙЪОБЮБМШОП РХУФПК: $T=\square$.
	\item $G_0$ \--- ХРПТСДПЮЕООБС ЗТХРРБ ХТБЧОЕОЙК, ЙЪОБЮБМШОП РХУФБС. 
	\item $Gs$ \--- УРЙУПЛ ХРПТСДПЮЕООЩИ ЗТХРР ХТБЧОЕОЙК, ЙЪОБЮБМШОП РХУФПК. 
\end{itemize}

\begin{algo}
	\item \label{lst:EQ-analyze-first}
		рЕТЧПЕ ХТБЧОЕОЙЕ $\Eq$ ЙЪЩНБЕФУС ЙЪ УЙУФЕНЩ $S$ ($S' = S \setminus \Eq$) Й БОБМЙЪЙТХЕФУС.
		\begin{enumerate}
			\item еУМЙ $\Eq$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ $X$, ФП
				ХТБЧОЕОЙЕ $\Eq$ ДПВБЧМСЕФУС Ч ЗТХРРХ $G_0$.
				\par
				чЩРПМОСЕФУС ТЕЛХТУЙЧОЩК ЧЩЪПЧ БМЗПТЙФНБ ДМС РПМХЮЕООПЗП УПУФПСОЙС.
			\item йОБЮЕ ЙЪНЕОСЕФУС УПУФПСОЙЕ БМЗПТЙФНБ:
			  \begin{quote}
            $(S, \square, G_0, Gs) \to (S', [X], G_0, Gs')$,
			  \end{quote}
				ЗДЕ $X$ \--- РЕТЧБС (УМЕЧБ)
				РЕТЕНЕООБС ЙЪ $\Eq$, a $Gs'$ РПМХЮЕО ДПВБЧМЕОЙЕН Л $Gs$ ОПЧПК РХУФПК ЗТХРРЩ.
				%\par
				чЩРПМОСЕФУС РЕТЕИПД Л ЫБЗХ~\ref{lst:EQ-make-group}.
		\end{enumerate}
	\item \label{lst:EQ-make-group}
		дП ФЕИ РПТ, РПЛБ УРЙУПЛ $T$ ОЕ РХУФ, ЧЩРПМОСАФУС УМЕДХАЭЙЕ ДЕКУФЧЙС:
		\begin{enumerate}
			\item йЪ УРЙУЛБ $T$ ЙЪЩНБЕФУС РЕТЧБС РЕТЕНЕООБС $X$:
			  \begin{quote}
			     ${T' = T \setminus X}$.
			  \end{quote}
			\item ч УЙУФЕНЕ $S$ ЙЭЕФУС ХТБЧОЕОЙЕ $\Eq$, УПДЕТЦБЭЕЕ $X$ 
				(Й ЙЪЩНБЕФУС ЙЪ УЙУФЕНЩ: $S' = S \setminus \Eq$).
				\par
				еУМЙ ФБЛПЗП ХТБЧОЕОЙС $\Eq$ Ч УЙУФЕНЕ $S$ ОЕФ, ФП РЕТЕНЕООБС $X$ ВХДЕФ
				\emph{УЧПВПДОПК}.  чЩРПМОСЕФУС
				ЙЪНЕОЕОЙЕ УПУФПСОЙС БМЗПТЙФНБ: $(S, T, G_0, Gs) \to (S, T', G_0, Gs)$, ЪБФЕН
				ТЕЛХТУЙЧОЩК РЕТЕИПД Л ЫБЗХ~\ref{lst:EQ-make-group}.
				\par
				йОБЮЕ РТПДПМЦБЕФУС ЧЩРПМОЕОЙЕ ФЕЛХЭЕЗП ЫБЗБ.
			\item рП ХТБЧОЕОЙА $\Eq$ УФТПЙФУС ХТБЧОЕОЙЕ $\Eq'$, ЙНЕАЭЕЕ ЧЙД
				$c \cdot X = \Sigma$ (ЧУЕ УМБЗБЕНЩЕ, ЛТПНЕ $c \cdot X$,
				РЕТЕОПУСФУС Ч РТБЧХА ЮБУФШ).
				\par
				хТБЧОЕОЙЕ $\Eq'$ ДПВБЧМСЕФУС Ч ЛПОЕГ РПУМЕДОЕК ЗТХРРЩ УРЙУЛБ 
				$Gs$ (ТЕЪХМШФБФ: $Gs'$).
			\item йЪНЕОСЕФУС УПУФПСОЙЕ БМЗПТЙФНБ:
				\[(S,T,G_0,Gs) \to (S'', T'', G_0, Gs''),\]
				ЗДЕ
				\begin{itemize}
					\item $S''$ РПМХЮБЕФУС ЙЪ $S'$ ЪБНЕОПК 
						${d \cdot c \cdot X}$ ОБ $d \cdot \Sigma$ ЧП ЧУЕИ
						ХТБЧОЕОЙСИ (РТЕДЧБТЙФЕМШОП ХНОПЦЕООЩИ ОБ $c$), 
						УПДЕТЦБЭЙИ $X$, Й РТЙЧЕДЕОЙЕН РПДПВОЩИ ЮМЕОПЧ Ч ЬФЙИ ХТБЧОЕОЙСИ.
					\item $T''$ РПМХЮБЕФУС ЙЪ $T'$ ДПВБЧМЕОЙЕН Ч ЛПОЕГ
						УРЙУЛБ ЧУЕИ РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч ЧЩТБЦЕОЙЕ $\Sigma$.
					\item $Gs''$ РПМХЮБЕФУС ЙЪ $Gs'$ ЪБНЕОПК
						${d \cdot c \cdot X}$ ОБ $d \cdot \Sigma$ ЧП ЧУЕИ
						РТБЧЩИ ЮБУФСИ ХТБЧОЕОЙК (РТЕДЧБТЙФЕМШОП ХНОПЦЕООЩИ ОБ $c$)
						РПУМЕДОЕК ЗТХРРЩ УРЙУЛБ $Gs'$, УПДЕТЦБЭЙИ $X$, Й РТЙЧЕДЕОЙЕН
						РПДПВОЩИ ЮМЕОПЧ Ч РТБЧЩИ ЮБУФСИ ЬФЙИ ХТБЧОЕОЙК.
				\end{itemize}
			\item чЩРПМОСЕФУС ТЕЛХТУЙЧОЩК РЕТЕИПД Л ЫБЗХ~\ref{lst:EQ-make-group}.
		\end{enumerate}
	\item еУМЙ УЙУФЕНБ $S$ ОЕ РХУФБ, ФП ЧЩРПМОСЕФУС РЕТЕИПД Л
		ЫБЗХ~\ref{lst:EQ-analyze-first}, ЙОБЮЕ БМЗПТЙФН ЪБЛБОЮЙЧБЕФ ТБВПФХ, ЧЩДБЧБС
		Ч ЛБЮЕУФЧЕ ТЕЪХМШФБФБ УРЙУПЛ ЗТХРР: $G_0, G_1, \ldots, G_k$, ЗДЕ
		$[G_1, \ldots, G_k] = Gs$.
\end{algo}

уЖПТНХМЙТХЕН ЧБЦОЩЕ ДМС ДБМШОЕКЫЕЗП ЙЪМПЦЕОЙС УЧПКУФЧБ РПУФТПЕООПЗП ТБЪВЙЕОЙС
ХТБЧОЕОЙК РП ЗТХРРБН.

% Was {pr}
\begin{prop}
	рХУФШ ЗТХРРЩ $G_0, G_1, \ldots, G_k$ РПМХЮЕОЩ У РПНПЭША БМЗПТЙФНБ \EqG{} ЙЪ
	УЙУФЕНЩ $\Seq$.  фПЗДБ ЧЕТОЩ УМЕДХАЭЙЕ ХФЧЕТЦДЕОЙС.
	\begin{enumerate}
		\item уЙУФЕНБ $\Seq' = G_0 \cup G_1 \cup \cdots \cup G_k$ ЬЛЧЙЧБМЕОФОБ УЙУФЕНЕ
			$\Seq$.
		\item нОПЦЕУФЧП РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч ОЕЛПФПТХА ЗТХРРХ, ОЕ РЕТЕУЕЛБЕФУС
			У НОПЦЕУФЧПН РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч МАВХА ДТХЗХА ЗТХРРХ.
		\item оЙЛБЛБС РЕТЕНЕООБС, ЧИПДСЭБС Ч РТБЧХА ЮБУФШ ($\Sigma$) ЛБЛПЗП-МЙВП
			ХТБЧОЕОЙС $c \cdot X = \Sigma$ (ФП ЕУФШ \emph{УЧПВПДОБС} РЕТЕНЕООБС), ОЕ
			ЧУФТЕЮБЕФУС Ч МЕЧПК ЮБУФЙ ОЙЛБЛПЗП ХТБЧОЕОЙС.
	\end{enumerate}
\end{prop}

\begin{cons}
	оЕЧЩРПМОЕОЙЕ МАВПЗП ЙЪ ТБЧЕОУФЧ ЗТХРРЩ $G_0$, ЙМЙ
	ОЕУПЧНЕУФОПУФШ МАВПК ЙЪ ЗТХРР $G_1, \ldots, G_k$ ЧМЕЮЕФ ОЕУПЧНЕУФОПУФШ
	ЙЪОБЮБМШОПК УЙУФЕНЩ $\Seq$.
\end{cons}

\begin{cons}
	лБЦДБС РПДУФБОПЧЛБ-ТЕЫЕОЙЕ УЙУФЕНЩ $\Seq$ ПДОПЪОБЮОП ЪБДБЕФУС ЪОБЮЕОЙСНЙ
	УЧПВПДОЩИ РЕТЕНЕООЩИ.
\end{cons}

% Was {pr}
\begin{prop}
	\label{pr:concret}
	рХУФШ ГЕРПЮЛБ РЕТЕУФТПЕЛ $\Scl'$ РПМХЮЕОБ ЙЪ ГЕРПЮЛЙ $\Scl$ РХФЕН
	ПЪОБЮЙЧБОЙС\footnote{
		фБЛПЕ ПЪОБЮЙЧБОЙЕ НПЦЕФ РТПЙЪПКФЙ Ч ТЕЪХМШФБФЕ ЧЩРПМОЕОЙС ЛПДБ,
		УЗЕОЕТЙТПЧБООПЗП ОБ ЫБЗБИ~\ref{lst:CL-new-val1}, \ref{lst:CL-compare},
		\ref{lst:CL-new-val2} Й~\ref{lst:CL-cycle} БМЗПТЙФНБ $\ClA$,
		УН.~ТБЪДЕМ~\ref{sec:ClA}.
	}
	ОПЧПК РЕТЕНЕООПК $V$, ЛПФПТПК УППФЧЕФУФЧХЕФ РЕТЕНЕООБС $X$ Ч УЙУФЕНЕ $\Seq$.
	фПЗДБ ТЕЪХМШФБФ РТЙНЕОЕОЙС БМЗПТЙФНБ $\EqG$ Л УЙУФЕНЕ $\Seq'$, УППФЧЕФУФЧХАЭЕК
	ГЕРПЮЛЕ $\Scl'$, ВХДЕФ УПДЕТЦБФШ ЧУЕ ЗТХРРЩ $G_1, \ldots, G_k$, РПУФТПЕООЩЕ РП
	УЙУФЕНЕ $\Seq$, ЛТПНЕ ПДОПК ЗТХРРЩ $G$, Ч ЛПФПТХА ЧИПДЙФ РЕТЕНЕООБС $X$, Б
	РПУФТПЕООБС РП УЙУФЕНЕ $\Seq'$ ЗТХРРБ $G_0'$ ВХДЕФ УПДЕТЦБФШ ЧУЕ ХТБЧОЕОЙС
	ЗТХРРЩ $G_0$.
\end{prop}

зТХРРЩ (Й ХТБЧОЕОЙС, ОЕ УПДЕТЦБЭЙЕ РЕТЕНЕООЩИ), ЧИПДСЭЙЕ Ч $\EqG(\Seq')$ Й ОЕ
ЧИПДСЭЙЕ Ч $\EqG(\Seq)$, НЩ ВХДЕН ОБЪЩЧБФШ \emph{ЛПОЛТЕФЙЪЙТХАЭЙНЙ} (ЗТХРРБНЙ Й
ХТБЧОЕОЙСНЙ) ДМС ЗТХРРЩ $G$.

мЕЗЛП РПЛБЪБФШ, ЮФП ЗТХРРЩ (Й ХТБЧОЕОЙС),
ЛПОЛТЕФЙЪЙТХАЭЙЕ ЗТХРРХ $G$, РПМХЮБАФУС ЙЪ ФЕИ ЦЕ ХТБЧОЕОЙК УЙУФЕНЩ $\Seq$, ЙЪ
ЛПФПТЩИ РПМХЮЕОБ ЗТХРРБ $G$, РПУМЕ ЪБНЕОЩ Ч ОЙИ РЕТЕНЕООПК $X$ УППФЧЕФУФЧХАЭЙН
РБТБНЕФТПН $A$.

% Was {pr}
\begin{prop}
	рХУФШ ГЕРПЮЛБ РЕТЕУФТПЕЛ $\Scl'$ РПМХЮЕОБ ЙЪ ГЕРПЮЛЙ $\Scl$ РХФЕН
	ПФЭЕРМЕОЙС\footnote{
		пФЭЕРМЕОЙЕ ЦЕУФЛЙИ ЮБУФЕК РЕТЕУФТПЕЛ РТПЙУИПДЙФ Ч ТЕЪХМШФБФЕ ЧЩРПМОЕОЙС ЛПДБ,
		УЗЕОЕТЙТПЧБООПЗП ОБ ЫБЗБИ~\ref{lst:CL-deref} Й~\ref{lst:CL-compare} БМЗПТЙФНБ
		$\ClA$, УН.~ТБЪДЕМ~\ref{sec:ClA}.
	}
	ЦЕУФЛПК (Й ОЕ УПДЕТЦБЭЕК ОПЧЩИ РЕТЕНЕООЩИ) ЮБУФЙ ОЕЛПФПТПК РЕТЕУФТПКЛЙ
	${\Oe	: \Pe}$, РТЙЮЕН РЕТЕУФТПКЛБ ОЕ ПЛБЪБМБУШ РПМОПУФША ЧЩЮЙУМЕООПК Ч
	ТЕЪХМШФБФЕ ЬФПК ПРЕТБГЙЙ.

%DONE AO- х НЕОС ОЙЦЕ ВЩМП ОБРЙУБОП "Ч РТПГЕУУЕ РТЙНЕОЕОЙС".  оЕ МХЮЫЕ МЙ ЬФП ВЩМП,
%    ЮЕН УЕКЮБУ?  чЕДШ РПУФТПЕООЩЕ ЗТХРРЩ Х ОБУ ОЕ УЮЙФБАФУС ТЕЪХМШФБФПН ТБВПФЩ EqA.
%DONE SA- С ВПТПМУС У bad-box-ПН... лБЦЕФУС УЕКЮБУ С ЧЕТОХМ 
%     РТЙНЕТОП УФБТЩК ЧБТЙБОФ (ОП ВЕЪ bad-box-Б), РТПЧЕТШФЕ, РПЦБМХКУФБ
  фПЗДБ Ч РТПГЕУУЕ РТЙНЕОЕОЙС БМЗПТЙФНБ \EqA{} Л УЙУФЕНЕ ХТБЧОЕОЙК \EqB$\,(\Scl')$ ВХДХФ
	РПУФТПЕОЩ ТПЧОП ФЕ ЦЕ УБНЩЕ ЗТХРРЩ ХТБЧОЕОЙК, ЮФП Й ДМС УЙУФЕНЩ
	\EqB$\,(\Scl)$.
\end{prop}

ьФП УЧПКУФЧП УМЕДХЕФ ЙЪ ФПЗП ЖБЛФБ, ЮФП РПУМЕ РТЙЧЕДЕОЙС РПДПВОЩИ ЮМЕОПЧ,
УЙУФЕНЩ ВХДХФ РПМОПУФША УПЧРБДБФШ:
\begin{quote}
	${\EqN(\EqB(\Scl')) = \EqN(\EqB(\Scl))}$.
\end{quote}

\subsection{\THard: БМЗПТЙФН РПУФТПЕОЙС УРЙУЛБ РЕТЕНЕООЩИ У ЧЩЮЙУМСЕНЩНЙ ДМЙОБНЙ}
\label{sec:var-hard}

бМЗПТЙФН %\THard{}
ЖПТНЙТХЕФ УРЙУПЛ $\Hard$, ЙУИПДС ЙЪ УМЕДХАЭЕЗП ПРТЕДЕМЕОЙС.

ьМЕНЕОФБНЙ УРЙУЛБ СЧМСАФУС:
\begin{enumerate}
	\item ЧУЕ РЕТЕНЕООЩЕ $V[m,m]$ ЙЪ ГЕРПЮЛЙ $\Scl$;
	\item ЧУЕ РЕТЕНЕООЩЕ $V$ ЙЪ ГЕРПЮЛЙ $\Scl$, ЛПФПТЩН УППФЧЕФУФЧХАФ
		РБТБНЕФТЩ $A$ УЙУФЕНЩ $\Seq$;
	\item ЧУЕ РЕТЕНЕООЩЕ $V$ ЙЪ ГЕРПЮЛЙ $\Scl$, ЛПФПТЩН УППФЧЕФУФЧХАФ РЕТЕНЕООЩЕ
		$X$ УЙУФЕНЩ $\Seq$, ФБЛЙЕ, ЮФП Ч ПДОПК ЙЪ ЗТХРР $G$ РТЙУХФУФЧХЕФ ХТБЧОЕОЙЕ
		$c \cdot X = \Sigma$, ЗДЕ $\Sigma$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ.
\end{enumerate}


\subsection{\ChkEq: БМЗПТЙФН ЗЕОЕТБГЙЙ РТПЧЕТПЛ ОБ ДМЙОЩ УФБТЩИ РЕТЕНЕООЩИ Й
ЦЕУФЛЙИ ЧЩТБЦЕОЙК}
\label{sec:cond-eq}
\label{sec:ChkEq}

ч ЗТХРРЕ $G_0$ ЛБЦДПЕ ХТБЧОЕОЙЕ ${\Sigma = 0}$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ, ПОП ОБЛМБДЩЧБЕФ ХУМПЧЙЕ ОБ РБТБНЕФТЩ.

%лБЦДПЕ ХТБЧОЕОЙЕ ${\Sigma = 0}$ ЙЪ ЗТХРРЩ $G_0$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ, 
%ПОП ОБЛМБДЩЧБЕФ ХУМПЧЙЕ ОБ РБТБНЕФТЩ.

бМЗПТЙФН \ChkEq{} ДМС ЛБЦДПЗП ХТБЧОЕОЙС ЙЪ ЗТХРРЩ $G_0$, ОЕ
ЛПОЛТЕФЙЪЙТХАЭЕЗП ОЙЛБЛХА ЙЪ ТБОЕЕ РПУФТПЕООЩИ ЗТХРР Й ОЕ УПЧРБДБАЭЕЗП ОЙ У
ЛБЛЙН ЙЪ ТБОЕЕ РПУФТПЕООЩИ ХТБЧОЕОЙК, ЗЕОЕТЙТХЕФ УМЕДХАЭЙК ЖТБЗНЕОФ ЛПДБ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ:
\begin{quote}
	\asail{\IF\ $\Sigma \ne 0$ \THEN\ \GOTO\ $L_{fail}$; $\blacksquare$}
\end{quote}

\subsection{\ChkHard: БМЗПТЙФН ЗЕОЕТБГЙЙ РТПЧЕТПЛ ОБ ДМЙОЩ ОПЧЩИ ЦЕУФЛЙИ РЕТЕНЕООЩИ}
\label{sec:ChkHard}

еУМЙ Ч УЙУФЕНЕ ЕУФШ ХТБЧОЕОЙЕ ЧЙДБ ${c \cdot X[m,n] = \Sigma}$, ЗДЕ $\Sigma$ ОЕ
УПДЕТЦЙФ РЕТЕНЕООЩИ, ФП УЙУФЕНБ ВХДЕФ УПЧНЕУФОПК ФПМШЛП РТЙ ФБЛЙИ
ЪОБЮЕОЙСИ РБТБНЕФТПЧ, ЧИПДСЭЙИ Ч ЧЩТБЦЕОЙЕ $\Sigma$, ЮФП $\Sigma$ ДЕМЙФУС
ОБ $c$, Й $c \cdot m \leq \Sigma \leq c \cdot n$.

бМЗПТЙФН \ChkHard{} Ч ЗТХРРБИ $G_p$ ($p>0$) 
ДМС ЛБЦДПЗП ФБЛПЗП ХТБЧОЕОЙС 
${c \cdot X[m,n] = \Sigma}$
(ЙЪ ФЕИ ХТБЧОЕОЙК, ДМС ЛПФПТЩИ ЬФП ОЕ ВЩМП УДЕМБОП ТБОШЫЕ), ЗЕОЕТЙТХЕФ УМЕДХАЭХА 
РТПЧЕТЛХ Ч ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ:
\begin{quote}
	\asail{\IF\ $\Sigma$ \MOD\ $c$ $\ne$ $0$ \THEN\ \GOTO\ $\Fail$; $\blacksquare$}
\end{quote}
дБМЕЕ, ДМС ЛБЦДПЗП ФБЛПЗП ХТБЧОЕОЙС $c \cdot X[m,n] = \Sigma$, ОЕ ЛПОЛТЕФЙЪЙТХАЭЕЗП
ОЙЛБЛХА ЙЪ ТБОЕЕ РПУФТПЕООЩИ ЗТХРР Й ОЕ УПЧРБДБАЭЙИ ОЙ У ПДОПК ЙЪ ОЙИ, 
ЗЕОЕТЙТХЕФУС УМЕДХАЭБС РТПЧЕТЛБ:
\begin{quote}
\asail{\IF\ $\Sigma < c \cdot m$ \OR\ $\Sigma > c \cdot n$ \THEN\ \GOTO\ $\Fail$; $\blacksquare$}
\end{quote}
еУМЙ РЕТЕНЕООБС $X[m,n]$ ОЕ ПЗТБОЙЮЕОБ УЧЕТИХ ($n = \infty$), ФП
РПУМЕДОСС ЮБУФШ РТПЧЕТЛЙ ($\Sigma > c \cdot n$) ПРХУЛБЕФУС.

дМС ЛБЦДПЗП ХТБЧОЕОЙС $c \cdot X = \Sigma$ (ЗДЕ
$\Sigma$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ, $X$ УППФЧЕФУФЧХЕФ ТЕЖБМ\-/РЕТЕНЕООПК $V$), ДМС
ЛПФПТПЗП ЬФП ОЕ ВЩМП УДЕМБОП ТБОШЫЕ, Ч ЛПДЕ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ЗЕОЕТЙТХЕФУС
ХОЙЛБМШОБС ГЕМПЮЙУМЕООБС РЕТЕНЕООБС
$\len_V$ Й ЕЕ ЙОЙГЙБМЙЪБГЙС:
\begin{quote}
	\asail{\INT\ $\len_V = \Sigma / c$; $\blacksquare$}
\end{quote}

фБЛЙН ПВТБЪПН, ДМС ЧУСЛПК ОПЧПК РЕТЕНЕООПК $V$ ЙЪ УРЙУЛБ $\Hard$ ЧЩТБЦЕОЙЕ
$\len_V$ ТЕДХГЙТХЕФУС ЧП ЧТЕНС ЙУРПМОЕОЙС УЗЕОЕТЙТПЧБООПК РТПЗТБННЩ Л
ДМЙОЕ, ЛПФПТХА ПВСЪБОП ЙНЕФШ ЪОБЮЕОЙЕ $V$.

% TeX-hack -- РПДБЧЙМ bad-box ЪБ УЮЕФ "\,"
\subsection{\ChkBnd:\, БМЗПТЙФН\, ЗЕОЕТБГЙЙ\, РТПЧЕТПЛ\, ЗТБОЙЮОЩИ ХУМПЧЙК ОБ ДМЙОЩ ОПЧЩИ РЕТЕНЕООЩИ}
\label{sec:cond-min-max}
\label{sec:ChkBnd}

%лБЦДПЕ ХТБЧОЕОЙЕ ${c \cdot X = \Sigma}$ ЗТХРРЩ $G_p$, ЗДЕ $p>0$ (ЪБ ЙУЛМАЮЕОЙЕН
ч ЗТХРРЕ $G_p$, ЗДЕ $p>0$, ЛБЦДПЕ ХТБЧОЕОЙЕ ${c \cdot X = \Sigma}$ (ЪБ ЙУЛМАЮЕОЙЕН
ФЕИ, Х ЛПФПТЩИ $\Sigma$ ОЕ УПДЕТЦЙФ РЕТЕНЕООЩИ) ЧЩТБЦБЕФ РЕТЕНЕООХА $X$ ЮЕТЕЪ
УЧПВПДОЩЕ РЕТЕНЕООЩЕ.  бМЗПТЙФН \ChkBnd{} ЗЕОЕТЙТХЕФ ОЕПВИПДЙНЩЕ
ХУМПЧЙС, ЛПФПТЩН ДПМЦОЩ ХДПЧМЕФЧПТСФШ ЪОБЮЕОЙС УЧПВПДОЩИ РЕТЕНЕООЩИ, ЮФПВЩ
УЙУФЕНБ ВЩМБ УПЧНЕУФОБ.

дМС ЛБЦДПК УЧПВПДОПК РЕТЕНЕООПК $X_j$, УПДЕТЦБЭЕКУС Ч ХТБЧОЕОЙСИ ЗТХРРЩ $G$,
УМЕДХАЭЙК БМЗПТЙФН РПТПЦДБЕФ ЧЩТБЦЕОЙС ЙНРЕТБФЙЧОПЗП СЪЩЛБ $\Amin_j$ Й
$\Amax_j$, ТЕДХГЙТХЕНЩЕ РПУМЕ ЙУРПМОЕОЙС ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ,
РПУФТПЕООПЗП ОБ ДБООЩК НПНЕОФ, Л ПЗТБОЙЮЕОЙСН ОБ ДМЙОХ РЕТЕНЕООПК $V_j$
УППФЧЕФУФЧЕООП УОЙЪХ Й УЧЕТИХ.

\begin{algo}
	\item йЪ ЗТХРРЩ $G$ ЙЪЩНБЕФУС РПУМЕДОЕЕ ХТБЧОЕОЙЕ $\Eq$ ЧЙДБ
		\begin{quote}
			${c \cdot X[m,n] = \Sigma}$,
		\end{quote}
		ЗДЕ $\Sigma$ УПДЕТЦЙФ РЕТЕНЕООЩЕ,
		ЙЪНЕОСЕФУС УПУФПСОЙЕ БМЗПТЙФНБ: $G \to G\setminus\Eq$.
		% \par
		еУМЙ ФБЛЙИ ХТБЧОЕОЙК Ч ЗТХРРЕ $G$ ОЕФ, ФП БМЗПТЙФН ЪБЛБОЮЙЧБЕФ ТБВПФХ.
	\item дМС ЛБЦДПЗП УМБЗБЕНПЗП ЧЙДБ $d \cdot X_j[k,l]$ ЙЪ $\Sigma$ ЧЩРПМОСЕФУС УМЕДХАЭЕЕ:
		\begin{enumerate}
			\item пРТЕДЕМСЕФУС ЧЩТБЦЕОЙЕ $\Sigma'$:
				\begin{itemize}
					\item $\Sigma' = \Sigma - d \cdot X_j - c \cdot X$, ЕУМЙ $d < 0$;
					\item $\Sigma' = c \cdot X - \Sigma + d \cdot X_j$, ЕУМЙ $d > 0$.
				\end{itemize}
			\item зЕОЕТЙТХЕФУС ОПЧПЕ ЧЩТБЦЕОЙЕ ДМС НЙОЙНХНБ РЕТЕНЕООПК $X_j$:
				$\Amin_j = \Max\l(\Amin_j, \l\lceil\Sigma_\mathit{min}/d\r\rceil\r)$,
				ЗДЕ
				\begin{itemize}
					\item $\Amin_j$ УРТБЧБ ПФ ЪОБЛБ ТБЧЕОУФЧБ \--- ТБОЕЕ РПМХЮЕООПЕ
						ЧЩТБЦЕОЙЕ ДМС НЙОЙНХНБ РЕТЕНЕООПК $X_j$, МЙВП $k$, ЕУМЙ ПОП ЕЭЕ ОЕ
						ВЩМП ПРТЕДЕМЕОП;
					\item ЧЩТБЦЕОЙЕ $\Sigma_\mathit{min}$ РПМХЮБЕФУС ЙЪ $\Sigma'$
						ЪБНЕОПК РЕТЕНЕООЩИ $X_p[s,t]$, ЧИПДСЭЙИ Ч $\Sigma'$ У РПМПЦЙФЕМШОЩНЙ
						ЛПЬЖЖЙГЙЕОФБНЙ, ОБ $\Amin_p$ (МЙВП ОБ $s$, ЕУМЙ $\Amin_p$ ОЕ ПРТЕДЕМЕОП),
						Б РЕТЕНЕООЩИ $X_q[s,t]$, ЧИПДСЭЙИ Ч $\Sigma'$ У ПФТЙГБФЕМШОЩНЙ ЛПЬЖЖЙГЙЕОФБНЙ,
						ОБ $\Amax_q$ (МЙВП ОБ $t$, ЕУМЙ $\Amax_q$ ОЕ ПРТЕДЕМЕОП).
				\end{itemize}
			\item зЕОЕТЙТХЕФУС ОПЧПЕ ЧЩТБЦЕОЙЕ ДМС НБЛУЙНХНБ РЕТЕНЕООПК $X_j$:
				$\Amax_j = \Min\l(\Amax_j, \l\lfloor\Sigma_\mathit{max}/d\r\rfloor\r)$,
				ЗДЕ
				\begin{itemize}
					\item $\Amax_j$ УРТБЧБ ПФ ЪОБЛБ ТБЧЕОУФЧБ \--- ТБОЕЕ РПМХЮЕООПЕ
						ЧЩТБЦЕОЙЕ ДМС НБЛУЙНХНБ РЕТЕНЕООПК $X_j$, МЙВП $l$, ЕУМЙ ПОП ЕЭЕ ОЕ
						ВЩМП ПРТЕДЕМЕОП;
					\item ЧЩТБЦЕОЙЕ $\Sigma_\mathit{max}$ РПМХЮБЕФУС ЙЪ $\Sigma'$
						ЪБНЕОПК РЕТЕНЕООЩИ $X_p[s,t]$, ЧИПДСЭЙИ Ч $\Sigma'$ У РПМПЦЙФЕМШОЩНЙ
						ЛПЬЖЖЙГЙЕОФБНЙ, ОБ $\Amax_p$ (МЙВП ОБ $t$, ЕУМЙ $\Amax_p$ ОЕ ПРТЕДЕМЕОП),
						Б РЕТЕНЕООЩИ $X_q[s,t]$, ЧИПДСЭЙИ Ч $\Sigma'$ У ПФТЙГБФЕМШОЩНЙ ЛПЬЖЖЙГЙЕОФБНЙ,
						ОБ $\Amin_q$ (МЙВП ОБ $s$, ЕУМЙ $\Amin_q$ ОЕ ПРТЕДЕМЕОП).
				\end{itemize}
		\end{enumerate}
	\item уЗЕОЕТЙТПЧБООЩЕ ОПЧЩЕ ЧЩТБЦЕОЙС ДМС НЙОЙНХНПЧ Й НБЛУЙНХНПЧ УЧПВПДОЩИ
		РЕТЕНЕООЩИ ЪБРПНЙОБАФУС ЧНЕУФП ЧЩТБЦЕОЙК, РПМХЮЕООЩИ ТБОЕЕ.  чЩРПМОСЕФУС
		РЕТЕИПД Л ЫБЗХ~1.
\end{algo}

%DONE AO- х НЕОС ВЩМП: "бМЗПТЙФН \ChkBnd{} ЧЩРПМОСЕФ...".  чЩЮЙФЩЧБС УФБФША, РПУМЕ
%    чБЫЙИ РПУМЕДОЙИ ЙЪНЕОЕОЙК, С, ХЧЙДЕЧ ЬФП НЕУФП, УТБЪХ ЦЕ ЪБНЕОЙМ ПВТБФОП ;-).
%    фПМШЛП РПФПН ЪБНЕФЙМ, ЮФП ЬФП, ПЛБЪЩЧБЕФУС, чЩ РПНЕОСМЙ ОБ ФП, ЮФП ЕУФШ.
%    б РПЮЕНХ чБН ЛБЦЕФУС, ЮФП ФБЛ МХЮЫЕ?
%DONE SA- оЕ ВПМЕЕ, ЮЕН ВПТШВБ У bad-box-ПН. нОЕ ЛБЦЕФУС, УЛБЪБОП ЛПТТЕЛФОП
%    Й ВЕЪ bad-box-Б.  с ОЕ НПЗХ УЛБЪБФШ РП ДТХЗПНХ ВЕЪ bad-box-Б, Б чЩ?
ч БМЗПТЙФНЕ \ChkBnd{} ЧЩРПМОСЕФУС ЧЩЫЕРТЙЧЕДЕООБС РПУМЕДПЧБФЕМШОПУФШ ЫБЗПЧ ДМС ЧУЕИ
ЗТХРР $G_p$ (ЗДЕ $p > 0$).  дБМЕЕ, ДМС ЛБЦДПК УЧПВПДОПК РЕТЕНЕООПК $X_j$,
ЧИПДСЭЕК Ч ЗТХРРХ $G_p$ ($p > 0$), ОЕ ЛПОЛТЕФЙЪЙТХАЭХА ОЙЛБЛХА ЙЪ ТБОЕЕ
РПУФТПЕООЩИ ЗТХРР Й ОЕ УПЧРБДБАЭХА ОЙ У ПДОПК ЙЪ ОЙИ, ЗЕОЕТЙТХЕФУС УМЕДХАЭЙК
ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ:
\begin{quote}
	\asail{\IF\ $\Amin_j > \Amax_j$ \THEN\ \GOTO\ $\Fail$; $\blacksquare$}
\end{quote}


\subsection{\VMinMax: БМЗПТЙФН РПУФТПЕОЙС ПЗТБОЙЮЕОЙК ОБ ЧЕДХЭХА РЕТЕНЕООХА ЗТХРРЩ}
\label{sec:VMinMax}

бМЗПТЙФН \VMinMax{} ЗЕОЕТЙТХЕФ ЧЩТБЦЕОЙС $\Amin$ Й $\Amax$ ЙНРЕТБФЙЧОПЗП СЪЩЛБ,
ТЕДХГЙТХЕНЩЕ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ Л ПЗТБОЙЮЕОЙСН УППФЧЕФУФЧЕООП УОЙЪХ
Й УЧЕТИХ ОБ ЪОБЮЕОЙЕ ЧЕДХЭЕК РЕТЕНЕООПК $X$ ЪБДБООПК ЗТХРРЩ $G$.

чЕДХЭБС РЕТЕНЕООБС $X$ ЧИПДЙФ Ч ХТБЧОЕОЙЕ $c \cdot X[m,n] = \Sigma$, ЗДЕ $\Sigma$
УПДЕТЦЙФ ОЕЛПФПТПЕ НОПЦЕУФЧП $\{X_j\}$ УЧПВПДОЩИ РЕТЕНЕООЩИ.  дМС ЛБЦДПК ЙЪ
РЕТЕНЕООЩИ $X_j$ Ч ТЕЪХМШФБФЕ ТБВПФЩ БМЗПТЙФНБ \ChkBnd{}
(УН.~ТБЪДЕМ~\ref{sec:ChkBnd}) РПУФТПЕОЩ ЧЩТБЦЕОЙС ЙНРЕТБФЙЧОПЗП СЪЩЛБ $\Amin_j$ Й
$\Amax_j$, ТЕДХГЙТХЕНЩЕ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ Л ПЗТБОЙЮЕОЙСН
УППФЧЕФУФЧЕООП УОЙЪХ Й УЧЕТИХ ОБ ЪОБЮЕОЙЕ $X_j$.

чЩТБЦЕОЙС $\Amin$ Й $\Amax$ УФТПСФУС УМЕДХАЭЙН ПВТБЪПН:
\begin{itemize}
	\item $\Amin = \Max\l(m, \l\lceil\Sigma_\mathit{min}/c\r\rceil\r)$;
	\item $\Amax = \Min\l(n, \l\lfloor\Sigma_\mathit{max}/c\r\rfloor\r)$;
	\item $\Sigma_\mathit{min}$ РПМХЮБЕФУС ЙЪ $\Sigma$ ЪБНЕОПК ЛБЦДПК РЕТЕНЕООПК
		$X_j$, ЧИПДСЭЕК Ч $\Sigma$ У РПМПЦЙФЕМШОЩН ЛПЬЖЖЙГЙЕОФПН, ОБ $\Amin_j$, Б
		ЛБЦДПК РЕТЕНЕООПК $X_j$, ЧИПДСЭЕК Ч $\Sigma$ У ПФТЙГБФЕМШОЩН ЛПЬЖЖЙГЙЕОФПН,
		ОБ $\Amax_j$.
	\item $\Sigma_\mathit{max}$ РПМХЮБЕФУС ЙЪ $\Sigma$ ЪБНЕОПК ЛБЦДПК РЕТЕНЕООПК
		$X_j$, ЧИПДСЭЕК Ч $\Sigma$ У РПМПЦЙФЕМШОЩН ЛПЬЖЖЙГЙЕОФПН, ОБ $\Amax_j$, Б
		ЛБЦДПК РЕТЕНЕООПК $X_j$, ЧИПДСЭЕК Ч $\Sigma$ У ПФТЙГБФЕМШОЩН ЛПЬЖЖЙГЙЕОФПН,
		ОБ $\Amin_j$.
\end{itemize}

нПЦОП РПЛБЪБФШ, ЮФП ЧЩТБЦЕОЙЕ $\Sigma_\mathit{max}$ ТЕДХГЙТХЕФУС Л ЛПОЕЮОПНХ
(ОЕ ТБЧОПНХ $\infty$) ЪОБЮЕОЙА.  фБЛЙН ПВТБЪПН, НОПЦЕУФЧП ЧПЪНПЦОЩИ ЪОБЮЕОЙК
ЧЕДХЭЕК РЕТЕНЕООПК ЛПОЕЮОП.


\subsection{\ClA: БМЗПТЙФН БОБМЙЪБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ}
\label{sec:CL-analysis}
\label{sec:ClA}

ч ТЕЪХМШФБФЕ БОБМЙЪБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$ УФТПЙФУС ЖТБЗНЕОФ ЛПДБ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ПУХЭЕУФЧМСАЭЙК ОЕЛПФПТЩК ОБВПТ ЙЪ УМЕДХАЭЙИ ЬФБРПЧ
ЧЩЮЙУМЕОЙС ТЕЫЕОЙС ГЕРПЮЛЙ:
\begin{itemize}
	\item РПУФТПЕОЙЕ ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС $\Oe_L$, УППФЧЕФУФЧХАЭЕЗП МЕЧПК ЮБУФЙ
		$\Pe_L$ ОЕЛПФПТПК РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ (УН.~ТБЪДЕМ~\ref{sec:CL-Oe}).
		чЕЪДЕ ДБМЕЕ, Ч УМХЮБЕ, ЕУМЙ УХЭЕУФЧХЕФ ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ\footnote{
			дМС ПРТЕДЕМЕОЙС ФБЛПЗП ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС $\Oe_L$ ЛПНРЙМСФПТ НПЦЕФ
			ИТБОЙФШ ОЕЛХА ДПРПМОЙФЕМШОХА ЙОЖПТНБГЙА П УПЪДБООЩИ ЧЩТБЦЕОЙСИ.  ч МАВПН
			УМХЮБЕ, ЕУМЙ $\Pe_L$ СЧМСЕФУС УФБТПК РЕТЕНЕООПК $V$, ФП ЪОБЮЕОЙЕ $V$ ЧП
			ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ ЛБЛ ТБЪ Й ВХДЕФ ОХЦОЩН ПВЯЕЛФОЩН ЧЩТБЦЕОЙЕН
			$\Oe_L$.
		} $\Oe_L$,
		УППФЧЕФУФЧХАЭЕЕ МЕЧПК ЮБУФЙ $\Pe_L$
		ОЕЛПФПТПК РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$, НЩ ВХДЕН ЗПЧПТЙФШ, ЮФП
		РЕТЕУФТПКЛБ ЙНЕЕФ ЧЙД ${\Oe_L : \Pe_R}$;
	\item ХРТПЭЕОЙЕ РЕТЕУФТПКЛЙ ${\Oe_L : \Pe_1 (\Pe_2) \Pe_3}$, Ч ЛПФПТПК ДМЙОБ ПДОПЗП ЙЪ
		ЧЩТБЦЕОЙК $\Pe_1$ Й $\Pe_3$ НПЦЕФ ВЩФШ ЧЩЮЙУМЕОБ РХФЕН УОСФЙС УЛПВПЛ У
		УППФЧЕФУФЧХАЭЕЗП ФЕТНБ ЧЩТБЦЕОЙС $\Oe_L$ Й УПЪДБОЙС ОПЧПК ЧУРПНПЗБФЕМШОПК
		РЕТЕУФТПКЛЙ (УН.~ТБЪДЕМ~\ref{sec:CL-deref});
	\item УТБЧОЕОЙЕ ОБ ТБЧЕОУФЧП УФБТЩИ РЕТЕНЕООЩИ Й ПВЯЕЛФОЩИ РПДЧЩТБЦЕОЙК,
		ЧУФТЕЮБАЭЙИУС Ч РТБЧПК ЮБУФЙ $\Pe_R$ ОЕЛПФПТПК РЕТЕУФТПКЛЙ ${\Oe_L : \Pe_R}$,
		УППФЧЕФУФЧХАЭЙН РПДЧЩТБЦЕОЙСН ЧЩТБЦЕОЙС $\Oe_L$ (УН.~ТБЪДЕМ~\ref{sec:CL-compare});
	\item ПЪОБЮЙЧБОЙЕ ОПЧЩИ РЕТЕНЕООЩИ, ЧУФТЕЮБАЭЙИУС Ч РТБЧПК ЮБУФЙ $\Pe_R$
		ОЕЛПФПТПК РЕТЕУФТПКЛЙ ${\Oe_L : \Pe_R}$, РХФЕН ЧЪСФЙС УППФЧЕФУФЧХАЭЙИ
		РПДЧЩТБЦЕОЙК ЧЩТБЦЕОЙС $\Oe_L$ (УН.~ТБЪДЕМ~\ref{sec:CL-compare});
	\item ЙФЕТБФЙЧОЩК РПДВПТ ЪОБЮЕОЙС ПДОПК ЙЪ ОПЧЩИ РЕТЕНЕООЩИ (УН.~ТБЪДЕМ~\ref{sec:CL-cycle}).
\end{itemize}

лТПНЕ ФПЗП, ЛБЛ ТЕЪХМШФБФ БОБМЙЪБ, ЙЪНЕОСЕФУС УПУФПСОЙЕ ЛПНРЙМСФПТБ 
\((\Scl, \Old, \Fail)\) (УН.~ТБЪДЕМ~\ref{sec:comp-params}):
\begin{itemize}
	\item ГЕРПЮЛБ РЕТЕУФТПЕЛ $\Scl$ ХРТПЭБЕФУС Ч ТЕЪХМШФБФЕ ДЕКУФЧЙК, ПРЙУБООЩИ
		Ч ТБЪДЕМБИ~\ref{sec:CL-new-vars}\--\ref{sec:CL-cycle};
	\item УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ $\Old$ РПРПМОСЕФУС ЪБ УЮЕФ ПЪОБЮЙЧБОЙС ОПЧЩИ
		РЕТЕНЕООЩИ Й ЪБЧЕДЕОЙС ЧУРПНПЗБФЕМШОЩИ ЧЩТБЦЕОЙК
		(УН. ТБЪДЕМЩ~\ref{sec:CL-Oe}, \ref{sec:CL-new-vars}, 
		\ref{sec:CL-compare} Й~\ref{sec:CL-cycle});
	\item НЕФЛБ $\Fail$, УППФЧЕФУФЧХАЭБС УМЕДХАЭЕК РПРЩФЛЕ ХДМЙОЕОЙС ЪОБЮЕОЙС
		ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК, ЙЪНЕОСЕФУС Ч ТЕЪХМШФБФЕ
		ПВТБЪПЧБОЙС ГЙЛМБ РПДВПТБ ЪОБЮЕОЙС ПДОПК ЙЪ ОПЧЩИ РЕТЕНЕООЩИ, ЛПФПТБС
		УФБОПЧЙФУС ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК (УН.~ТБЪДЕМ~\ref{sec:CL-cycle}).
\end{itemize}

оБ ЧИПД БМЗПТЙФНБ \ClA{} БОБМЙЪБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$, РПНЙНП УПУФПСОЙС ЛПНРЙМСФПТБ
\((\Scl, \Old, \Fail)\), РПДБЕФУС ХРПТСДПЮЕООБС ФТПКЛБ $(\Hard, \Amin, \Amax)$,
РПМХЮЕООБС У РПНПЭША БМЗПТЙФНБ \EqA{} ЙЪ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$,
УППФЧЕФУФЧХАЭЕК ГЕРПЮЛЕ $\Scl$ (УН.~ТБЪДЕМ~\ref{sec:EQ-analysis}):
\begin{itemize}
	\item $\Hard$ \--- УРЙУПЛ РЕТЕНЕООЩИ, ДМЙОБ ЪОБЮЕОЙК ЛПФПТЩИ НПЦЕФ ВЩФШ
		ЧЩЮЙУМЕОБ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ.  еУМЙ ДМЙОБ ОЕЛПФПТПЗП ЧЩТБЦЕОЙС
		$\Pe$ НПЦЕФ ВЩФШ ЧЩЮЙУМЕОБ (ФП ЕУФШ ЬФП ЧЩТБЦЕОЙЕ СЧМСЕФУС ЛПОЛБФЕОБГЙЕК
		ПВЯЕЛФОЩИ УЙНЧПМПЧ $\Os$, ЧЩТБЦЕОЙК Ч УЛПВЛБИ $(\Pe')$ Й РЕТЕНЕООЩИ
		$V$, РТЙОБДМЕЦБЭЙИ УРЙУЛХ $\Hard$), ФП НЩ ВХДЕН ОБЪЩЧБФШ ЕЗП
		\emph{ЦЕУФЛЙН} ЧЩТБЦЕОЙЕН Й ПВПЪОБЮБФШ $\He$;
	\item $\Amin, \Amax$ \--- ЧЩТБЦЕОЙС, ТЕДХГЙТХЕНЩЕ ЧП ЧТЕНС ЙУРПМОЕОЙС Л
		ПЗТБОЙЮЕОЙСН УППФЧЕФУФЧЕООП УОЙЪХ Й УЧЕТИХ ОБ ДМЙОХ РЕТЧПК (УМЕЧБ)
		РЕТЕНЕООПК $V$ ЙЪ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$, ЛПФПТБС ОЕ ЧИПДЙФ Ч УРЙУПЛ
		$\Hard$.  ьФБ РЕТЕНЕООБС УФБОЕФ ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК)
		РЕТЕНЕООПК, ЕУМЙ ВХДЕФ ЧЩРПМОЕОП РПУФТПЕОЙЕ ОПЧПЗП ГЙЛМБ (УН.~ТБЪДЕМ~\ref{sec:CL-cycle}).
\end{itemize}

пВЭБС УИЕНБ ТБВПФЩ БМЗПТЙФНБ \ClA{} НПЦЕФ ВЩФШ РТЕДУФБЧМЕОБ УМЕДХАЭЙН ПВТБЪПН:
\begin{algo}
	\item \label{lst:CL-deref}
		еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ
		\begin{quote}
		   ${\Oe_L : \Pe_1 (\Pe_2)	\Pe_3}$, 
		\end{quote}
		ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ ЙМЙ $\Pe_3$ СЧМСЕФУС
		ЦЕУФЛЙН, ФП ЙЪ УПДЕТЦЙНПЗП УППФЧЕФУФЧХАЭЕЗП УЛПВПЮОПЗП ФЕТНБ ЧЩТБЦЕОЙС
		$\Oe_L$ Й ЧЩТБЦЕОЙС $\Pe_2$ (РПУМЕ ЧЩРЙУЩЧБОЙС ОЕПВИПДЙНЩИ РТПЧЕТПЛ)
		УПУФБЧМСЕФУС ОПЧБС РЕТЕУФТПКЛБ, ЛПФПТБС РПНЕЭБЕФУС Ч ГЕРПЮЛХ $\Scl$
		(УН.~ТБЪДЕМ~\ref{sec:CL-deref}).  йЪНЕОЙЧ ФБЛЙН ПВТБЪПН УПУФПСОЙЕ
		ЛПНРЙМСФПТБ, БМЗПТЙФН \ClA{} ЪБЛБОЮЙЧБЕФ ТБВПФХ.
	\item \label{lst:CL-symbols}
		дМС ЧУЕИ РЕТЕУФТПЕЛ ЧЙДБ ${\Oe_L : \Pe_R}$ ЙЪ ГЕРПЮЛЙ $\Scl$, ДМС ЧУЕИ
		РТЕДУФБЧМЕОЙК ЧЩТБЦЕОЙС $\Pe_R$ Ч ЧЙДЕ ЛПОЛБФЕОБГЙЙ ЧЩТБЦЕОЙК
		${\Pe_1 V \Pe_2}$, ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ Й $\Pe_2$ СЧМСЕФУС
		ЦЕУФЛЙН, Б РЕТЕНЕООБС $V$ СЧМСЕФУС ОПЧПК $s$\=/РЕТЕНЕООПК, ЧЩРПМОСЕФУС
		РПУФТПЕОЙЕ РТПЧЕТЛЙ ФПЗП, ЮФП ФЕТН ЧЩТБЦЕОЙС $\Oe_L$, ОБИПДСЭЙКУС Ч
		РПЪЙГЙЙ, УППФЧЕФУФЧХАЭЕК РПЪЙГЙЙ РЕТЕНЕООПК $V$ Ч ЧЩТБЦЕОЙЙ  $\Pe_R$,
		СЧМСЕФУС УЙНЧПМПН (УН.~ТБЪДЕМ~\ref{sec:CL-symbols}).  рПУФТПЕООБС РТПЧЕТЛБ
		ЧЩЧПДЙФУС Ч ЛПД ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ЕУМЙ ДМС ДБООПЗП ФЕТНБ ЧЩТБЦЕОЙС
		$\Oe_L$ ЬФП ОЕ ВЩМП УДЕМБОП ТБОШЫЕ.
	\item еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ 
		\begin{quote}
	     ${\Pe_L : \Pe_1 (\Pe_2) \Pe_3}$,
		\end{quote}
	  ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ Й $\Pe_3$ СЧМСЕФУС ЦЕУФЛЙН, Б ЧУЕ РЕТЕНЕООЩЕ,
		ЧИПДСЭЙЕ Ч ЧЩТБЦЕОЙЕ $\Pe_L$, СЧМСАФУС УФБТЩНЙ, ФП ЖПТНЙТХЕФУС ПВЯЕЛФОПЕ
		ЧЩТБЦЕОЙЕ $\Oe_L$, УППФЧЕФУФЧХАЭЕЕ ЧЩТБЦЕОЙА $\Pe_L$
		(УН.~ТБЪДЕМ~\ref{sec:CL-Oe}).  рЕТЕУФТПКЛБ РТЙОЙНБЕФ ЧЙД
		${\Oe_L : \Pe_1 (\Pe_2) \Pe_3}$.  чЩРПМОСЕФУС РЕТЕИПД Л ЫБЗХ~\ref{lst:CL-deref}.
	\item \label{lst:CL-new-val1}
		еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ 
		\begin{quote}
	      ${\Pe_L : \Pe_1 (\Pe_2) \Pe_3}$,
		\end{quote}
		ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ Й $\Pe_3$ СЧМСЕФУС ЦЕУФЛЙН, Б ЪОБЮЕОЙС ОПЧЩИ
		РЕТЕНЕООЩИ ЧЩТБЦЕОЙС $\Pe_L$ ПДОПЪОБЮОП ПРТЕДЕМСАФУС, ЙУИПДС ЙЪ ЪОБЮЕОЙК
		УФБТЩИ РЕТЕНЕООЩИ, ФП ЧЩРПМОСЕФУС ПЪОБЮЙЧБОЙЕ ОПЧЩИ РЕТЕНЕООЩИ
		ЧЩТБЦЕОЙС $\Pe_L$ (ЧПЪНПЦОП, ФТЕВХАЭЕЕ РПУФТПЕОЙС ОПЧЩИ ПВЯЕЛФОЩИ
		ЧЩТБЦЕОЙК, УН.~ТБЪДЕМ~\ref{sec:CL-new-vars}).  пЪОБЮЕООЩЕ РЕТЕНЕООЩЕ
		ДПВБЧМСАФУС Ч УРЙУПЛ $\Old$.
		чЩРПМОСЕФУС РЕТЕИПД Л ЫБЗХ~\ref{lst:CL-deref}.
	\item \label{lst:CL-compare}
		еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ ${\Oe_L : \He_1 \Pe_2 \He_3}$,
		ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\He_1$ Й $\He_3$ ОЕ РХУФП, ФП Ч ЛПДЕ ЙНРЕТБФЙЧОПК
		РТПЗТБННЩ УФТПСФУС РТПЧЕТЛЙ ОБ ТБЧЕОУФЧП УФБТЩИ РЕТЕНЕООЩИ Й ПВЯЕЛФОЩИ
		РПДЧЩТБЦЕОЙК ЧЩТБЦЕОЙК $\He_1$ Й $\He_3$ УППФЧЕФУФЧХАЭЙН РПДЧЩТБЦЕОЙСН
		ЧЩТБЦЕОЙС $\Oe_L$.
		оПЧЩЕ РЕТЕНЕООЩЕ, УПДЕТЦБЭЙЕУС Ч ЧЩТБЦЕОЙСИ $\He_1$ Й $\He_3$, РПМХЮБАФ
		ЪОБЮЕОЙС Й ДПВБЧМСАФУС Ч УРЙУПЛ $\Old$.
		йУИПДОБС РЕТЕУФТПКЛБ ЪБНЕОСЕФУС ОБ РЕТЕУФТПКЛХ ${\Oe_L' : \Pe_2}$, ЗДЕ
		$\Oe_L'$ РПМХЮБЕФУС ЙЪ $\Oe_L$ ПФВТБУЩЧБОЙЕН УМЕЧБ Й УРТБЧБ ЧЩТБЦЕОЙК,
		ТБЧОЩИ УППФЧЕФУФЧЕООП $\He_1$ Й $\He_3$ (УН.~ТБЪДЕМ~\ref{sec:CL-compare}).
		чЩРПМОСЕФУС ТЕЛХТУЙЧОЩК РЕТЕИПД Л ЫБЗХ~\ref{lst:CL-compare}.
	\item \label{lst:CL-new-val2}
		еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ ${\Pe_L : \He_1 \Pe_2 \He_3}$,
		ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\He_1$ Й $\He_3$ ОЕ РХУФП, Б ЪОБЮЕОЙС ОПЧЩИ РЕТЕНЕООЩИ
		ЧЩТБЦЕОЙС $\Pe_L$ ПДОПЪОБЮОП ПРТЕДЕМСАФУС, ЙУИПДС ЙЪ ЪОБЮЕОЙК УФБТЩИ РЕТЕНЕООЩИ,
		ФП ЧЩРПМОСЕФУС ПЪОБЮЙЧБОЙЕ ОПЧЩИ РЕТЕНЕООЩИ ЧЩТБЦЕОЙС $\Pe_L$
		(УН.~ТБЪДЕМ~\ref{sec:CL-new-vars}) Й ЖПТНЙТПЧБОЙЕ ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС
		$\Oe_L$, УППФЧЕФУФЧХАЭЕЗП ЧЩТБЦЕОЙА $\Pe_L$ (УН.~ТБЪДЕМ~\ref{sec:CL-Oe}).
		рЕТЕУФТПКЛБ РТЙОЙНБЕФ ЧЙД ${\Oe_L : \He_1 \Pe_2 \He_3}$.  чЩРПМОСЕФУС РЕТЕИПД
		Л ЫБЗХ~\ref{lst:CL-compare}.
	\item \label{lst:CL-catenate}
		еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ${\Pe_L : \Pe_R}$, ЗДЕ ЧУЕ
		РЕТЕНЕООЩЕ, ЧИПДСЭЙЕ Ч ЧЩТБЦЕОЙЕ $\Pe_L$, СЧМСАФУС УФБТЩНЙ, ФП ЖПТНЙТХЕФУС
		ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ $\Oe_L$, УППФЧЕФУФЧХАЭЕЕ ЧЩТБЦЕОЙА $\Pe_L$
		(УН.~ТБЪДЕМ~\ref{sec:CL-Oe}).
		рЕТЕУФТПКЛБ РТЙОЙНБЕФ ЧЙД ${\Oe_L : \Pe_R}$.  чЩРПМОСЕФУС ТЕЛХТУЙЧОЩК РЕТЕИПД
		Л ЫБЗХ~\ref{lst:CL-catenate}.
		% DONE: SA: бОФПО, ФБЛ Й ЕУФШ? РЕТЕИПД Л ЫБЗХ~\ref{lst:CL-catenate}?
	\item \label{lst:CL-cycle}
		еУМЙ ГЕРПЮЛБ $\Scl$ ОЕ РХУФБ, ФП ЧЩРПМОСЕФУС РПУФТПЕОЙЕ 
		% ЖТБЗНЕОФБ ЛПДБ 
		ПРЕТБФПТБ ГЙЛМБ (\FOR) 
		Ч ЙНРЕТБФЙЧОПК РТПЗТБННЕ, УППФЧЕФУФЧХАЭЕЗП ГЙЛМХ РПДВПТБ ЪОБЮЕОЙС РЕТЧПК
		(УМЕЧБ) РЕТЕНЕООПК РЕТЧПК РЕТЕУФТПКЛЙ ГЕРПЮЛЙ
		(УН.~ТБЪДЕМ~\ref{sec:CL-cycle}).  ьФБ РЕТЕНЕООБС ДПВБЧМСЕФУС Ч УРЙУПЛ
		$\Old$, НЕФЛБ $\Fail$ РПМХЮБЕФ ОПЧПЕ ЪОБЮЕОЙЕ.  йЪНЕОЙЧ ФБЛЙН ПВТБЪПН
		УПУФПСОЙЕ ЛПНРЙМСФПТБ, БМЗПТЙФН ЪБЛБОЮЙЧБЕФ ТБВПФХ.
	\item гЕРПЮЛБ РЕТЕУФТПЕЛ $\Scl$ РХУФБ.  бМЗПТЙФН ЪБЛБОЮЙЧБЕФ ТБВПФХ.
\end{algo}
ч УМЕДХАЭЙИ ТБЪДЕМБИ РПДТПВОЕЕ ТБУУНБФТЙЧБАФУС ХРПНСОХФЩЕ ЧЩЫЕ ЖТБЗНЕОФЩ БМЗПТЙФНБ \ClA.

\subsubsection{рПУФТПЕОЙЕ ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС, УППФЧЕФУФЧХАЭЕЗП МЕЧПК
ЮБУФЙ ПДОПК ЙЪ РЕТЕУФТПЕЛ}
\label{sec:CL-Oe}

еУМЙ МЕЧБС ЮБУФШ $\Pe_L$ РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ УПУФПЙФ ФПМШЛП ЙЪ ПВЯЕЛФОЩИ
ЧЩТБЦЕОЙК Й УФБТЩИ РЕТЕНЕООЩИ, ФП НПЦОП РПУФТПЙФШ ОПЧПЕ ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ $\Oe_L$,
УППФЧЕФУФЧХАЭЕЕ ЧЩТБЦЕОЙА $\Pe_L$.

у РПНПЭША УМЕДХАЭЕЗП ТЕЛХТУЙЧОПЗП БМЗПТЙФНБ РП ПВТБЪГПЧПНХ ЧЩТБЦЕОЙА $\Pe$, ОЕ
УПДЕТЦБЭЕНХ ОПЧЩИ РЕТЕНЕООЩИ, ЧЩРЙУЩЧБЕФУС ЧЩТБЦЕОЙЕ $E$ ЙНРЕТБФЙЧОПЗП СЪЩЛБ,
ТЕДХГЙТХЕНПЕ ЧП ЧТЕНС ЙУРПМОЕОЙС РТПЗТБННЩ Л ПВЯЕЛФОПНХ ЧЩТБЦЕОЙА $\Oe$,
ЛПФПТПЕ УППФЧЕФУФЧХЕФ ЧЩТБЦЕОЙА $\Pe$.
\begin{algo}
	\item еУМЙ ЧЩТБЦЕОЙЕ $\Pe$ ЙНЕЕФ ЧЙД ${\Pe_1 \Pe_2}$, УМЕДХЕФ ЧЩРПМОЙФШ
		РПУФТПЕОЙЕ ЧЩТБЦЕОЙК ЙНРЕТБФЙЧОПЗП СЪЩЛБ $E_1$ Й $E_2$ ДМС ЧЩТБЦЕОЙК
		УППФЧЕФУФЧЕООП $\Pe_1$ Й $\Pe_2$, Й ЧЕТОХФШ ЙИ ЛПОЛБФЕОБГЙА:
		\(E_1 \mathop{++} E_2\).
	\item еУМЙ ЧЩТБЦЕОЙЕ $\Pe$ ЙНЕЕФ ЧЙД $(\Pe')$, УМЕДХЕФ ЧЩРПМОЙФШ
		РПУФТПЕОЙЕ ЧЩТБЦЕОЙС ЙНРЕТБФЙЧОПЗП СЪЩЛБ $E'$ ДМС ЧЩТБЦЕОЙС
		$\Pe'$ Й ЧЪСФШ ЕЗП Ч УЛПВЛЙ: \((E^\prime)\).
	\item еУМЙ ЧЩТБЦЕОЙЕ $\Pe$ СЧМСЕФУС ПВЯЕЛФОЩН УЙНЧПМПН ЙМЙ УФБТПК
		РЕТЕНЕООПК, УМЕДХЕФ РТПУФП ЧЕТОХФШ ЧЩТБЦЕОЙЕ \(\Pe\).
\end{algo}

рПУМЕ ФПЗП, ЛБЛ У РПНПЭША ДБООПЗП БМЗПТЙФНБ РПУФТПЕОП ЧЩТБЦЕОЙЕ ЙНРЕТБФЙЧОПЗП
СЪЩЛБ $E_L$, УППФЧЕФУФЧХАЭЕЕ ЧЩТБЦЕОЙА $\Pe_L$, ЗЕОЕТЙТХЕФУС ЖТБЗНЕОФ ЛПДБ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ПВЕУРЕЮЙЧБАЭЙК ЪБЧЕДЕОЙЕ ОПЧПК ЧУРПНПЗБФЕМШОПК
РЕТЕНЕООПК, УМХЦБЭЕК ДМС ПВТБЭЕОЙС Л ПВЯЕЛФОПНХ ЧЩТБЦЕОЙА $\Oe_L$:
\asail{\EXPR\ $V_\diamond = E_L$; $\blacksquare$},
ЗДЕ $V_\diamond$ \--- ОПЧПЕ, ОЕЙУРПМШЪХЕНПЕ ЙНС РЕТЕНЕООПК.

рЕТЕНЕООБС $V_\diamond$ ЪБОПУЙФУС Ч УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ $\Old$.

рЕТЕУФТПКЛБ ${\Pe_L : \Pe_R}$ ЪБНЕОСЕФУС ОБ УМЕДХАЭХА: ${V_\diamond : \Pe_R}$.

\subsubsection{жПТНЙТПЧБОЙЕ ЪОБЮЕОЙК ОПЧЩИ РЕТЕНЕООЩИ, РТЙОБДМЕЦБЭЙИ МЕЧПК
ЮБУФЙ ЛБЛПК-МЙВП РЕТЕУФТПКЛЙ}
\label{sec:CL-new-vars}

рПУФТПЕОЙЕ ПВЯЕЛФОПЗП ЧЩТБЦЕОЙС, УППФЧЕФУФЧХАЭЕЗП МЕЧПК ЮБУФЙ %$\Pe_L$
РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$, ЧПЪНПЦОП МЙЫШ Ч ФПН УМХЮБЕ, ЛПЗДБ ЧЩТБЦЕОЙЕ $\Pe_L$
ОЕ УПДЕТЦЙФ ОПЧЩИ РЕТЕНЕООЩИ.  дБООБС ЮБУФШ БМЗПТЙФНБ УМХЦЙФ ДМС ПФЧЕФБ ОБ
ЧПРТПУ П ФПН, НПЦОП МЙ, ЙУИПДС ЙЪ ФЕЛХЭЕЗП ОБВПТБ УФБТЩИ РЕТЕНЕООЩИ,
УЖПТНЙТПЧБФШ ЪОБЮЕОЙС ЧУЕИ ОПЧЩИ РЕТЕНЕООЩИ ЧЩТБЦЕОЙС $\Pe_L$, Й Ч УМХЮБЕ, ЛПЗДБ
ПФЧЕФ РПМПЦЙФЕМШОЩК, ДМС РПУФТПЕОЙС ЖТБЗНЕОФБ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ,
%ЧЩЮЙУМСАЭЕЗП ЪОБЮЕОЙС ОПЧЩИ РЕТЕНЕООЩИ ЧЩТБЦЕОЙС $\Pe_L$.
% оЕ ПЮЕОШ ЧОСФОП ЙЪМПЦЕО УНЩУМ РПУМЕДОЕЗП РТЕДМПЦЕОЙС... лБЛ ВХДФП ОЕ ИЧБФБЕФ ЕЭЕ ЮЕЗП-ФП!
ЧЩЮЙУМСАЭЕЗП ЬФЙ ЪОБЮЕОЙС.
%AO: фБЛ МХЮЫЕ?

уМЕДХАЭЙК ТЕЛХТУЙЧОЩК БМЗПТЙФН ЗЕОЕТЙТХЕФ ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ,
ПУХЭЕУФЧМСАЭЙК РПУФТПЕОЙЕ ЪОБЮЕОЙС ОПЧПК РЕТЕНЕООПК $V$, Б ФБЛЦЕ ЧУЕИ ПВЯЕЛФОЩИ
ЧЩТБЦЕОЙК Й ЪОБЮЕОЙК ДТХЗЙИ ОПЧЩИ РЕТЕНЕООЩИ, ОЕПВИПДЙНЩИ ДМС ЬФПЗП.
еУМЙ, ЙУИПДС ЙЪ ФЕЛХЭЕЗП ОБВПТБ УФБТЩИ РЕТЕНЕООЩИ $\Old$ Й ЙНЕАЭЙИУС
РЕТЕУФТПЕЛ $\Scl$, ЖПТНЙТПЧБОЙЕ ЪОБЮЕОЙС РЕТЕНЕООПК $V$ ОЕЧПЪНПЦОП, ФП
ТБВПФБ БМЗПТЙФНБ ЪБЛБОЮЙЧБЕФУС ОЕХДБЮЕК.
\begin{algo}
	\item еУМЙ РЕТЕНЕООБС $V$ ОЕ РТЙОБДМЕЦЙФ УРЙУЛХ ЦЕУФЛЙИ РЕТЕНЕООЩИ
		$\Hard$, ФП ТБВПФБ БМЗПТЙФНБ ЪБЛБОЮЙЧБЕФУС ОЕХДБЮЕК.
	\item \label{lst:new-vars:iterate}
		тБУУНБФТЙЧБАФУС \emph{ПДОБ ЪБ ДТХЗПК} ЧУЕ РЕТЕУФТПКЛЙ 
		ЧЙДБ
		\begin{quote}
		   ${\Pe_L : \Pe_1\,\, V\, \Pe_2}$, 
		\end{quote}
		ЗДЕ РП
		ЛТБКОЕК НЕТЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ Й $\Pe_2$ СЧМСЕФУС 
		ЦЕУФЛЙН\footnote{
				оБРПНОЙН, ДМС ЦЕУФЛЙИ ЧЩТБЦЕОЙК $\He$ ЮЕТЕЪ $|\He|$ 
		ПВПЪОБЮБАФ ЧЩТБЦЕОЙЕ ЙНРЕТБФЙЧОПЗП СЪЩЛБ, ЛПФПТПЕ ЧП ЧТЕНС 
		ЙУРПМОЕОЙС РТПЗТБННЩ ТЕДХГЙТХЕФУС Л ЪОБЮЕОЙА ДМЙОЩ $\He$.
		лПНРЙМСФПТ УФТПЙФ ЬФП ЧЩТБЦЕОЙЕ, ПРЙТБСУШ ОБ ФПФ ЖБЛФ, ЮФП ДМС ЧУСЛПК
		ЦЕУФЛПК РЕТЕНЕООПК $V$ ТБОЕЕ ВЩМБ РПУФТПЕОБ ГЕМПЮЙУМЕООБС РЕТЕНЕООБС $\len_V$,
		ЪОБЮЕОЙЕ ЛПФПТПК ТБЧОП ДМЙОЕ, ЛПФПТХА ПВСЪБОП ЙНЕФШ ЪОБЮЕОЙЕ РЕТЕНЕООПК $V$
		(УН.~ТБЪДЕМ~\ref{sec:ChkHard}).
		}.
		\begin{enumerate}
			\item \label{lst:new-vars:create-values}
				еУМЙ ХЦЕ РПУФТПЕОП ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ $\Oe_L$, УППФЧЕФУФЧХАЭЕЕ
				ЧЩТБЦЕОЙА $\Pe_L$, ФП ЗЕОЕТЙТХЕФУС ПДЙО ЙЪ УМЕДХАЭЙИ ЖТБЗНЕОФПЧ
				ЙНРЕТБФЙЧОПЗП ЛПДБ, ПЪОБЮЙЧБАЭЙИ РЕТЕНЕООХА $V$:
				\begin{itemize}
					\item	\asail{$V = \Subexpr{\Oe_L}{|\Pe_1|}{|V|}$; $\blacksquare$},
					  \\ ЕУМЙ $\Pe_1$ СЧМСЕФУС ЦЕУФЛЙН ЧЩТБЦЕОЙЕН;
					\item \asail{$V = \Subexpr{\Oe_L}{|\Oe_L|-|\Pe_2|-|V|}{|V|}$; $\blacksquare$},%
					  \\ ЕУМЙ $\Pe_2$ СЧМСЕФУС ЦЕУФЛЙН ЧЩТБЦЕОЙЕН.
				\end{itemize}
				 рЕТЕНЕООБС $V$ ЪБОПУЙФУС Ч УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ $\Old$.
				 бМЗПТЙФН (ХУРЕЫОП) ЪБЛБОЮЙЧБЕФ ТБВПФХ.
			\item \label{lst:new-vars:create-Oe}
				еУМЙ ЧЩТБЦЕОЙЕ $\Pe_L$ ОЕ УПДЕТЦЙФ ОПЧЩИ РЕТЕНЕООЩИ, ФП ЖПТНЙТХЕФУС
				УППФЧЕФУФЧХАЭЕЕ ЕНХ ПВЯЕЛФОПЕ ЧЩТБЦЕОЙЕ $\Oe_L$
				(УН.~ТБЪДЕМ.~\ref{sec:CL-Oe}), ЪБФЕН ЧЩРПМОСАФУС ЧУЕ ФЕ ЦЕ ДЕКУФЧЙС,
				ЮФП Й Ч РХОЛФЕ~\ref{lst:new-vars:create-values}.
			\item еУМЙ ЧЩТБЦЕОЙЕ $\Pe_L$ УПДЕТЦЙФ ОПЧЩЕ РЕТЕНЕООЩЕ $V_j$, ФП ДМС ЛБЦДПК ЙЪ
				ЬФЙИ РЕТЕНЕООЩИ ЪБРХУЛБЕФУС БМЗПТЙФН ЖПТНЙТПЧБОЙС ЪОБЮЕОЙС.
				\begin{itemize}
					\item еУМЙ ХДБМПУШ УЖПТНЙТПЧБФШ ЪОБЮЕОЙС ЧУЕИ РЕТЕНЕООЩИ $V_j$, ФП
						ДБМЕЕ ЧЩРПМОСАФУС ДЕКУФЧЙС РХОЛФБ~\ref{lst:new-vars:create-Oe}.
					\item еУМЙ ЦЕ ИПФС ВЩ ДМС ПДОПК ЙЪ РЕТЕНЕООЩИ $V_j$ ТБВПФБ БМЗПТЙФНБ
						ЪБЛБОЮЙЧБЕФУС ОЕХДБЮЕК, ФП ЧЕУШ ЙНРЕТБФЙЧОЩК ЛПД, РПУФТПЕООЩК Ч
						РТПГЕУУЕ ЖПТНЙТПЧБОЙС ЪОБЮЕОЙС РЕТЕНЕООПК $V$, ЪБВЩЧБЕФУС.
						рЕТЕНЕООЩЕ, РПМХЮЙЧЫЙЕ ЪОБЮЕОЙС Ч РТПГЕУУЕ ТБВПФЩ БМЗПТЙФНБ, ЧОПЧШ
						ХДБМСАФУС ЙЪ УРЙУЛБ УФБТЩИ РЕТЕНЕООЩИ $\Old$.
						\par
						рПУМЕ ЬФПЗП ЧЩРПМОСАФУС ДЕКУФЧЙС
						ЫБЗБ~\ref{lst:new-vars:iterate} ДМС \emph{УМЕДХАЭЕК} РЕТЕУФТПКЛЙ ЧЙДБ
						${\Pe_L : \Pe_1 V \Pe_2}$, ЗДЕ РП ЛТБКОЕК НЕТЕ ПДОП ЙЪ ЧЩТБЦЕОЙК
						$\Pe_1$ Й $\Pe_2$ СЧМСЕФУС ЦЕУФЛЙН.
				\end{itemize}
		\end{enumerate}
	\item еУМЙ ОЙ ПДОБ ЙЪ ЙНЕАЭЙИУС РЕТЕУФТПЕЛ ЧЙДБ ${\Pe_L : \Pe_1 V \Pe_2}$ ОЕ
		РПЪЧПМЙМБ УЖПТНЙТПЧБФШ ЪОБЮЕОЙЕ РЕТЕНЕООПК $V$, ФП ТБВПФБ БМЗПТЙФНБ
		ЪБЛБОЮЙЧБЕФУС ОЕХДБЮЕК.
\end{algo}
%еУМЙ ЖТБЪБ "`дМС ФПЗП ЮФПВЩ"' УФПЙФ ЧРЕТЕДЙ, ФП РЕТЕД "`ЮФПВЩ"' ЪБРСФБС ОЕ ОХЦОБ. ьФП ЕДЙОЩК ВМПЛ.
%AO: сУОП, УРБУЙВП! ;-)
дМС ФПЗП ЮФПВЩ ЧЩТБЦЕОЙЕ $\Pe_L$ ОЕ УПДЕТЦБМП ОПЧЩИ РЕТЕНЕООЩИ, ДПУФБФПЮОП
ЪБРХУФЙФШ РТЙЧЕДЕООЩК БМЗПТЙФН ДМС ЧУЕИ ОПЧЩИ РЕТЕНЕООЩИ, УПДЕТЦБЭЙИУС Ч
$\Pe_L$.  еУМЙ ДМС ЛБЛПК-ФП ЙЪ ЬФЙИ РЕТЕНЕООЩИ ТБВПФБ БМЗПТЙФНБ ЪБЛПОЮЙФУС
ОЕХДБЮЕК, ФП УЖПТНЙТПЧБФШ ЕЕ ЪОБЮЕОЙЕ, ЙУИПДС ЙЪ ФЕЛХЭЕЗП УПУФПСОЙС
ЛПНРЙМСФПТБ, ОЕЧПЪНПЦОП.  ч ЬФПН УМХЮБЕ УМЕДХЕФ ХДБМЙФШ ЖТБЗНЕОФ ЛПДБ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ, РПМХЮЕООПК ЧП ЧТЕНС ТБВПФЩ БМЗПТЙФНБ, Й ПФНЕОЙФШ
РТПЙЪЧЕДЕООЩЕ ЙЪНЕОЕОЙС УПУФПСОЙС ЛПНРЙМСФПТБ.


\subsubsection{рПУФТПЕОЙЕ ОПЧПК РЕТЕУФТПКЛЙ ЙЪ УПДЕТЦЙНПЗП УЛПВПЛ ПДОПК ЙЪ УФБТЩИ РЕТЕУФТПЕЛ}
\label{sec:CL-deref}

еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ${\Oe_L : \Pe_R}$, Ч ЛПФПТПК $\Pe_R$ ЙНЕЕФ ЧЙД:
\begin{itemize}
	\item $\He_1 (\Pe_2) \Pe_3$, ФП
		\begin{enumerate}
			\item ЗЕОЕТЙТХЕФУС ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ, РТПЧЕТСАЭЙК, ЮФП
				УППФЧЕФУФЧХАЭЙК ФЕТН $\Oe_L$ СЧМСЕФУС ЧЩТБЦЕОЙЕН Ч УЛПВЛБИ\vadjust{\kern 2pt}:
\begin{quote}
\begin{ASAIL}[frame=single]
  \IF\ \SYMB($\Subterm{\Oe_L}{|\He_1|}$)
  \THEN\ \GOTO\ $\Fail$
  $\blacksquare$
\end{ASAIL}
\end{quote}
			\item РЕТЕУФТПКЛБ ЪБНЕОСЕФУС ОБ ФТЙ (ЙДХЭЙЕ Ч ХЛБЪБООПН РПТСДЛЕ):
				\par
				$\Oe_L : \He_1 (\Pe_2) \Pe_3 \quad\rightarrow$
					\hfill $\Subexpr{\Oe_L}{0}{|\He_1|} : \He_1$,\par
					\hfill $*\Subterm{\Oe_L}{|\He_1|} : \Pe_2$,\par
					\hfill $\Subexpr{\Oe_L}{|\He_1|+1}{|\Oe_L|-|\He_1|-1} : \Pe_3$.
		\end{enumerate}
	\item $\Pe_1 (\Pe_2) \He_3$, ФП
		\begin{enumerate}
			\item ЗЕОЕТЙТХЕФУС ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ, РТПЧЕТСАЭЙК, ЮФП
				УППФЧЕФУФЧХАЭЙК ФЕТН $\Oe_L$ СЧМСЕФУС ЧЩТБЦЕОЙЕН Ч УЛПВЛБИ\vadjust{\kern 2pt}:
\begin{quote}
\begin{ASAIL}[frame=single]
  \IF \SYMB($\Subterm{\Oe_L}{|\Oe_L|-|\He_3|-1}$)
  \THEN \GOTO $\Fail$
  $\blacksquare$
\end{ASAIL}
\end{quote}
			\item РЕТЕУФТПКЛБ ЪБНЕОСЕФУС ОБ ФТЙ (ЙДХЭЙЕ Ч ХЛБЪБООПН РПТСДЛЕ):
				\par
				$\Oe_L : \Pe_1 (\Pe_2) \He_3 \hfill \rightarrow$ \hfill
					\hfill ${\Subexpr{\Oe_L}{0}{|\Oe_L|-|\He_3|-1} : \Pe_1}$,\par
					\hfill ${*\Subterm{\Oe_L}{|\Oe_L|-|\He_3|-1} : \Pe_2}$,\par
					\hfill ${\Subexpr{\Oe_L}{|\Oe_L|-|\He_3|}{|\He_3|} : \He_3}$.
		\end{enumerate}
\end{itemize}

ъБНЕФЙН, ЮФП Ч ПВПЙИ УМХЮБСИ ТБЪВЙЕОЙЕ РЕТЕУФТПКЛЙ ОЕ НЕОСЕФ РПТСДПЛ УМЕДПЧБОЙС
ОПЧЩИ РЕТЕНЕООЩИ Ч ГЕРПЮЛЕ $\Scl$.  рПЬФПНХ ФБЛПЕ РТЕПВТБЪПЧБОЙЕ ОЕ НЕОСЕФ
РПТСДПЛ ЧИПЦДЕОЙС РПДУФБОПЧПЛ, ЧЩЮЙУМСЕНЩИ ЗЕОЕТЙТХЕНЩН ЛПДПН, Ч ТЕЫЕОЙЕ
ГЕРПЮЛЙ $\Scl$ (УН.~ФЕПТЕНХ~\ref{thm:order}).

\subsubsection{рПУФТПЕОЙЕ РТПЧЕТПЛ ФПЗП, ЮФП ПВЯЕЛФОЩЕ ФЕТНЩ, УППФЧЕФУФЧХАЭЙЕ
ОПЧЩН $s$\=/РЕТЕНЕООЩН, СЧМСАФУС УЙНЧПМБНЙ}
\label{sec:CL-symbols}

рТЙ ЧЩРПМОЕОЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ, ОЕПВИПДЙНП РТПЧЕТСФШ, ЮФП ОПЧЩН
$s$\=/РЕТЕНЕООЩН РТЙУЧБЙЧБАФУС ФПМШЛП ПВЯЕЛФОЩЕ ФЕТНЩ, СЧМСАЭЙЕУС УЙНЧПМБНЙ.

дМС ЬФПЗП ОБ ЫБЗЕ~\ref{lst:CL-symbols} БМЗПТЙФНБ \ClA{} ДМС ЛБЦДПК ОПЧПК
$s$\=/РЕТЕНЕООПК $V$ ЙЪ РТБЧПК ЮБУФЙ $\Pe_R$ ЛБЦДПК РЕТЕУФТПКЛЙ
${\Oe_L : \Pe_R}$, ДМС ЛБЦДПЗП РТЕДУФБЧМЕОЙС ЧЩТБЦЕОЙС $\Pe_R$ Ч ЧЙДЕ
ЛПОЛБФЕОБГЙЙ ФТЕИ ЧЩТБЦЕОЙК ${\Pe_1 V \Pe_2}$, ЗДЕ ПДОП ЙЪ ЧЩТБЦЕОЙК $\Pe_1$ Й
$\Pe_2$ СЧМСЕФУС ЦЕУФЛЙН, ЧЩРПМОСЕФУС ПДОП ЙЪ УМЕДХАЭЙИ ДЕКУФЧЙК:
\begin{itemize}
	\item ЕУМЙ ЧЩТБЦЕОЙЕ $\Pe_1$ СЧМСЕФУС ЦЕУФЛЙН, ФП ЗЕОЕТЙТХЕФУС
		УМЕДХАЭЙК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ:
		\begin{quote}
			\asail{\IF\ \PARENTH($\Subterm{\Oe_L}{|\Pe_1|}$) \THEN\ \GOTO\ $\Fail$; $\blacksquare$}
		\end{quote}
	\item ЕУМЙ ЧЩТБЦЕОЙЕ $\Pe_2$ СЧМСЕФУС ЦЕУФЛЙН, ФП ЗЕОЕТЙТХЕФУС
		УМЕДХАЭЙК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ\vadjust{\kern 2pt}:
		\begin{quote}
\begin{ASAIL}
  \IF\ \PARENTH($\Subterm{\Oe_L}{|\Oe_L|-|\Pe_2|-1}$)
  \THEN\ \GOTO\ $\Fail$
  $\blacksquare$
\end{ASAIL}
		\end{quote}
\end{itemize}
%
лБЦДБС РТПЧЕТЛБ ЧЩЧПДЙФУС Ч ЛПД ЙНРЕТБФЙЧОПК РТПЗТБННЩ МЙЫШ Ч ФПН УМХЮБЕ, ЕУМЙ
ПОБ ОЕ ВЩМБ РПУФТПЕОБ БМЗПТЙФНПН \ClA{} ТБОЕЕ.

\subsubsection{пФЭЕРМЕОЙЕ ЦЕУФЛЙИ ЧЩТБЦЕОЙК}
\label{sec:CL-compare}

еУМЙ Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ЧЙДБ ${\Oe_L : \He_1 \Pe_2 \He_3}$, ФП
ЙЪЧЕУФОЩЕ ЮБУФЙ ЧЩТБЦЕОЙК $\He_1$ Й $\He_3$ ОЕПВИПДЙНП РТПЧЕТЙФШ ОБ ТБЧЕОУФЧП
УППФЧЕФУФЧХАЭЙН РПДЧЩТБЦЕОЙСН $\Oe_L$.

рТЕЦДЕ ЧУЕЗП, РЕТЕУФТПКЛБ ТБЪВЙЧБЕФУС ОБ ФТЙ ОПЧЩЕ:
\par\noindent
$\Oe_L : \He_1 \Pe_2 \He_3$ \hfill $\rightarrow$ \hfill
	\(
		\left\{
		\begin{array}{l}
			\Subexpr{\Oe_L}{0}{|\He_1|} : \He_1,\\[1pt]
			\Subexpr{\Oe_L}{|\He_1|}{|\Oe_L|-|\He_1|-|\He_3|} : \Pe_2,\\[1pt]
			\Subexpr{\Oe_L}{|\Oe_L|-|\He_1|-|\He_3|}{|\He_3|} : \He_3.
		\end{array}
		\right.
	\)

дБМЕЕ, ОБД РЕТЧПК Й ФТЕФШЕК РПМХЮЕООЩНЙ РЕТЕУФТПКЛБНЙ РППЮЕТЕДОП РТПЙЪЧПДСФУС
УМЕДХАЭЙЕ ДЕКУФЧЙС:

\begin{algo}
	\item \label{lst:CL-compare-begin}
		еУМЙ РЕТЕУФТПКЛБ РХУФБ, ФП БМЗПТЙФН ЪБЛБОЮЙЧБЕФ ТБВПФХ.
	\item йОБЮЕ РЕТЕУФТПКЛБ ЙНЕЕФ ЧЙД ${\Oe : \Pt\,\He}$.
		\begin{itemize}
			\item еУМЙ ПВТБЪГПЧЩК ФЕТН $\Pt$ СЧМСЕФУС ПВЯЕЛФОЩН УЙНЧПМПН ЙМЙ УФБТПК
				РЕТЕНЕООПК, ФП УФТПЙФУС ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ,
				ПУХЭЕУФЧМСАЭЙК УТБЧОЕОЙЕ $\Pt$ c УППФЧЕФУФЧХАЭЙН РПДЧЩТБЦЕОЙЕН $\Oe$:
				\begin{quote}
					\asail{\IF\ $\Pt \ne \Subexpr{\Oe}{0}{|\Pt|}$ \THEN\ \GOTO\ $\Fail$; $\blacksquare$}
				\end{quote}
			\item еУМЙ ЦЕ ПВТБЪГПЧЩК ФЕТН $\Pt$ СЧМСЕФУС ОПЧПК РЕТЕНЕООПК, ФП ПОБ
				РПМХЮБЕФ ЪОБЮЕОЙЕ:
				\begin{quote}
					\asail{$\Pt = \Subexpr{\Oe}{0}{|\Pt|}$; $\blacksquare$}
				\end{quote}
				Й ДПВБЧМСЕФУС Ч УРЙУПЛ УФБТЩИ РЕТЕНЕООЩИ $\Old$.
		\end{itemize}
	\item рЕТЕУФТПКЛБ ЪБНЕОСЕФУС ОБ УМЕДХАЭХА: ${\Subexpr{\Oe}{|\Pt|}{|\He|} : \He}$,
		РПУМЕ ЮЕЗП ЧЩРПМОСЕФУС РЕТЕИПД Л ЫБЗХ~\ref{lst:CL-compare-begin}.
\end{algo}

йУИПДОБС РЕТЕУФТПКЛБ Ч ГЕРПЮЛЕ $\Scl$ ЪБНЕОСЕФУС ОБ ПУФБЧЫХАУС,
ОЕРТПЧЕТЕООХА ЮБУФШ: ${\Subexpr{\Oe_L}{|\He_1|}{|\Oe_L|-|\He_1|-|\He_3|} : \Pe_2}$.

\subsubsection{рПУФТПЕОЙЕ ГЙЛМБ РПДВПТБ ЪОБЮЕОЙС ОПЧПК РЕТЕНЕООПК}
\label{sec:CL-cycle}

йЪ ГЕРПЮЛЙ $\Scl$ ЧЩВЙТБЕФУС РЕТЧБС РЕТЕУФТПКЛБ.
ч ТЕЪХМШФБФЕ ТБВПФЩ ЫБЗБ~\ref{lst:CL-catenate},
ПОБ ЙНЕЕФ ЧЙД ${\Oe_L : \Pe_R}$.

ч ТЕЪХМШФБФЕ ТБВПФЩ ЫБЗБ~\ref{lst:CL-compare},
ЧЩТБЦЕОЙЕ $\Pe_R$ ЙНЕЕФ ЧЙД $V \Pe_R'$, ЗДЕ $V$ \--- ОПЧБС РЕТЕНЕООБС, ОЕ
ЧИПДСЭБС Ч УРЙУПЛ $\Hard$, ЕЕ ДМЙОХ ФТЕВХЕФУС РПДВЙТБФШ.

пЗТБОЙЮЕОЙС ОБ ДМЙОХ $V$ ДБАФ ЧЩТБЦЕОЙС $\Amin$ Й $\Amax$, РПУФТПЕООЩЕ ОБ
ЫБЗЕ~\ref{lst:EQ-Min-Max} БМЗПТЙФНБ \EqA{} БОБМЙЪБ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$,
УППФЧЕФУФЧХАЭЕК ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$ (УН.~ТБЪДЕМ~\ref{sec:EqA}).

зЕОЕТЙТХЕФУС УМЕДХАЭЙК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ:
\begin{quote}
\begin{ASAIL}[frame=single]
  \INT \(\len_V\)
  \FOR ($\len_V = \Amin$; $\len_V \leq \Amax$; $\len_V\mathclose{++}$) \{
    \(V = \subexpr{\Oe_L}{0}{\len_V}\)
    $\blacksquare$
  \(\Next\):
  \}
\end{ASAIL}
\end{quote}
ъДЕУШ $\Next$ \--- ЬФП ОПЧБС НЕФЛБ.
рЕТЕНЕООБС $V$ ЪБОПУЙФУС Ч УРЙУПЛ $\Old$ УФБТЩИ РЕТЕНЕООЩИ, ПОБ УФБОПЧЙФУС
ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК.
нЕФЛБ $\Fail$ РТЙОЙНБЕФ ЪОБЮЕОЙЕ $\Next$.

\section{пВПУОПЧБОЙЕ БМЗПТЙФНБ ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ}

\subsection{лПТТЕЛФОПУФШ}

уМЕДХАЭЙЕ ФЕПТЕНЩ РПЛБЪЩЧБАФ, ЮФП РПУФТПЕООЩК У РПНПЭША БМЗПТЙФНБ \CSC{}
ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ЧЩЮЙУМСЕФ ТЕЫЕОЙЕ ЪБДБООПК ГЕРПЮЛЙ
РЕТЕУФТПЕЛ Ч РПТСДЛЕ УМЕДПЧБОЙС РПДУФБОПЧПЛ УМЕЧБ ОБРТБЧП.

\ignore{
\begin{thm}
	дМС МАВПЗП ОБЮБМШОПЗП УПУФПСОЙС \((\Scl, \Old, \Fail, \Next)\),
	РТЕДМПЦЕООЩК БМЗПТЙФН ЛПНРЙМСГЙЙ ЪБЛПОЮЙФ ТБВПФХ ЪБ ЛПОЕЮОПЕ ЮЙУМП ЫБЗПЧ.
\end{thm}
}

\begin{thm}
	рПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ЧЩЮЙУМСЕФ НОПЦЕУФЧП
	РПДУФБОПЧПЛ $\sigma_i$, ЛБЦДБС ЙЪ ЛПФПТЩИ РТЙОБДМЕЦЙФ ТЕЫЕОЙА ГЕРПЮЛЙ
	$\Scl$.
\end{thm}

% IGNORE: РПЮЕНХ НЩ ЧЩЮЙУМСЕН ЙНЕООП РПДУФБОПЧЛЙ?

рТЕДРПМПЦЙН, ЮФП Ч ТЕЪХМШФБФЕ ТБВПФЩ РПУФТПЕООПК ЙНРЕТБФЙЧОПК РТПЗТБННЩ ВЩМБ
РПМХЮЕОБ РПДУФБОПЧЛБ $\sigma$, ОЕ РТЙОБДМЕЦБЭБС ТЕЫЕОЙА ГЕРПЮЛЙ $\Scl$.

ьФП ЪОБЮЙФ, ЮФП Ч ГЕРПЮЛЕ $\Scl$ ЕУФШ РЕТЕУФТПКЛБ ${\Pe_L : \Pe_R}$, ФБЛБС, ЮФП
$\Pe_L/\sigma$ ОЕ УПЧРБДБЕФ У $\Pe_R/\sigma$.

пДОБЛП ЬФПЗП ОЕ НПЦЕФ ВЩФШ.  уПЧРБДЕОЙЕ ЛБЦДПЗП ФЕТНБ РТБЧПК ЮБУФЙ $\Pe_R$ У
УППФЧЕФУФЧХАЭЙН ФЕТНПН МЕЧПК ЮБУФЙ $\Pe_L$ ЛБЦДПК РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ ЙЪ
ГЕРПЮЛЙ $\Scl$ ПВЕУРЕЮЙЧБЕФУС ОБ ЫБЗЕ~\ref{lst:CL-compare} БМЗПТЙФНБ \ClA{} БОБМЙЪБ
ГЕРПЮЛЙ РЕТЕУФТПЕЛ (УН.~ТБЪДЕМ~\ref{sec:ClA}).


\begin{thm}
	мАВБС РПДУФБОПЧЛБ $\sigma$, РТЙОБДМЕЦБЭБС ТЕЫЕОЙА ГЕРПЮЛЙ $\Scl$, ВХДЕФ
	ЧЩЮЙУМЕОБ РПУФТПЕООЩН ЖТБЗНЕОФПН ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ.
\end{thm}

йЪОБЮБМШОП, МАВБС РПДУФБОПЧЛБ
\[\sigma = \{V_j \to \Oe_j \mid V_j \mbox{ \--- ОПЧБС РЕТЕНЕООБС ГЕРПЮЛЙ } \Scl\}\]
ТБУУНБФТЙЧБЕФУС ЛБЛ РПФЕОГЙБМШОП РТЙОБДМЕЦБЭБС ТЕЫЕОЙА ГЕРПЮЛЙ $\Scl$.

бМЗПТЙФН \EqA{} БОБМЙЪБ УЙУФЕНЩ ХТБЧОЕОЙК $\Seq$, УППФЧЕФУФЧХАЭЕК ГЕРПЮЛЕ $\Scl$,
УФТПЙФ ФПМШЛП ХУМПЧЙС ОБ РПДУФБОПЧЛЙ $\sigma_i$ \emph{ОЕПВИПДЙНЩЕ} ДМС ФПЗП,
ЮФПВЩ $\sigma_i$ РТЙОБДМЕЦБМЙ ТЕЫЕОЙА $\Scl$ (УН.~ФЕПТЕНХ~\ref{thm:sys}
Й~БМЗПТЙФН~\EqA, ТБЪДЕМ~\ref{sec:EqA}).

чУЕ ХУМПЧЙС, ЛПФПТЩЕ УФТПЙФ БМЗПТЙФН \ClA{} БОБМЙЪБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$,
ПРЙТБАФУС ОБ РТСНПЕ УТБЧОЕОЙЕ МЕЧЩИ Й РТБЧЩИ ЮБУФЕК РЕТЕУФТПЕЛ (УН.~ТБЪДЕМ~\ref{sec:ClA}).
уППФЧЕФУФЧЕООП, ЧЩРПМОЕОЙЕ ЬФЙИ ХУМПЧЙК ДМС РПДУФБОПЧЛЙ $\sigma$ ФБЛЦЕ
\emph{ОЕПВИПДЙНП}, ЮФПВЩ $\sigma$ РТЙОБДМЕЦБМБ ТЕЫЕОЙА $\Scl$.

фБЛЙН ПВТБЪПН, РПДУФБОПЧЛБ, РТЙОБДМЕЦБЭБС ТЕЫЕОЙА ГЕРПЮЛЙ $\Scl$, ПВСЪБОБ
ХДПЧМЕФЧПТСФШ ЧУЕН ЧЩРЙУБООЩН ХУМПЧЙСН.  пДОБЛП РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ ПУХЭЕУФЧМСЕФ РПМОЩК РЕТЕВПТ ЧУЕИ РПДУФБОПЧПЛ,
ХДПЧМЕФЧПТСАЭЙИ ЧЩРЙУБООЩН ХУМПЧЙСН.  уМЕДПЧБФЕМШОП, МАВБС РПДУФБОПЧЛБ ЙЪ
ТЕЫЕОЙС ГЕРПЮЛЙ $\Scl$ ВХДЕФ Ч ЛБЛПК-ФП НПНЕОФ ЧЩЮЙУМЕОБ.


\begin{thm}
	\label{thm:order}
	рПДУФБОПЧЛЙ $\sigma_i$ ЧЩЮЙУМСАФУС РПУФТПЕООЩН ЖТБЗНЕОФПН ЛПДБ ЙНРЕТБФЙЧОПК
	РТПЗТБННЩ Ч РПТСДЛЕ УМЕДПЧБОЙС \emph{УМЕЧБ ОБРТБЧП}.
\end{thm}

уЖПТНХМЙТХЕН Й ДПЛБЦЕН ЧУРПНПЗБФЕМШОХА МЕННХ.

\begin{lem}
	еУМЙ ${\Pe_L : \Pe_R}$ \--- РЕТЕУФТПКЛБ ЙЪ ГЕРПЮЛЙ $\Scl$, ФБЛБС, ЮФП ЧЩТБЦЕОЙЕ
	$\Pe_L$ ОЕ УПДЕТЦЙФ ОПЧЩИ РЕТЕНЕООЩИ, Б ДМЙОБ МАВПК ОПЧПК РЕТЕНЕООПК ЧЩТБЦЕОЙС
	$\Pe_R$ ПДОПЪОБЮОП ПРТЕДЕМСЕФУС, ЙУИПДС ЙЪ ФЕЛХЭЙИ ЪОБЮЕОЙК ДМЙО УФБТЩИ
	РЕТЕНЕООЩИ, ФП ТЕЫЕОЙЕ ГЕРПЮЛЙ $\Scl$ ОЕ ЙЪНЕОЙФУС, ЕУМЙ ДБООХА РЕТЕУФТПКЛХ
	${\Pe_L : \Pe_R}$ РЕТЕОЕУФЙ ОБ РЕТЧПЕ НЕУФП ГЕРПЮЛЙ.
\end{lem}

йЪ ХУМПЧЙС МЕННЩ УМЕДХЕФ, ЮФП ЪОБЮЕОЙЕ ЛБЦДПК ОПЧПК РЕТЕНЕООПК ЧЩТБЦЕОЙС $\Pe_R$
ПДОПЪОБЮОП ПРТЕДЕМСЕФУС, ЙУИПДС ЙЪ ФЕЛХЭЙИ ЪОБЮЕОЙК УФБТЩИ РЕТЕНЕООЩИ.

ьФП ЪОБЮЙФ, ЮФП (ОЕХРПТСДПЮЕООПЕ) НОПЦЕУФЧП РПДУФБОПЧПЛ, УПУФБЧМСАЭЙИ ТЕЫЕОЙЕ
ГЕРПЮЛЙ $\Scl$, ОЕ ЙЪНЕОЙФУС РТЙ РЕТЕОПУЕ РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ Ч ОБЮБМП
ГЕРПЮЛЙ.

рТЕДРПМПЦЙН, ЮФП РПНЕОСЕФУС РПТСДПЛ УМЕДПЧБОЙС РПДУФБОПЧПЛ Ч ТЕЫЕОЙЙ.  фП ЕУФШ
УХЭЕУФЧХАФ ДЧЕ ФБЛЙЕ РПДУФБОПЧЛЙ $\sigma_1$ Й $\sigma_2$, ЮФП
${\sigma_1 < \sigma_2}$ Ч ТЕЫЕОЙЙ ГЕРПЮЛЙ $\Scl$, Й ${\sigma_2 < \sigma_1}$ Ч
ТЕЫЕОЙЙ ГЕРПЮЛЙ, РПМХЮЕООПК РЕТЕОПУПН РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ Ч ОБЮБМП.

ъОБЮЙФ, УХЭЕУФЧХАФ ДЧЕ ФБЛЙЕ РЕТЕНЕООЩЕ $V_1$ Й $V_2$, ЮФП:
\begin{itemize}
\item $V_1/\sigma_1 < V_1/\sigma_2$,
\item $V_2/\sigma_1 > V_2/\sigma_2$,
\item $V_1$ ОБИПДЙФУС МЕЧЕЕ, ЮЕН $V_2$ Ч ГЕРПЮЛЕ $\Scl$,
\item $V_1$ ОБИПДЙФУС РТБЧЕЕ, ЮЕН $V_2$ Ч ГЕРПЮЛЕ $\Scl$, У РЕТЕОЕУЕООПК Ч
	ОБЮБМП РЕТЕУФТПКЛПК ${\Pe_L : \Pe_R}$.
\end{itemize}

лБЛ НЩ ЧЙДЙН, РЕТЕНЕООБС $V_2$ ЧИПДЙФ Ч ЧЩТБЦЕОЙЕ $\Pe_R$ \--- ФПМШЛП ФБЛ ПОБ НПЦЕФ
ПЛБЪБФШУС МЕЧЕЕ $V_1$ РПУМЕ РЕТЕОПУБ РЕТЕУФТПКЛЙ.

пДОБЛП, НЩ ХЦЕ ЪОБЕН, ЮФП ЪОБЮЕОЙЕ ЛБЦДПК ОПЧПК РЕТЕНЕООПК $V_j$ ЧЩТБЦЕОЙС $\Pe_R$
ПРТЕДЕМСЕФУС ПДОПЪОБЮОП, ФП ЕУФШ ОЕ НПЦЕФ УХЭЕУФЧПЧБФШ ДЧХИ РПДУФБОПЧПЛ
$\sigma_1$ Й $\sigma_2$, РТЙУЧБЙЧБАЭЙИ ЛБЛПК-МЙВП ЙЪ РЕТЕНЕООЩИ $V_j$ ТБЪОЩЕ
ЪОБЮЕОЙС.

йФБЛ, РПТСДПЛ УМЕДПЧБОЙС РПДУФБОПЧПЛ Ч ТЕЫЕОЙЙ ГЕРПЮЛЙ $\Scl$ ФБЛЦЕ ОЕ
РПНЕОСЕФУС РТЙ РЕТЕОПУЕ РЕТЕУФТПКЛЙ ${\Pe_L : \Pe_R}$ Ч ОБЮБМП ГЕРПЮЛЙ.  мЕННБ
ДПЛБЪБОБ.

рТЙЧЕДЕООБС МЕННБ ХФЧЕТЦДБЕФ, ЮФП ТЕЫЕОЙЕ ГЕРПЮЛЙ РЕТЕУФТПЕЛ ОЕ ЪБЧЙУЙФ ПФ
ФПЗП, Ч ЛБЛПН РПТСДЛЕ ЧЩЮЙУМСАФУС ЪОБЮЕОЙС РЕТЕНЕООЩИ, ЛПФПТЩЕ ПРТЕДЕМСАФУС
РБТБНЕФТБНЙ (УФБТЩНЙ РЕТЕНЕООЩНЙ) ГЕРПЮЛЙ ПДОПЪОБЮОП.

йОЩНЙ УМПЧБНЙ, ЕУМЙ ОЕ НЕОСЕФУС РПТСДПЛ РПДВПТБ ЪОБЮЕОЙК ПФЛТЩФЩИ РЕТЕНЕООЩИ,
ФП ОЕ РПНЕОСЕФУС Й ТЕЫЕОЙЕ ГЕРПЮЛЙ.

ъБНЕФЙН ФЕРЕТШ, ЮФП РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ
ПУХЭЕУФЧМСЕФ РЕТЕВПТ ЪОБЮЕОЙК ПФЛТЩФЩИ РЕТЕНЕООЩИ Ч РПТСДЛЕ
\emph{УМЕЧБ ОБРТБЧП}: ГЙЛМ ЧУЕЗДБ УФТПЙФУС РП УБНПК МЕЧПК ПФЛТЩФПК РЕТЕНЕООПК,
РТЙЮЕН ЕЕ ЪОБЮЕОЙЕ ЙЪНЕОСЕФУС ПФ НЕОШЫЕЗП Л ВПМШЫЕНХ
(УН.~ТБЪДЕМ~\ref{sec:CL-cycle}).

уМЕДПЧБФЕМШОП, РТЕДМПЦЕООЩК БМЗПТЙФН ЛПНРЙМСГЙЙ ДЕКУФЧЙФЕМШОП УФТПЙФ ЖТБЗНЕОФ
ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ, ЧЩЮЙУМСАЭЙК ТЕЫЕОЙЕ ГЕРПЮЛЙ РЕТЕУФТПЕЛ,
УППФЧЕФУФЧХАЭЕЕ УПРПУФБЧМЕОЙА УМЕЧБ ОБРТБЧП.

\subsection{ьЖЖЕЛФЙЧОПУФШ}
\label{sec:efficiency}

рХУФШ ДБОБ ГЕРПЮЛБ РЕТЕУФТПЕЛ 
\[
\Scl=\langle \Pe_L^1 : \Pe_R^1, \ldots, \Pe_L^n : \Pe_R^n \rangle\,,
\]
ФБЛБС, ЮФП ЧЩТБЦЕОЙС $\Pe_R^i$ ОЕ
УПДЕТЦБФ УЛПВПЮОЩИ ФЕТНПЧ\footnote{
	чУЕ ПВУХЦДБЕНЩЕ ФЕПТЕНЩ МЕЗЛП ПВПВЭБАФУС ОБ ГЕРПЮЛЙ РЕТЕУФТПЕЛ МАВПЗП
	ЧЙДБ, ЛПФПТЩЕ МЙВП УЧПДСФУС Л ГЕРПЮЛБН ВЕЪ УЛПВПЛ Ч РТБЧПК ЮБУФЙ, МЙВП Л
	ГЕРПЮЛБН, ЗДЕ УЛПВЛЙ ОЕ ЧМЙСАФ ОБ ЧЩЮЙУМЕОЙЕ ЮБУФЙ ТЕЫЕОЙС, ПФОПУСЭЕКУС Л
	РЕТЕНЕООЩН ЧЕТИОЕЗП ХТПЧОС.
}.
ч ЛБЦДПК ЙЪ РЕТЕУФТПЕЛ УХННБ ДМЙО ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК Й РЕТЕНЕООЩИ ОБ ЧЕТИОЕН
ХТПЧОЕ ЧЩТБЦЕОЙС $\Pe_L^i$, ДПМЦОБ ВЩФШ ТБЧОБ УХННЕ ДМЙО ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК Й
РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч ЧЩТБЦЕОЙЕ $\Pe_R^i$.  ъБЖЙЛУЙТХЕН ЪОБЮЕОЙС УФБТЩИ
РЕТЕНЕООЩИ, ЧИПДСЭЙИ Ч $\Scl$, Й ТБУУНПФТЙН ЬФЙ ТБЧЕОУФЧБ ЛБЛ
УЙУФЕНХ $\Req$ ХТБЧОЕОЙК ПФОПУЙФЕМШОП \emph{ДЕКУФЧЙФЕМШОЩИ} РЕТЕНЕООЩИ $Y$
(Ф.~Е. $Y \in \mathbb{R}$), УППФЧЕФУФЧХАЭЙИ ДМЙОБН ОПЧЩИ РЕТЕНЕООЩИ $V[m,n]$,
ЗДЕ $m \ne n$ (ВХДЕН ПВПЪОБЮБФШ ФБЛЙЕ РЕТЕНЕООЩЕ ЮЕТЕЪ $Y[m,n]$).

\begin{thm}
	рХУФШ ГЕРПЮЛБ $\Scl$ ФБЛПЧБ, ЮФП РТЙ ОЕЛПФПТЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ
	ЧЩРПМОЕОП ПДОП ЙЪ УМЕДХАЭЙИ ХУМПЧЙК:
	\begin{itemize}
		\item УЙУФЕНБ $\Req$ ОЕУПЧНЕУФОБ;
		\item УЙУФЕНБ $\Req$ ЙНЕЕФ ЕДЙОУФЧЕООПЕ ТЕЫЕОЙЕ, ОП ПОП ОЕ ГЕМПЮЙУМЕООП;
		\item УЙУФЕНБ $\Req$ ЙНЕЕФ ЕДЙОУФЧЕООПЕ ТЕЫЕОЙЕ, ЛПФПТПЕ РТЙУЧБЙЧБЕФ
			ОЕЛПФПТПК РЕТЕНЕООПК $Y[m,n]$ ЪОБЮЕОЙЕ, МЕЦБЭЕЕ ЧОЕ ПФТЕЪЛБ (МХЮБ)
			$[m,n]$.
	\end{itemize}
	фПЗДБ РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ПРТЕДЕМЙФ, ЮФП
	РТЙ ДБООЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ
	ГЕРПЮЛБ $\Scl$ ОЕУПЧНЕУФОБ, ОЕ УТБЧОЙЧБС ОБ ТБЧЕОУФЧП ОЙЛБЛЙЕ ПВЯЕЛФОЩЕ
	ЧЩТБЦЕОЙС.
\end{thm}

рХУФШ $[G_0,G_1,\ldots,G_k]$ \--- ЗТХРРЩ ХТБЧОЕОЙК, РПУФТПЕООЩЕ РП ГЕРПЮЛЕ
$\Scl$ У РПНПЭША БМЗПТЙФНПЧ \EqB{} Й \EqG{} (ТБЪДЕМЩ~\ref{sec:EqB} Й 
\ref{sec:EqG}, УППФЧЕФУФЧЕООП).

еУМЙ ЧУЕ ТБЧЕОУФЧБ ЗТХРРЩ $G_0$ ЧЩРПМОЕОЩ, ФП УЙУФЕНБ $\Req$ ВХДЕФ ЙНЕФШ РП
ЛТБКОЕК НЕТЕ ПДОП ТЕЫЕОЙЕ (ДПУФБФПЮОП ЪБЖЙЛУЙТПЧБФШ РТПЙЪЧПМШОЩЕ ЪОБЮЕОЙС
УЧПВПДОЩИ РЕТЕНЕООЩИ Ч ЗТХРРБИ $G_1,\ldots,G_k$).  фБЛЙН ПВТБЪПН, ОЕУПЧНЕУФОПУФШ
УЙУФЕНЩ $\Req$ (Б УМЕДПЧБФЕМШОП, Й ГЕРПЮЛЙ $\Scl$) ВХДЕФ ПРТЕДЕМЕОБ РТЙ
РТПЧЕТЛЕ ЧЩРПМОЕОЙС ТБЧЕОУФЧ ЗТХРРЩ $G_0$ (УН.~БМЗПТЙФН~\ChkEq,
ТБЪДЕМ~\ref{sec:ChkEq}).

еУМЙ ЛБЛБС-ФП ЙЪ ЗТХРР $G_1,\ldots,G_k$ УПДЕТЦЙФ ИПФС ВЩ ПДОХ УЧПВПДОХА
РЕТЕНЕООХА, ФП УЙУФЕНБ $\Req$ МЙВП ОЕУПЧНЕУФОБ, МЙВП ЙНЕЕФ ВПМЕЕ ПДОПЗП ТЕЫЕОЙС
(ДЕКУФЧЙФЕМШОП, ЕУМЙ ЕУФШ ЛБЛПК-ФП ОБВПТ ЪОБЮЕОЙК РЕТЕНЕООЩИ, ХДПЧМЕФЧПТСАЭЙК
УЙУФЕНЕ $\Req$, ФП ЕК ВХДЕФ ХДПЧМЕФЧПТСФШ Й МАВПК ДТХЗПК ОБВПТ ЪОБЮЕОЙК,
ПФМЙЮБАЭЙКУС ПФ РЕТЧПЗП ФПМШЛП ОБ УЧПВПДОЩИ РЕТЕНЕООЩИ ЗТХРР $G_1,\ldots,G_k$).
рПЬФПНХ, ЕУМЙ УЙУФЕНБ $\Req$ ЙНЕЕФ ЕДЙОУФЧЕООПЕ ТЕЫЕОЙЕ, ФП ЕЗП ГЕМПЮЙУМЕООПУФШ
Й ХДПЧМЕФЧПТЕОЙЕ ЗТБОЙЮОЩН ХУМПЧЙСН ВХДХФ РТПЧЕТЕОЩ РТЙ ЧЩРПМОЕОЙЙ ЛПДБ,
РПУФТПЕООПЗП У РПНПЭША БМЗПТЙФНБ \ChkHard{} (ТБЪДЕМ~\ref{sec:ChkHard}).

\begin{thm}
	еУМЙ ГЕРПЮЛБ $\Scl$ ФБЛПЧБ, ЮФП РТЙ ОЕЛПФПТЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ
	УЙУФЕНБ $\Req$ ЙНЕЕФ ЕДЙОУФЧЕООПЕ ТЕЫЕОЙЕ, ЬФП ТЕЫЕОЙЕ ГЕМПЮЙУМЕООП, Й
	ЪОБЮЕОЙЕ ЛБЦДПК РЕТЕНЕООПК $Y[m,n]$ РТЙОБДМЕЦЙФ ПФТЕЪЛХ (МХЮХ) $[m,n]$, ФП
	РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ЧЩЮЙУМЙФ ТЕЫЕОЙЕ ГЕРПЮЛЙ
	$\Scl$ (РТЙ ДБООЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ), УТБЧОЙЧ РТЙ ЬФПН ОЕ ВПМЕЕ,
	ЮЕН $C \cdot \Sigma$ ПВЯЕЛФОЩИ ФЕТНПЧ.  ъДЕУШ $\Sigma$ \--- УХННБ ДМЙО
	ЪОБЮЕОЙК ЧУЕИ УФБТЩИ РЕТЕНЕООЩИ ЙЪ $\Scl$, Б $C$ \--- ЛПОУФБОФБ, ОЕ ЪБЧЙУСЭБС
	ПФ ЪОБЮЕОЙК УФБТЩИ РЕТЕНЕООЩИ ЙЪ $\Scl$.
\end{thm}

рХУФШ $[G_0,G_1,\ldots,G_k]$ \--- ЗТХРРЩ ХТБЧОЕОЙК, РПУФТПЕООЩЕ РП ГЕРПЮЛЕ
$\Scl$ У РПНПЭША БМЗПТЙФНПЧ \EqB{} Й \EqG{} (ТБЪДЕМЩ~\ref{sec:EqB} Й 
\ref{sec:EqG}, УППФЧЕФУФЧЕООП).

фБЛ ЛБЛ УЙУФЕНБ $\Req$ ЙНЕЕФ ЕДЙОУФЧЕООПЕ ТЕЫЕОЙЕ, ФП ОЙ ПДОБ ЙЪ ЬФЙИ ЗТХРР ОЕ
УПДЕТЦЙФ УЧПВПДОЩИ РЕТЕНЕООЩИ.  ьФП ЪОБЮЙФ, ЮФП ЧУЕ РЕТЕНЕООЩЕ ЙЪ ГЕРПЮЛЙ
$\Scl$ РПРБДХФ ОБ ЫБЗЕ~\ref{lst:EQ-hard} БМЗПТЙФНБ \EqA{}
(УН.~ТБЪДЕМ~\ref{sec:EqA}) Ч УРЙУПЛ $\THard$ ЦЕУФЛЙИ РЕТЕНЕООЩИ.
рПЬФПНХ ЧЩЪЧБООЩК ДБМЕЕ БМЗПТЙФН \ClA{} (УН.~ТБЪДЕМ~\ref{sec:ClA}) ЪБЧЕТЫЙФ
ЛПНРЙМСГЙА ГЕРПЮЛЙ РЕТЕУФТПЕЛ $\Scl$, РПУФТПЙЧ ЛПД ДМС УТБЧОЕОЙС ОЕ ВПМЕЕ, ЮЕН
$\Sigma'$ ПВЯЕЛФОЩИ ФЕТНПЧ, ЗДЕ $\Sigma'$ \--- УХННБ ДМЙО ЧЕТИОЙИ ХТПЧОЕК ЧУЕИ
РЕТЕУФТПЕЛ: $\Sigma'=\sum_{i=1}^q|\Pe_L^i|$, ЗДЕ $q$ \--- ЮЙУМП РЕТЕУФТПЕЛ Ч
ГЕРПЮЛЕ $\Scl$.

пУФБМПУШ ЪБНЕФЙФШ, ЮФП ДМЙОЩ ОПЧЩИ ЦЕУФЛЙИ РЕТЕНЕООЩИ ЧЩТБЦБАФУС ЮЕТЕЪ ДМЙОЩ
УФБТЩИ РЕТЕНЕООЩИ У РПНПЭША МЙОЕКОЩИ ХТБЧОЕОЙК.  рПЬФПНХ Й ДМЙОЩ РЕТЕУФТПЕЛ
ЧЩТБЦБАФУС ЮЕТЕЪ ДМЙОЩ УФБТЩИ РЕТЕНЕООЩИ МЙОЕКОП.  б ЬФП ЪОБЮЙФ, ЮФП УХЭЕУФЧХЕФ
ФБЛБС ЛПОУФБОФБ $C$, ЮФП $\Sigma' \leq C \cdot \Sigma$.

\begin{thm}
	рХУФШ ГЕРПЮЛБ $\Scl$ ФБЛПЧБ, ЮФП РТЙ ОЕЛПФПТЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ
	ЧУЕ ТЕЫЕОЙС УЙУФЕНЩ $\Req$ РБТБНЕФТЙЪХАФУС ЪОБЮЕОЙЕН ТПЧОП ПДОПК УЧПВПДОПК
	ОЕЙЪЧЕУФОПК.  фПЗДБ РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ВХДЕФ Ч
	ГЙЛМЕ РПДВЙТБФШ ЪОБЮЕОЙЕ $\Oe$ ОЕЛПФПТПК РЕТЕНЕООПК $V$ ЙЪ $\Scl$, РТЙЮЕН
	ВХДХФ ТБУУНБФТЙЧБФШУС ФПМШЛП ФБЛЙЕ ЪОБЮЕОЙС $\Oe$, ЮФП УЙУФЕНБ $\Req'$,
	УППФЧЕФУФЧХАЭБС (РТЙ ДБООЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ) ГЕРПЮЛЕ
	$\Scl/{\{V\to\Oe\}}$, ВХДЕФ ЙНЕФШ ТЕЫЕОЙЕ, ЛПФПТПЕ ЛБЦДПК РЕТЕНЕООПК $Y[m,n]$
	РТЙУЧБЙЧБЕФ ЪОБЮЕОЙЕ ЙЪ ПФТЕЪЛБ (МХЮБ) $[m,n]$.
\end{thm}

рХУФШ $[G_0,G_1,\ldots,G_k]$ \--- ЗТХРРЩ ХТБЧОЕОЙК, РПУФТПЕООЩЕ РП ГЕРПЮЛЕ
$\Scl$ У РПНПЭША БМЗПТЙФНПЧ \EqB{} Й \EqG{} (ТБЪДЕМЩ~\ref{sec:EqB} Й 
\ref{sec:EqG}, УППФЧЕФУФЧЕООП).

рПУЛПМШЛХ ТЕЫЕОЙС УЙУФЕНЩ $\Req$ РБТБНЕФТЙЪХАФУС ЪОБЮЕОЙЕН ПДОПК УЧПВПДОПК
ОЕЙЪЧЕУФОПК, ФП ПДОБ ЙЪ ЗТХРР $G_p$ ($p>0$) УПДЕТЦЙФ ПДОХ УЧПВПДОХА
РЕТЕНЕООХА $X$.  ъОБЮЕОЙС ЧУЕИ РЕТЕНЕООЩИ ЧП ЧУЕИ ПУФБМШОЩИ ЗТХРРБИ
ПРТЕДЕМСАФУС ПДОПЪОБЮОП.

чУЕ (ЛТПНЕ $X$) РЕТЕНЕООЩЕ $X_j$ ЗТХРРЩ $G_p$ ЧЩТБЦБАФУС ЮЕТЕЪ $X$:
$X_j = \Sigma_j(X)$.  бМЗПТЙФН \ChkBnd{} (ТБЪДЕМ~\ref{sec:ChkBnd}) УФТПЙФ
ФБЛЙЕ ПЗТБОЙЮЕОЙС ОБ ЪОБЮЕОЙЕ $\Oe'$ РЕТЕНЕООПК $X$, ЮФП УППФЧЕФУФЧХАЭЙЕ
ЪОБЮЕОЙС ЧУЕИ РЕТЕНЕООЩИ $X_j$ МЕЦБФ Ч ДПРХУФЙНЩИ РТЕДЕМБИ:
\[\forall j\; \min(X_j) \leq \Sigma_j(\Oe') \leq \max(X_j)\,,\]
ЗДЕ ЮЕТЕЪ $\min(X_j)$ Й
$\max(X_j)$ ДМС РЕТЕНЕООПК $X_j[m,n]$ ПВПЪОБЮЕОЩ УППФЧЕФУФЧЕООП ЮЙУМБ $m$ Й
$n$.

бМЗПТЙФН \VMinMax{} (ТБЪДЕМ~\ref{sec:VMinMax}) ЧЩВЙТБЕФ ФБЛЙЕ РТЕДЕМЩ ЙЪНЕОЕОЙС
ЧЕДХЭЕК РЕТЕНЕООПК ЗТХРРЩ $G_p$, ЮФПВЩ ЧЩРПМОСМЙУШ РПМХЮЕООЩЕ ПЗТБОЙЮЕОЙС ДМС
УЧПВПДОПК РЕТЕНЕООПК $X$.  фБЛЙН ПВТБЪПН, РТЙ ЛБЦДПН ТБУУНБФТЙЧБЕНПН ЪОБЮЕОЙЙ
ЧЕДХЭЕК РЕТЕНЕООПК, ЗТБОЙЮОЩЕ ХУМПЧЙС ДМС ЧУЕИ ПУФБМШОЩИ РЕТЕНЕООЩИ ВХДХФ
БЧФПНБФЙЮЕУЛЙ ЧЩРПМОЕОЩ.

\ignore{
\begin{thm}
	рХУФШ ГЕРПЮЛБ $\Scl$ ФБЛПЧБ, ЮФП РТЙ ОЕЛПФПТЩИ ЪОБЮЕОЙСИ УФБТЩИ РЕТЕНЕООЩИ
	ЧУЕ ТЕЫЕОЙС УЙУФЕНЩ $\Req$ РБТБНЕФТЙЪХАФУС ЪОБЮЕОЙСНЙ $p$ УЧПВПДОЩИ
	ОЕЙЪЧЕУФОЩИ.  фПЗДБ РПУФТПЕООЩК ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК РТПЗТБННЩ ЧЩРПМОЙФ
	ОЕ ВПМЕЕ, ЮЕН $C \cdot p^2 \cdot q$ УТБЧОЕОЙК ГЕМПЮЙУМЕООЩИ ЧЩТБЦЕОЙК, ЗДЕ
	$C$ \--- ЛПОУФБОФБ, ОЕ ЪБЧЙУСЭБС ПФ ЪОБЮЕОЙК УФБТЩИ РЕТЕНЕООЩИ, $q$ \---
	ЛПМЙЮЕУФЧП РЕТЕУФТПЕЛ Ч ГЕРПЮЛЕ $\Scl$.
\end{thm}

уТБЧОЕОЙС ГЕМПЮЙУМЕООЩИ ЧЩТБЦЕОЙК ЙУРПМШЪХАФУС РТЙ РТПЧЕТЛЕ ХУМПЧЙК,
РПУФТПЕООЩИ ОБ ЫБЗЕ~\ref{lst:EQ-conds} БМЗПТЙФНБ \EqA{} (ТБЪДЕМ~\ref{sec:EqA}),
РТЙ ЧЩЮЙУМЕОЙЙ РТЕДЕМПЧ ЙФЕТЙТПЧБОЙС УМЕДХАЭЕК ПФЛТЩФПК РЕТЕНЕООПК Й РТЙ
РТПЧЕТЛЕ ФПЗП, ЮФП УМЕДХАЭЕЕ ЪОБЮЕОЙЕ ДМЙОЩ ФЕЛХЭЕК ЙФЕТЙТХЕНПК РЕТЕНЕООПК
ПУФБЕФУС Ч ДПРХУФЙНЩИ РТЕДЕМБИ (Ч ГЙЛМЕ).

рХУФШ $[G_0,G_1,\ldots,G_k]$ \--- ЗТХРРЩ ХТБЧОЕОЙК, РПУФТПЕООЩЕ РП ГЕРПЮЛЕ
$\Scl$ У РПНПЭША БМЗПТЙФНПЧ \EqB{} (ТБЪДЕМ~\ref{sec:EqB}) Й \EqG{}
(ТБЪДЕМ~\ref{sec:EqG}).  

фБЛ ЛБЛ РТБЧЩЕ ЮБУФЙ РЕТЕУФТПЕЛ ОЕ УПДЕТЦБФ УЛПВПЛ, ЧУЕ ЗТХРРЩ (Й ХТБЧОЕОЙС ЙЪ
ЗТХРРЩ $G_0$), РПУФТПЕООЩЕ Ч РТПГЕУУЕ ДБМШОЕКЫЕК ЛПНРЙМСГЙЙ ГЕРПЮЛЙ $\Scl$,
ВХДХФ ЛПОЛТЕФЙЪЙТПЧБФШ ЛБЛХА-МЙВП ЙЪ ЗТХРР $G_1,\ldots,G_k$
(УН.~УЧПКУФЧП~\ref{pr:concret} ТБЪВЙЕОЙС ХТБЧОЕОЙК ОБ ЗТХРРЩ), РПЬФПНХ ДМС ОЙИ
ОБ ЫБЗЕ~\ref{lst:EQ-conds} БМЗПТЙФНБ \EqA{} Ч ЛПДЕ
ЙНРЕТБФЙЧОПК РТПЗТБННЩ ОЕ ВХДЕФ РПУФТПЕОП ОЙЛБЛЙИ РТПЧЕТПЛ.  уМЕДПЧБФЕМШОП,
ЛПМЙЮЕУФЧП УТБЧОЕОЙК ГЕМПЮЙУМЕООЩИ ЧЩТБЦЕОЙК, ПУХЭЕУФЧМСЕНЩИ РТЙ РТПЧЕТЛЕ
ХУМПЧЙК, РПУФТПЕООЩИ ОБ ЫБЗЕ~\ref{lst:EQ-conds} БМЗПТЙФНБ \EqA, ОЕ РТЕЧПУИПДЙФ
$C_0 \cdot q$, ЗДЕ $C_0$ \--- ОЕЛПФПТБС ЛПОУФБОФБ.
}


\section{чПЪНПЦОЩЕ РХФЙ ХМХЮЫЕОЙС БМЗПТЙФНБ ЛПНРЙМСГЙЙ}

тБУУНПФТЕООЩК Ч ДБООПК ТБВПФЕ БМЗПТЙФН ЛПНРЙМСГЙЙ ГЕРПЮЛЙ РЕТЕУФТПЕЛ ЙУРПМШЪХЕФ БОБМЙЪ ДМЙО ДМС
УХЦЕОЙС ПВМБУФЙ РЕТЕВПТБ РТЙ РПЙУЛЕ ТЕЫЕОЙС ГЕРПЮЛЙ.  пДОБЛП, ЙУРПМШЪХЕФУС ОЕ
ЧУС ЙОЖПТНБГЙС, ЛПФПТХА НПЦОП ЙЪЧМЕЮШ ЙЪ УППФОПЫЕОЙК ОБ ДМЙОЩ.

еУМЙ $\Req$ \--- УЙУФЕНБ ХТБЧОЕОЙК (УППФЧЕФУФЧХАЭБС ГЕРПЮЛЕ РЕТЕУФТПЕЛ $\Scl$)
ПФОПУЙФЕМШОП РЕТЕНЕООЩИ $Y \in \mathbb{R}$, ЛБЛ ПРЙУБОП Ч
ТБЪДЕМЕ~\ref{sec:efficiency}, ФП ЙУРПМШЪПЧБОЙА ЧУЕК ЙОЖПТНБГЙЙ П УППФОПЫЕОЙСИ
ДМЙО УППФЧЕФУФЧХЕФ РПЙУЛ ЧУЕИ ГЕМПЮЙУМЕООЩИ ТЕЫЕОЙК УЙУФЕНЩ $\Req$, ФБЛЙИ, ЮФП
ЛБЦДПК РЕТЕНЕООПК $Y[m,n]$ РТЙУЧБЙЧБЕФУС ЪОБЮЕОЙЕ ЙЪ ПФТЕЪЛБ (МХЮБ) $[m,n]$.

\subsection{хФПЮОЕОЙЕ ЗТБОЙГ РЕТЕВПТБ}
еУМЙ ТЕЫЕОЙС УЙУФЕНЩ $\Req$ РБТБНЕФТЙЪХАФУС ВПМЕЕ, ЮЕН ПДОПК УЧПВПДОПК
ОЕЙЪЧЕУФОПК, ФП РПУФТПЕООЩК БМЗПТЙФНПН \CSC{} ЖТБЗНЕОФ ЛПДБ ЙНРЕТБФЙЧОПК
РТПЗТБННЩ ВХДЕФ РЕТЕВЙТБФШ ОЕ ФПМШЛП ФБЛЙЕ ТЕЫЕОЙС УЙУФЕНЩ $\Req$, ЛПФПТЩЕ
РТЙУЧБЙЧБАФ ЛБЦДПК РЕТЕНЕООПК $Y[m,n]$ ЪОБЮЕОЙЕ ЙЪ ПФТЕЪЛБ (МХЮБ) $[m,n]$.
ьФП УЧСЪБОП У ФЕН, ЮФП УЧПВПДОЩЕ РЕТЕНЕООЩЕ, ЧИПДСЭЙЕ УПЧНЕУФОП Ч ЧЩТБЦЕОЙЕ ДМС
ОЕЛПФПТПК УЧСЪБООПК РЕТЕНЕООПК, НПЗХФ ПЗТБОЙЮЙЧБФШ ЪОБЮЕОЙС ДТХЗ ДТХЗБ.
бМЗПТЙФН \EqA{} ОЕ ЗЕОЕТЙТХЕФ ЛПД ДМС УППФЧЕФУФЧХАЭЕЗП БОБМЙЪБ.

тБУУНПФТЙН РТПГЕУУ ЛПНРЙМСГЙЙ УМЕДХАЭЕК ГЕРПЮЛЙ:
\[
	\begin{array}{r@{\;}c@{\;}l}
		e_x & : & e_1\,e_2\,e_3\,e_4\,e_5\,e_6,\\
		e_5 & : & e_2\,e_y,\\
		e_6 & : & e_3\,e_y,\\
		e_z & : & e_4\,e_5\,e_6
	\end{array}
\]
ъДЕУШ $e_x$, $e_y$ Й $e_z$ \--- УФБТЩЕ РЕТЕНЕООЩЕ, Б $e_1,\ldots,e_6$ \--- ОПЧЩЕ.
%
рП ФБЛПК ГЕРПЮЛЕ РЕТЕУФТПЕЛ ВХДЕФ РПУФТПЕОБ УМЕДХАЭБС (ЕДЙОУФЧЕООБС) ЗТХРРБ $G_1$ ХТБЧОЕОЙК
ОБ ДМЙОЩ (УН.~БМЗПТЙФН~\EqG, ТБЪДЕМ~\ref{sec:EqG}):
\[
	\left\{
	\begin{array}{r@{\;\;}c@{\;\;}l}
		X_1 & = & A_x + 2 \cdot A_y - A_z - X_5 - X_6\\
		X_2 & = & X_5 - A_y\\
		X_3 & = & X_6 - A_y\\
		X_4 & = & A_z - X_5 - X_6
	\end{array}
	\right.
\]

бОБМЙЪЙТХС РПУМЕДПЧБФЕМШОП (УОЙЪХ ЧЧЕТИ) РПМХЮЕООЩЕ ХТБЧОЕОЙС, УФТПСФУС
(УН.~БМЗПТЙФН~\ChkBnd, ТБЪДЕМ~\ref{sec:ChkBnd}) УМЕДХАЭЙЕ ПЗТБОЙЮЕОЙС ОБ ДМЙОЩ
УЧПВПДОЩИ РЕТЕНЕООЩИ:
\begin{enumerate}
	\item \(\left\{
		\begin{array}{r@{\;}r@{\;}c@{\;}l@{\;}l}
			0 & \leq & X_5 & \leq & A_z\\
			0 & \leq & X_6 & \leq & A_z
		\end{array}
		\right.\)\vadjust{\kern 3pt}
	\item \(\left\{
		\begin{array}{r@{\;}r@{\;}c@{\;}l@{\;}l}
			  0 & \leq & X_5 & \leq & A_z\\
			A_y & \leq & X_6 & \leq & A_z
		\end{array}
		\right.\)\vadjust{\kern 3pt}
	\item \(\left\{
		\begin{array}{r@{\;}r@{\;}c@{\;}l@{\;}l}
			A_y & \leq & X_5 & \leq & A_z\\
			A_y & \leq & X_6 & \leq & A_z
		\end{array}
		\right.\)\vadjust{\kern 3pt}
	\item \(\left\{
		\begin{array}{r@{\;}r@{\;}c@{\;}l@{\;}l}
			A_y & \leq & X_5 & \leq & \min(A_z,\, A_x + A_y - A_z)\\
			A_y & \leq & X_6 & \leq & \min(A_z,\, A_x + A_y - A_z)
		\end{array}
		\right.\)
\end{enumerate}

фБЛЙН ПВТБЪПН, Ч ЛПД ЙНРЕТБФЙЧОПК РТПЗТБННЩ ВХДЕФ ЧЩЧЕДЕОБ РТПЧЕТЛБ ФПЗП, ЮФП
$A_y \leq \min(A_z,\, A_x + A_y - A_z)$, Й ЪБФЕН ВХДЕФ РПУФТПЕО ГЙЛМ РП
РЕТЕНЕООПК $e_1$, ДМЙОБ ЪОБЮЕОЙС ЛПФПТПК ВХДЕФ ЙЪНЕОСФШУС ПФ
$\max(0,\, A_x + 2 \cdot A_y - A_z - 2 \cdot \min(A_z,\, A_x + A_y - A_z))$ ДП
$A_x - A_z$ (УН.~БМЗПТЙФН~\VMinMax, ТБЪДЕМ~\ref{sec:VMinMax}).

еУМЙ РТЕДРПМПЦЙФШ, ЮФП $A_x = 200$, $A_y = 100$, Й $A_z = 150$, ФП ДМЙОБ
ЪОБЮЕОЙС РЕТЕНЕООПК $e_1$ ВХДЕФ ЙЪНЕОСФШУС ПФ 0 ДП 50.  оП СУОП, ЮФП РТЙ МАВЩИ
ЪОБЮЕОЙСИ ДМЙОЩ РЕТЕНЕООПК $e_1$, РПМХЮБАЭБСУС ГЕРПЮЛБ ВХДЕФ ОЕУПЧНЕУФОБ, ФБЛ
ЛБЛ ДМЙОБ ЛБЦДПК ЙЪ РЕТЕНЕООЩИ $e_5$ Й $e_6$ ПЗТБОЙЮЕОБ УОЙЪХ ЮЙУМПН 100, Б
УХННБ ЬФЙИ ДМЙО ПЗТБОЙЮЕОБ УЧЕТИХ ЮЙУМПН 150.

рТПВМЕНБ Ч ФПН, ЮФП УЧПВПДОЩЕ РЕТЕНЕООЩЕ $X_5$ Й $X_6$ ЧИПДСФ Ч РПУМЕДОЕЕ
ХТБЧОЕОЙЕ ЗТХРРЩ ПДОПЧТЕНЕООП, ПДОБЛП ПЗТБОЙЮЕОЙС ОБ ОЙИ ЗЕОЕТЙТХАФУС
ОЕЪБЧЙУЙНП.  ч ДБООПН ЛПОЛТЕФОПН УМХЮБЕ ДПУФБФПЮОП ВЩМП ВЩ РПУМЕ РПМХЮЕОЙС ОБ
УЧПВПДОЩЕ РЕТЕНЕООЩЕ ОЕФТЙЧЙБМШОЩИ ПЗТБОЙЮЕОЙК УОЙЪХ, ЕЭЕ ТБЪ ЧЩЮЙУМЙФШ
ПЗТБОЙЮЕОЙС ОБ ОЙИ УЧЕТИХ, ЙУИПДС ЙЪ РПУМЕДОЕЗП ХТБЧОЕОЙС.

\subsection{бЛЛХТБФОЩК РЕТЕВПТ ГЕМПЮЙУМЕООЩИ ТЕЫЕОЙК}

бМЗПТЙФН \EqA{} ОЕ ДЕМБЕФ ОЙЛБЛЙИ РПРЩФПЛ ЧЩЛЙОХФШ ЙЪ ТБУУНПФТЕОЙС ФЕ ПВМБУФЙ
ЪОБЮЕОЙК РЕТЕНЕООЩИ, Ч ЛПФПТЩИ ОЕ НПЗХФ ОБИПДЙФШУС ГЕМПЮЙУМЕООЩЕ ТЕЫЕОЙС
УЙУФЕНЩ $\Req$.

нЕЦДХ ФЕН, ДБЦЕ ОЕУМПЦОЩК БОБМЙЪ Ч ЬФПН ОБРТБЧМЕОЙЙ НПЦЕФ ДБФШ ЪОБЮЙФЕМШОПЕ
УПЛТБЭЕОЙЕ ПВМБУФЙ РЕТЕВПТБ.  оБРТЙНЕТ, ТБУУНПФТЙН ТЕБМЙЪБГЙА ЖХОЛГЙЙ
\Verb|AreSymmetric| ЙЪ ТБЪДЕМБ~\ref{sec:IntroExampleSystem}, ЙЪПВТБЦЕООХА ОБ
ТЙУХОЛЕ~\ref{pic:AreSymmetric}.  мЕЗЛП ЧЙДЕФШ, ЮФП ЧЩТБЦЕОЙЕ
\begin{quote}
\asail{$(A_y + A_x - 2 \cdot X_1)$ \MOD\ $2\, \ne \,0$}
\end{quote}
УРТБЧЕДМЙЧП ФПЗДБ Й ФПМШЛП ФПЗДБ, ЛПЗДБ УРТБЧЕДМЙЧП ЧЩТБЦЕОЙЕ
\begin{quote}
\asail{$(A_y + A_x)$ \MOD\ $2\, \ne \,0$},
\end{quote}
ЛПФПТПЕ ОЕ ЪБЧЙУЙФ ПФ ЪОБЮЕОЙС ФЕЛХЭЕК ПФЛТЩФПК (ЙФЕТЙТХЕНПК) РЕТЕНЕООПК.
ьФП ХУМПЧЙЕ ДПУФБФПЮОП РТПЧЕТЙФШ ПДЙО ТБЪ РЕТЕД ЙУРПМОЕОЙЕН ГЙЛМБ.  еУМЙ ПОП
ПЛБЦЕФУС МПЦОЩН, ФП ГЙЛМ ОЕ ДПМЦЕО ЙУРПМОСФШУС ЧППВЭЕ.

дБМЕЕ, НПЦОП ЪБНЕФЙФШ, ЮФП ХУМПЧЙЕ ГЕМПЮЙУМЕООПУФЙ РПЪЧПМСЕФ РПДВЙТБФШ ЪОБЮЕОЙС
ДМЙО ЙФЕТЙТХЕНЩИ РЕТЕНЕООЩИ ОЕ РПДТСД, Б У ПРТЕДЕМЕООЩН ЫБЗПН.

оБРТЙНЕТ,
ТБУУНПФТЙН РЕТЕУФТПКЛХ ${e_x : e_1\,e_2\,e_2}$, ЗДЕ $e_x$ \--- УФБТБС, Б $e_1$ Й
$e_2$ \--- ОПЧЩЕ РЕТЕНЕООЩЕ.  сУОП, ЮФП ДМЙОХ РЕТЕНЕООПК $e_1$ УМЕДХЕФ
РПДВЙТБФШ У ЫБЗПН 2.

пЗТБОЙЮЕОЙС ОБ ПЮЕТЕДОПЕ ЪОБЮЕОЙЕ ДМЙОЩ ЙФЕТЙТХЕНПК РЕТЕНЕООПК НПЗХФ ВЩФШ
РПМХЮЕОЩ Й ДТХЗЙНЙ УРПУПВБНЙ (ОБРТЙНЕТ, У РПНПЭША БОБМЙЪБ ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК,
ЧИПДСЭЙИ Ч РЕТЕУФТПКЛХ), Й ЪДЕУШ ЧПЪОЙЛБЕФ ЙОФЕТЕУОБС ЧПЪНПЦОПУФШ ДМС
ЛПНВЙОБГЙЙ НЕФПДБ БОБМЙЪБ ДМЙО У ДТХЗЙНЙ НЕФПДБНЙ УХЦЕОЙС ПВМБУФЙ РЕТЕВПТБ РТЙ
РПЙУЛЕ ТЕЫЕОЙК РЕТЕУФТПЕЛ.

\subsection*{вМБЗПДБТОПУФЙ}
ъБ РМПДПФЧПТОЩЕ ПВУХЦДЕОЙС РП ФЕНЕ ДБООПК ТБВПФЩ БЧФПТЩ ВМБЗПДБТОЩ ХЮБУФОЙЛБН РТПЕЛФБ
ТЕБМЙЪБГЙЙ УЙУФЕНЩ РТПЗТБННЙТПЧБОЙС тЕЖБМ рМАУ: м.~ч.~рБТНЕОПЧПК, у.~н.~рПОПНБТЕЧПК Й
б.~ж.~уМЕРХИЙОХ.
   пУПВЩЕ ВМБЗПДБТОПУФЙ ТЕЖБМ\-/БЛФЙЧЙУФБН, ВЕЪ ЮШЙИ ХУЙМЙК ОЕ ХДБМПУШ ВЩ 
ЪБРПМОЙФШ ДБООЩНЙ фБВМЙГХ~\ref{tab:IsTripletTime}:
	б.~б.~чМБДЙНЙТПЧХ,
	бО.~ч.~лМЙНПЧХ,
	бТЛ.~ч.~лМЙНПЧХ,
	б.~р.~оЕНЩФЩИ Й
	н.~а.~рПФБОЙОХ.

\begin{bibsection}
\begin{biblist}

\bib{bib:Refal-5}{manual}{
        author={Turchin, V. F.},
        title={Refal\-/5},
        type={Programming Guide and Reference Manual},
        publisher={New England Publishing Co.},
        place={Holyoke},
        note={\mbox{\url{http://shura.botik.ru/refal/book/html/}}, ОБ ТХУУЛПН СЪЩЛЕ:
        \mbox{\url{http://www.refal.ru/rf5_frm.htm}}},
        date={1989},
}

\bib{bib:Refal+}{manual}{
        author={зХТЙО, т. ж.},
        author={тПНБОЕОЛП, у. б.},
        title={сЪЩЛ РТПЗТБННЙТПЧБОЙС тЕЖБМ рМАУ},
        pages={183},
        publisher={йОФЕТФЕИ},
        place={н.},
        date={1991},
}
\bib{bib:KRT-Comp}{misc}{
        author={лМЙНПЧ, бО. ч.},
        author={тПНБОЕОЛП, у. б.},
        author={фХТЮЙО, ч. ж.},
        title={лПНРЙМСФПТ У СЪЩЛБ тЕЖБМ},
        publisher={йрн ЙН. н.ч.лЕМДЩЫБ},
        place={н.},
        date={1972},
        pages={74},
}

\bib{bib:KRT-PM}{misc}{
        author={лМЙНПЧ, бО. ч.},
        author={тПНБОЕОЛП, у. б.},
        author={фХТЮЙО, ч. ж.},
        title={фЕПТЕФЙЮЕУЛЙЕ ПУОПЧЩ УЙОФБЛУЙЮЕУЛПЗП ПФПЦДЕУФЧМЕОЙС Ч СЪЩЛЕ тЕЖБМ},
        series={13},
        type={рТЕРТЙОФ},
        publisher={йрн ЙН. н.ч.лЕМДЩЫБ},
        place={н.},
        date={1973},
        pages={65},
}

\bib{bib:Refal-2}{book}{
        author={тПНБОЕОЛП, у. б.},
        title={тЕБМЙЪБГЙС тЕЖБМБ\-/2},
        publisher={йрн ЙН. н.ч.лЕМДЩЫБ},
        place={н.},
        date={1987},
        pages={191},
}

\bib{bib:Rom-diss}{thesis}{
        author={тПНБОЕОЛП, у. б.},
        title={нБЫЙООП-ОЕЪБЧЙУЙНЩК ЛПНРЙМСФПТ У СЪЩЛБ ТЕЛХТУЙЧОЩИ ЖХОЛГЙК},
	type={дЙУУЕТФБГЙС ОБ УПЙУЛБОЙЕ ХЮ.УФЕРЕОЙ Л.Ж.-Н.О.},
        publisher={йрн ЙН. н.ч.лЕМДЩЫБ},
        place={н.},
        date={1978},
        pages={211},
}

\bib{bib:vector-exps}{misc}{
        author={бВТБНПЧ, у. н.},
        author={тПНБОЕОЛП, у. б.},
        title={рТЕДУФБЧМЕОЙЕ ПВЯЕЛФОЩИ ЧЩТБЦЕОЙК НБУУЙЧБНЙ РТЙ ТЕБМЙЪБГЙЙ СЪЩЛБ тЕЖБМ},
        series={186},
        type={рТЕРТЙОФ},
        publisher={йрн ЙН. н.ч.лЕМДЩЫБ},
        pages={27},
        place={н.},
        date={1988},
}

\bib{bib:rbvcomp}{misc}{
        author={тПНБОЕОЛП, у. б.},
        title={лПНРЙМСГЙС тЕЖБМ\-/РТПЗТБНН Ч ЧЙТФХБМШОЩК ЛПД},
        date={1999},
        note={\\\mbox{\url{http://shade.msu.ru/refal.msu.ru/docs/rbvcomp.ps.gz}}},
}


\bib{bib:Web:New-Refal+}{report}{
        title={тЕБМЙЪБГЙС СЪЩЛБ РТПЗТБННЙТПЧБОЙС тЕЖБМ рМАУ ЪБ УЮЕФ РТСНПК ЛПНРЙМСГЙЙ Ч ЙНРЕТБФЙЧОЩК СЪЩЛ},
        date={2003},
        institution={йру тбо},
        type={чЕВ\-/УБКФ РТПЕЛФБ},
        note={\\\mbox{\url{http://skif.pereslavl.ru/refal}}},
}

\bib{bib:K03}{misc}{
        author={Klimov, A. V.},
        title={Refal\-/6},
        date={2003}, 
        note={\mbox{\url{http://www.refal.org/\~arklimov/refal6}}},
}
\bib{bib:KK03}{misc}{
        author={Klimov, A. V.},
        author={Klimov, An. V.},
        title={REFAL \---JAVA. The prog\-ram\-ming language Refal implemented on top of the
        Java2 Platform},
        note={\\\mbox{\url{http://www.refal.org/\~arklimov/refal6/refal-j.htm}}},
        date={2003}, 
}

\bib{bib:Refal-Plus-04}{inproceedings}{
        author={бВТБНПЧ, уЕТЗЕК нЙИБКМПЧЙЮ},
        author={пТМПЧ, бОФПО аТШЕЧЙЮ},
        author={рБТНЕОПЧБ, мАВПЧШ чБМЕТШЕЧОБ},
        author={рПОПНБТЕЧБ, уЧЕФМБОБ нЙИБКМПЧОБ},
        author={уМЕРХИЙО, бОДТЕК жЕМЙЛУПЧЙЮ},
        title={оПЧЩК РПДИПД Л ТЕБМЙЪБГЙЙ УЙУФЕНЩ РТПЗТБННЙТПЧБОЙС тЕЖБМ~рМАУ},
        publisher={жЙЪНБФМЙФ},
        conference={нЕЦДХОБТПДОБС ЛПОЖЕТЕОГЙС <<рТПЗТБННОЩЕ УЙУФЕНЩ: ФЕПТЙС Й РТЙМПЦЕОЙС>>},
        place={рЕТЕУМБЧМШ\-/ъБМЕУУЛЙК},
        date={2004},
}

\end{biblist}
\end{bibsection}

\end{document}
