Final preparations (or afterwards?).

[algebraic-prog-equiv.git] / intro.tex

\section{ðÒÅÄÍÅÔ ÒÁÂÏÔÙ (ÉÓÓÌÅÄÕÅÍÁÑ ÓÏÄÅÒÖÁÔÅÌØÎÁÑ ÚÁÄÁÞÁ)}
íÙ ÉÓÓÌÅÄÕÅÍ \tING{ÐÒÏÂÌÅÍÕ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ} (\tING{ðü}).
ïÂßÑÓÎÉÍ ÐÏÄÒÏÂÎÅÅ, ÞÔÏ ÜÔÏ ÚÎÁÞÉÔ.

\bigskip

ðÒÏÇÒÁÍÍÙ\T Ä×ÕÓÔÏÒÏÎÎÉÅ ÓÕÝÎÏÓÔÉ. 

\paragraph{óÉÎÔÁËÓÉÓ.}
õ ÐÒÏÇÒÁÍÍ ÅÓÔØ ÓÉÎÔÁËÓÉÞÅÓËÏÅ ÐÒÅÄÓÔÁ×ÌÅÎÉÅ: ÐÒÏÇÒÁÍÍÙ ÏÂÙÞÎÏ
ÚÁÐÉÓÙ×ÁÀÔÓÑ ÎÁ ËÁËÏÍ-ÎÉÂÕÄØ ÑÚÙËÅ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ, ÓÏÓÔÁ×ÌÑÀÔÓÑ ÉÚ
ÂÁÚÏ×ÙÈ ÓÏÓÔÁ×ÌÑÀÝÉÈ × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÐÒÁ×ÉÌÁÍÉ ÓÉÎÔÁËÓÉÓÁ. 

\paragraph{óÅÍÁÎÔÉËÁ.}
é Ó ÐÒÏÇÒÁÍÍÁÍÉ Ó×ÑÚÁÎÏ ÉÈ ÓÅÍÁÎÔÉÞÅÓËÏÅ ÚÎÁÞÅÎÉÅ. ÷Ï-ÐÅÒ×ÙÈ,
ÉÓÐÏÌÎÅÎÉÅ ÐÒÏÇÒÁÍÍÙ, ×Ï ×ÒÅÍÑ ËÏÔÏÒÏÇÏ ÉÓÐÏÌÎÉÔÅÌØ ×ÚÁÉÍÏÄÅÊÓÔ×ÕÅÔ Ó
ÏËÒÕÖÅÎÉÅÍ, ÞÉÔÁÑ ÉÚ ÎÅÇÏ ×ÈÏÄÎÙÅ ÄÁÎÎÙÅ, ÐÒÏÉÚ×ÏÄÑ ×ÎÕÔÒÅÎÎÉÅ
×ÙÞÉÓÌÅÎÉÑ É ×ÙÄÁ×ÁÑ ÐÏÌÕÞÅÎÎÙÅ ÒÅÚÕÌØÔÁÔÙ ÏÂÒÁÔÎÏ × ÏËÒÕÖÅÎÉÅ\T
ÓÍÙÓÌ, ÚÁÌÏÖÅÎÎÙÊ × ÐÒÏÇÒÁÍÍÕ. ÷Ï-×ÔÏÒÙÈ, ÓÅÍÁÎÔÉËÁ ÐÒÏÇÒÁÍÍ (×
ÎÅËÏÔÏÒÏÍ ÑÚÙËÅ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ) ÍÏÖÅÔ
ÂÙÔØ ÆÏÒÍÁÌØÎÏ ÏÐÉÓÁÎÁ ÐÒÉ ÐÏÍÏÝÉ ËÁËÉÈ-ÔÏ ÆÏÒÍÁÌØÎÙÈ ÓÒÅÄÓÔ×. ôÏ, ÞÔÏ
ÔÁËÏÅ ÏÐÉÓÁÎÉÅ ÓÏÐÏÓÔÁ×ÌÑÅÔ ËÁÖÄÏÊ ÐÒÏÇÒÁÍÍÅ, ÔÏÖÅ ÍÏÖÎÏ ÓÞÉÔÁÔØ
ÚÎÁÞÅÎÉÅÍ ÐÒÏÇÒÁÍÍÙ.

\paragraph{ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ.}
ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÉ ÏÞÅÎØ ÏÂÝÅÍ ×ÚÇÌÑÄÅ ÎÁ ×ÅÝÉ
ÆÏÒÍÕÌÉÒÕÅÔÓÑ ÔÁË: 
\begin{quote}
ÐÏ ÄÁÎÎÙÍ ÓÉÎÔÁËÓÉÞÅÓËÉÍ ÐÒÅÄÓÔÁ×ÌÅÎÉÑÍ
ÐÒÏÇÒÁÍÍ, ÏÐÒÅÄÅÌÉÔØ ÏÄÉÎÁËÏ×Ù ÌÉ ÏÎÉ Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÓÅÍÁÎÔÉËÉ. 
\end{quote}
éÎÏÇÄÁ
ÇÏ×ÏÒÑÔ, ÏÄÉÎÁËÏ×ÏÅ ÌÉ Õ ÎÉÈ ÐÏ×ÅÄÅÎÉÅ, ÉÌÉ ÏÐÒÅÄÅÌÑÀÔ ÌÉ ÏÎÉ ÏÄÎÏ É
ÔÏ ÖÅ ÏÔÎÏÛÅÎÉÅ ÍÅÖÄÕ ×ÈÏÄÎÙÍÉ ÄÁÎÎÙÍÉ É ×ÙÈÏÄÎÙÍÉ
ÒÅÚÕÌØÔÁÔÁÍÉ. (÷ÐÒÏÞÅÍ, ÐÏÓÌÅÄÎÑÑ ÆÏÒÍÕÌÉÒÏ×ËÁ ÂÏÌÅÅ ËÏÎËÒÅÔÎÁ É
ÐÒÅÄÐÏÌÁÇÁÅÔ ×ÙÂÏÒ ÎÅËÏÔÏÒÏÇÏ ÏÐÒÅÄÅÌ£ÎÎÏÇÏ ×ÚÇÌÑÄÁ ÎÁ ÔÏ, ÞÔÏ ÔÁËÏÅ
ÓÅÍÁÎÔÉËÁ ÐÒÏÇÒÁÍÍÙ.)

\paragraph{áÌÇÏÒÉÔÍÉÞÅÓËÁÑ ÒÁÚÒÅÛÉÍÏÓÔØ.}
íÙ ÉÎÔÅÒÅÓÕÅÍÓÑ ÁÌÇÏÒÉÔÍÉÞÅÓËÏÊ ÒÁÚÒÅÛÉÍÏÓÔØÀ ÔÁËÏÊ ÐÒÏÂÌÅÍÙ ÐÒÉ
ÏÐÒÅÄÅÌ£ÎÎÙÈ ÕÔÏÞÎÅÎÉÑÈ, ËÁÓÁÀÝÉÈÓÑ ÔÏÇÏ, 
ÞÔÏ ÍÙ ÐÏÎÉÍÁÅÍ ÐÏÄ ÓÉÎÔÁËÓÉÓÏÍ É ÓÅÍÁÎÔÉËÏÊ ÐÒÏÇÒÁÍÍ. 

ðÏÑÓÎÅÎÉÅ ÏÓÔÁÌØÎÏÊ ÞÁÓÔÉ ÎÁÚ×ÁÎÉÑ ÓÔÁÎÅÔ ×ÏÚÍÏÖÎÙÍ ÐÏÓÌÅ 
ÕÔÏÞÎÅÎÉÊ × òÁÚÄÅÌÅ~\ref{sec:abstract-models}. 
÷ÏÚÍÏÖÎÙÅ ×ÁÒÉÁÎÔÙ ÄÁÌØÎÅÊÛÉÈ ÕÔÏÞÎÅÎÉÊ ÚÁÄÁÞÉ × ×ÙÂÒÁÎÎÙÈ 
ÔÅÏÒÅÔÉÞÅÓËÉÈ ÒÁÍËÁÈ, ÉÈ Ó×ÏÊÓÔ×Á ÐÏ ÏÔÎÏÛÅÎÉÀ Ë ÒÁÚÒÅÛÉÍÏÓÔÉ ðü 
É Ó×ÑÚÉ ÍÅÖÄÕ ÎÉÍÉ ÓÁÍÉ ÐÏ ÓÅÂÅ ÔÏÖÅ ÓÏÓÔÁ×ÌÑÀÔ
ÐÒÅÄÍÅÔ ÉÓÓÌÅÄÏ×ÁÎÉÊ (ÄÁÎÎÏÊ ÒÁÂÏÔÙ).

\paragraph{ï ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÓÌÏ×Á \emph{ÐÒÏÇÒÁÍÍÁ}.}
äÁÌÅÅ, ÞÁÓÔÏ ËÏÇÄÁ ÍÙ ÂÕÄÅÍ ÇÏ×ÏÒÉÔØ \emph{ÐÒÏÇÒÁÍÍÁ}, ÍÙ ÂÕÄÅÍ ÉÍÅÔØ
× ×ÉÄÕ ÓÉÎÔÁËÓÉÞÅÓËÏÅ ÐÒÅÄÓÔÁ×ÌÅÎÉÅ ÐÒÏÇÒÁÍÍÙ (\te ÌÉÛ£ÎÎÕÀ ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍÕ).

\paragraph{éÎÔÅÒÅÓÎÏÓÔØ ÐÒÅÄÍÅÔÁ.}
éÓÓÌÅÄÏ×ÁÎÉÅ ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ, × ÔÏÍ ÞÉÓÌÅ 
ÓÏÚÄÁÎÉÅ ÜÆÆÅËÔÉ×ÎÙÈ ÁÌÇÏÒÉÔÍÏ×
ÐÒÏ×ÅÒËÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ, 
ÐÒÅÄÓÔÁ×ÌÑÅÔ ÉÎÔÅÒÅÓ ÄÌÑ ÒÅÛÅÎÉÑ ÐÒÁËÔÉÞÅÓËÉÈ
ÚÁÄÁÞ.%\T òÁÚÄÅÌ~\ref{sec:applications}.

ðü ÐÒÏÇÒÁÍÍ ÏÂÌÁÄÁÅÔ ÔÅÏÒÅÔÉÞÅÓËÏÊ ÚÁÎÉÍÁÔÅÌØÎÏÓÔØÀ, ×ÙÚ×ÁÎÎÏÊ
ÖÅÌÁÎÉÅÍ ×ÙÑÓÎÉÔØ ÇÒÁÎÉÃÕ ÍÅÖÄÕ ÒÁÚÒÅÛÉÍÙÍÉ É ÎÅÒÁÚÒÅÛÉÍÙÍÉ ÓÌÕÞÁÑÍÉ.
% \todo{[???]}\T òÁÚÄÅÌ~\ref{sec:interesting-theory}.

\paragraph{þÔÏ ÏÖÉÄÁÔØ ÏÔ ÒÁÂÏÔÙ?}
ðÒÅÖÄÅ ÞÅÍ ÕÔÏÞÎÑÔØ ÐÒÅÄÍÅÔ ÎÁÛÅÊ ÒÁÂÏÔÙ, ÄÁ×ÁÔØ ÐÏÓÔÁÎÏ×ËÕ ÎÁÛÅÊ
ÚÁÄÁÞÉ Ï ÐÒÏÂÌÅÍÅ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ × ÔÏÞÎÙÈ ÔÅÒÍÉÎÁÈ, ÏÐÉÓÙ×ÁÔØ ÉÓÐÏÌØÚÕÅÍÙÅ
ÍÅÔÏÄ٠ţ ÉÓÓÌÅÄÏ×ÁÎÉÑ É ÐÏÌÕÞÅÎÎÙÅ ÒÅÚÕÌØÔÁÔÙ, ÐÏÑÓÎÉÍ, ËÁËÏÇÏ
ÈÁÒÁËÔÅÒÁ ÜÔÁ ÒÁÂÏÔÁ.

ïÎÁ ÈÏÔØ É ÎÅËÏÒÏÔËÁÑ, ÎÏ ÓÏÄÅÒÖÉÔ ÍÁÌÏ ÎÅÉÚ×ÅÓÔÎÙÈ ÒÁÎÅÅ ÆÁËÔÏ×, ÉÌÉ
ÆÁËÔÏ×, ×Ù×ÏÄ ËÏÔÏÒÙÈ ÉÚ ÕÓÔÁÎÏ×ÌÅÎÎÙÈ ÒÁÎÅÅ ÐÏÔÒÅÂÏ×ÁÌ ÂÙ ËÁÖÄÙÊ ÐÏ ÏÔÄÅÌØÎÏÓÔÉ
ÓÌÏÖÎÙÈ ÒÁÓÓÕÖÄÅÎÉÊ. òÁÂÏÔÁ ×ÏÚÎÉËÌÁ ÉÚ ÖÅÌÁÎÉÑ ÏÔÄÅÌÉÔØ 
ÉÎÄÉ×ÉÄÕÁÌØÎÕÀ ÔÒÕÄÎÏÓÔØ ËÁÖÄÏÊ ÏÔÄÅÌØÎÏÊ ÚÁÄÁÞÉ ÉÚ
ÏÂÌÁÓÔÉ, ÏÈ×ÁÔÙ×ÁÅÍÏÊ ÔÅÍÏÊ ÒÁÂÏÔÙ, ÏÔ ÏÂÝÉÈ ÚÁËÏÎÏÍÅÒÎÏÓÔÅÊ,
ÒÁÓÐÒÏÓÔÒÁÎÉÔØ ÐÏÌÕÞÅÎÎÙÅ ÒÁÎÅÅ ÏÔÄÅÌØÎÙÅ ÒÅÛÅÎÉÑ ÎÁ ÂÏÌØÛÅÅ ÞÉÓÌÏ
ÓÌÕÞÁÅ×, ÓÏÏÔÎÅÓÔÉ ÉÈ ÍÅÖÄÕ ÓÏÂÏÊ, ÓÐÅÃÉÆÉÃÉÒÏ×ÁÔØ ÏÂÝÉÅ ÕÔ×ÅÒÖÄÅÎÉÑ
ÄÌÑ ÒÅÛÅÎÉÑ ÚÁÄÁÞ ÉÚ ÜÔÏÊ ÏÂÌÁÓÔÉ.%
\footnote{
÷ÏÔ ÓÏÚ×ÕÞÎÙÅ ÓÌÏ×Á Ï ÈÁÒÁËÔÅÒÅ ÒÁÂÏÔÙ, ÈÏÔÑ É ÐÏ×ÏÄÙ ÄÌÑ ÎÉÈ ÎÅÓÏÉÚÍÅÒÉÍÙ:
<<õÎÉ×ÅÒÓÁÌØÎÁÑ ÁÌÇÅÂÒÁ ÚÁÎÉÍÁÅÔÓÑ ÉÚÕÞÅÎÉÅÍ ÞÅÒÔ, ÏÂÝÉÈ ÄÌÑ
ÐÒÉ×ÙÞÎÙÈ ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÓÉÓÔÅÍ, ÔÁËÉÈ, ËÁË ÇÒÕÐÐÙ, ËÏÌØÃÁ, ÓÔÒÕËÔÕÒÙ
É~Ô.Ä.; \emph{ÐÒÉ ÜÔÏÍ ÏÐÒÅÄÅÌÑÅÔÓÑ ÎÁÓÔÏÑÝÅÅ ÍÅÓÔÏ ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÐÏÎÑÔÉÊ} É
ÞÁÓÔÏ ÏÂÎÁÒÕÖÉ×ÁÀÔÓÑ Ó×ÑÚÉ ÍÅÖÄÕ ÎÁ ÐÅÒ×ÙÊ ×ÚÇÌÑÄ ÒÁÚÌÉÞÎÙÍÉ
ÐÏÎÑÔÉÑÍÉ, ÞÔÏ 
\emph{ÐÏÍÏÇÁÅÔ ÓÉÓÔÅÍÁÔÉÚÁÃÉÉ ÒÅÚÕÌØÔÁÔÏ×. éÄÅÉ, ÓÏÄÅÒÖÁÝÉÅÓÑ
ÚÄÅÓØ ÎÁ ÓÁÍÏÍ ÄÅÌÅ ÏÞÅÎØ ÐÒÏÓÔÙ É ×ÏÚÎÉËÁÀÔ ÐÒÉ ÅÓÔÅÓÔ×ÅÎÎÏÍ ÏÂÏÂÝÅÎÉÉ
ÎÅÓËÏÌØËÉÈ ÞÁÓÔÎÙÈ ÓÌÕÞÁÅ×. ïÄÎÁËÏ ÎÕÖÎÏ ÐÏÍÎÉÔØ, ÞÔÏ ÜÔÏÔ ÐÏÄÈÏÄ
ÏÂÙÞÎÏ ÎÅ ÄÁ£Ô ÒÅÛÅÎÉÑ ×ÓÅÊ ÐÒÏÂÌÅÍÙ, Á ÔÏÌØËÏ ÉÚÂÁ×ÌÑÅÔ ÏÔ
ÔÒÉ×ÉÁÌØÎÙÈ ÄÅÔÁÌÅÊ, ÄÁ×ÁÑ ×ÏÚÍÏÖÎÏÓÔØ ÓËÏÎÃÅÎÔÒÉÒÏ×ÁÔØ ÓÉÌÙ ÎÁ ÓÕÔÉ
ÄÁÎÎÏÊ ÐÒÏÂÌÅÍÙ.}>> \cite{cohn-ua-rus}.}
%
üÔÏ ÉÍÅÅÔ ÚÎÁÞÉÍÏÓÔØ, ÐÏÔÏÍÕ ÞÔÏ
ÒÁÚÌÉÞÉÅ × ÐÏÎÑÔÉÑÈ, ÉÓÐÏÌØÚÏ×ÁÎÎÙÈ × ÐÏÓÔÁÎÏ×ËÁÈ  É 
ÉÚ×ÅÓÔÎÙÈ ÒÅÛÅÎÉÑÈ ÂÌÉÚËÉÈ Ó ÎÁÛÅÊ ÔÏÞËÉ
ÚÒÅÎÉÑ ÚÁÄÁÞ ÉÚ ÜÔÏÊ ÏÂÌÁÓÔÉ, ÍÅÛÁÌÏ ÐÏÎÑÔØ, ËÁË ÍÏÇÌÏ ÂÙ ×ÙÇÌÑÄÅÔØ
ÁÎÁÌÏÇÉÞÎÏÅ ÒÅÛÅÎÉÅ ÂÌÉÚËÏÊ ÚÁÄÁÞÉ. 
ëÏÎÅÞÎÏ, ÜÔÏ ÎÅ ÓÂÏÒÎÉË ÉÚ×ÅÓÔÎÙÈ ÆÁËÔÏ×: ÏÎÉ ×ÙÓÔÒÏÅÎÙ × ÔÏÍ ×ÉÄÅ, ×
ËÏÔÏÒÏÍ ÏÎÉ ÐÏÍÏÇÌÉ ÎÁÈÏÄÉÔØ ÎÏ×ÙÅ ÏÔ×ÅÔÙ É ÚÁÄÁ×ÁÔØ ÎÏ×ÙÅ ËÏÎËÒÅÔÎÙÅ
×ÏÐÒÏÓÙ.

ôÁËÁÑ ÒÁÂÏÔÁ ÄÁÌÁ ÎÅËÏÔÏÒÙÅ ÐÌÏÄÙ:
× ÏÂÝÕÀ ËÁÒÔÉÎÕ ÂÙÌÉ ×ËÌÀÞÅÎÙ É ÎÅËÏÔÏÒÙÅ ÎÏ×ÙÅ ÆÁËÔÙ, Á ÔÁËÖÅ ÓÔÁÌÉ
ÑÓÎÙ ÐÒÏÂÅÌÙ × ÉÓÓÌÅÄÕÅÍÏÊ ÏÂÌÁÓÔÉ É ÎÁÐÒÁ×ÌÅÎÉÑ, × ËÏÔÏÒÙÈ ÍÏÇÕÔ
×ÅÓÔÉÓØ ÄÁÌØÎÅÊÛÉÅ ÉÓÓÌÅÄÏ×ÁÎÉÑ, ÚÁÄÁÎÎÙÅ ËÏÎËÒÅÔÎÙÍÉ ×ÏÐÒÏÓÁÍÉ.



ðÏÄÒÏÂÎÅÅ Ï ÃÅÌÑÈ, ÐÏÓÔÁ×ÌÅÎÎÙÈ ÐÅÒÅÄ ÒÁÂÏÔÏÊ\T
òÁÚÄÅÌ~\ref{sec:goals}, 
É ÄÏÓÔÉÇÎÕÔÙÈ ÒÅÚÕÌØÔÁÔÁÈ\T  úÁËÌÀÞÅÎÉÅ.

\section{ðÒÅÄÓÔÁ×ÌÅÎÉÅ Ï ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÑÈ ÐÒÏÇÒÁÍÍ}
\label{sec:abstract-models}
÷ÏÔ ÉÚ ËÁËÉÈ ÐÒÅÄÓÔÁ×ÌÅÎÉÊ ÉÓÈÏÄÉÔ ÜÔÁ ÒÁÂÏÔÁ. 

\paragraph{<<îÅÄÏÓÔÕÐÎÏÓÔØ>>  ÄÌÑ ÉÓÓÌÅÄÏ×ÁÎÉÑ ÔÏÞÎÏÊ ÓÅÍÁÎÔÉËÉ.}
÷ ÔÏÞÎÏÓÔÉ ÐÒÁ×ÉÌÁ ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍ ÍÏÇÕÔ ÂÙÔØ ÎÅÄÏÓÔÕÐÎÙ ÉÌÉ
ÓÌÉÛËÏÍ ÓÌÏÖÎÙ, ÞÔÏÂÙ ÍÙ ÍÏÇÌÉ ÄÅÌÁÔØ ×Ù×ÏÄÙ Ï ÐÒÏÇÒÁÍÍÁÈ ÎÁ ÉÈ
ÏÓÎÏ×ÁÎÉÉ (ÂÅÓÐÏÌÅÚÎÏÓÔØ ÔÏÞÎÏÇÏ ÕÞ£ÔÁ ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍ ÏÂÝÅÇÏ
ÎÁÚÎÁÞÅÎÉÑ ÄÌÑ ÐÒÁËÔÉÞÅÓËÉÈ ÚÁÄÁÞ ÁÎÁÌÉÚÁ
ÐÏÄÔ×ÅÒÖÄÁÅÔ É ÔÅÏÒÅÍÁ òÁÊÓÁ\EndrõÓÐÅÎÓËÏÇÏ
\cite{Rice-recenum,Usp-algo,VerShen-computable}. 
%ÓÍ.~òÁÚÄÅÌ~\ref{sec:interesting-theory}).

\paragraph{áÂÓÔÒÁËÃÉÉ É ÏÔÎÏÛÅÎÉÅ ÁÐÐÒÏËÓÉÍÁÃÉÉ.}
ðÏÜÔÏÍÕ ÉÍÅÅÔ ÓÍÙÓÌ ÒÅÛÁÔØ ÚÁÄÁÞÉ ÁÎÁÌÉÚÁ ÐÒÏÇÒÁÍÍ (× ÔÏÍ ÞÉÓÌÅ, ðü) ×
ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÑÈ ÐÒÏÇÒÁÍÍ: × ÎÉÈ ÍÙ ÏÔ×ÌÅÞÅÎÙ ÏÔ ÎÅËÏÔÏÒÙÈ ÄÅÔÁÌÅÊ
ÓÉÎÔÁËÓÉÓÁ É ÓÅÍÁÎÔÉËÉ ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ, ÏÂÒÁÝÁÅÍ ×ÎÉÍÁÎÉÅ ÔÏÌØËÏ ÎÁ
ÐÏËÁÚÁ×ÛÉÅÓÑ ÎÁÍ ÐÏ ËÁËÉÍ-ÔÏ ÐÒÉÞÉÎÁÍ ÓÕÝÅÓÔ×ÅÎÎÙÅ ÄÅÔÁÌÉ (ÎÁÐÒÉÍÅÒ,
ÉÚ-ÚÁ ÏÓÏÂÅÎÎÏÓÔÅÊ ÒÅÛÁÅÍÏÊ ÐÒÁËÔÉÞÅÓËÏÊ ÚÁÄÁÞÉ). áÂÓÔÒÁËÔÎÁÑ ÍÏÄÅÌØ
ÐÒÏÇÒÁÍÍ \tING{ÁÐÐÒÏËÓÉÍÉÒÕÅÔ} ÄÒÕÇÕÀ ÁÂÓÔÒÁËÔÎÕÀ ÍÏÄÅÌØ ÐÒÏÇÒÁÍÍ (ÉÌÉ
ÍÏÄÅÌØ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÕÀ ÒÅÁÌØÎÙÍ ÐÒÏÇÒÁÍÍÁÍ), ÅÓÌÉ ÍÙ ÍÏÖÅÍ
ÐÅÒÅ×ÅÓÔÉ ÐÒÏÇÒÁÍÍÙ ÉÚ ÁÐÐÒÏËÓÉÍÉÒÕÅÍÏÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ × ÐÒÏÇÒÁÍÍÙ
ÁÐÐÒÏËÓÉÍÉÒÕÀÝÅÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ, ÔÁË, ÞÔÏ ÅÓÌÉ
ÎÅËÏÔÏÒÏÅ Ó×ÏÊÓÔ×Ï ÜÔÉÈ ÐÒÏÇÒÁÍÍ ÂÕÄÅÔ ×ÙÐÏÌÎÅÎÏ × ÁÐÐÒÏËÓÉÍÉÒÕÀÝÅÊ
ÍÏÄÅÌÉ, ÔÏ ÏÎÏ ÂÕÄÅÔ ×ÙÐÏÌÎÅÎÏ É × ÁÐÐÒÏËÓÉÍÉÒÕÅÍÏÊ. áÐÐÒÏËÓÉÍÁÃÉÑ ×
Ó×ÑÚÉ Ó ÐÒÏÂÌÅÍÏÊ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÚÎÁÞÉÔ, ÞÔÏ ÏÔÎÏÛÅÎÉÅ
ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ × ÁÐÐÒÏËÓÉÍÉÒÕÀÝÅÊ ÍÏÄÅÌÉ ÂÏÌÅÅ ÓÉÌØÎÏÅ, ÞÅÍ
× ÁÐÐÒÏËÓÉÍÉÒÕÅÍÏÊ.

÷ ÁÐÐÒÏËÓÉÍÉÒÕÀÝÅÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ ÉÎÔÅÒÅÓÕÀÝÉÅ ÎÁÓ Ó×ÏÊÓÔ×Á ÐÒÏÇÒÁÍÍ ÍÏÇÕÔ
ÏËÁÚÁÔØÓÑ ÒÁÚÒÅÛÉÍÙÍÉ, ÞÔÏ ÐÒÉÎÅÓ£Ô ÎÅËÏÔÏÒÕÀ ÐÏÌØÚÕ É ÄÌÑ ÁÎÁÌÉÚÁ
ÁÐÐÒÏËÓÉÍÉÒÕÅÍÏÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ.

\paragraph{ïÐÑÔØ Ï ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÓÌÏ×.}
÷ ÏÓÎÏ×ÎÏÍ × ÜÔÏÍ ÔÅËÓÔÅ ÓÌÏ×Ï \emph{ÐÒÏÇÒÁÍÍÁ} ÂÕÄÅÔ ÏÔÎÏÓÉÔÓÑ Ë
ÁÂÓÔÒÁËÔÎÙÍ ÐÒÏÇÒÁÍÍÁÍ\T ÓÉÎÔÁËÓÉÞÅÓËÉÍ ÐÒÅÄÓÔÁ×ÌÅÎÉÑÍ ÐÒÏÇÒÁÍÍ ×
ÉÚÕÞÁÅÍÏÊ ÁÂÓÔÒÁËÔÎÏÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ. óÌÏ×Á \emph{ÁÂÓÔÒÁËÔÎÁÑ ÍÏÄÅÌØ
  ÐÒÏÇÒÁÍÍ} ÎÁÍ ÐÏÎÁÄÏÂÉÌÉÓØ ÔÏÌØËÏ ÄÌÑ ÜÔÏÇÏ ××ÅÄÅÎÉÑ × ÓÕÔØ ÒÁÂÏÔÙ,
ÍÙ ÉÈ × ÏÓÎÏ×ÎÏÍ ÔÅËÓÔÅ ÉÓÐÏÌØÚÏ×ÁÔØ ÎÅ ÂÕÄÅÍ. éÎÏÇÄÁ ÍÙ ÂÕÄÅÍ
ÇÏ×ÏÒÉÔØ ÐÒÏ \emph{ÒÅÁÌØÎÙÅ ÐÒÏÇÒÁÍÍÙ}, ÉÍÅÑ × ×ÉÄÕ ÐÒÉÍÅÒÙ ÉÚ
ÒÅÁÌØÎÏÊ ÐÒÁËÔÉËÉ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ.

\paragraph{ä×Á ÕÒÏ×ÎÑ ÓÔÁ×ÑÝÉÈÓÑ ÐÒÉ ÉÓÓÌÅÄÏ×ÁÎÉÉ ÚÁÄÁÞ.}
íÙ ÂÕÄÅÍ ÉÍÅÔØ × ×ÉÄÕ Ä×Á ÕÒÏ×ÎÑ ÐÏÓÔÁÎÏ×ËÉ ×ÏÐÒÏÓÏ× × ÜÔÏÊ ÒÁÂÏÔÅ:
\tING{ÐÒÅÄÍÅÔÎÙÊ}, 
ÉÌÉ \tING{ÓÏÄÅÒÖÁÔÅÌØÎÙÊ},\T ×ÏÐÒÏÓÙ, ÏÓÍÙÓÌÅÎÎÙÅ Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÁÎÁÌÉÚÁ
ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ, É \tING{ÔÅÈÎÉÞÅÓËÉÊ}, 
ÉÌÉ \emph{ÍÁÔÅÍÁÔÉÞÅÓËÉÊ},\T ÍÁÔÅÍÁÔÉÞÅÓËÉÅ 
×ÏÐÒÏÓÙ, ×ÙÒÁÖÁÅÍÙÅ ×
ÔÅÒÍÉÎÁÈ ÆÏÒÍÁÌØÎÙÈ ÐÏÓÔÒÏÅÎÉÊ ÁÂÓÔÒÁËÔÎÏÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ. ÷ÏÐÒÏÓÙ ÏÄÎÏÇÏ ÕÒÏ×ÎÑ
ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ×ÏÐÒÏÓÁÍ ÄÒÕÇÏÇÏ. ÷ ÎÁÐÒÁ×ÌÅÎÉÉ ÉÓÓÌÅÄÏ×ÁÎÉÊ ÍÙ
ÒÕËÏ×ÏÄÓÔ×ÕÅÍÓÑ ÚÁÄÁÞÁÍÉ, ÐÏÓÔÁ×ÌÅÎÎÙÍÉ ÎÁ ÐÒÅÄÍÅÔÎÏÍ ÕÒÏ×ÎÅ, Á
ÒÅÁÌÉÚÕÅÍ ÉÓÓÌÅÄÏ×ÁÎÉÑ, ÎÁÈÏÄÉÍ ÏÔ×ÅÔÙ ÎÁ ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ. ôÅÍ
ÓÁÍÙÍ, ×ÏÚ×ÒÁÝÁÑÓØ Ë ÔÏÍÕ, ÞÔÏ ÂÙÌÏ ÓËÁÚÁÎÏ ÞÕÔØ ×ÙÛÅ,
\emph{ÐÒÏÇÒÁÍÍÁ}\T ÂÕÄÅÔ × ÏÓÎÏ×ÎÏÍ ÕÐÏÔÒÅÂÌÑÔØÓÑ ËÁË ÜÌÅÍÅÎÔ
ÔÅÈÎÉÞÅÓËÏÇÏ ÕÒÏ×ÎÑ ÎÁÛÅÇÏ ÉÓÓÌÅÄÏ×ÁÎÉÑ, Á \emph{ÒÅÁÌØÎÁÑ ÐÒÏÇÒÁÍÍÁ}\T
ÐÒÅÄÍÅÔÎÏÇÏ. (\emph{ðÒÏÇÒÁÍÍÁ} ÂÕÄÅÔ ÒÏÄÏ×ÙÍ ÔÅÒÍÉÎÏÍ ÄÌÑ
ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ ×ÓÅÈ ×ÏÚÍÏÖÎÙÈ ×ÉÄÏ×.)

\paragraph{þÔÏ ÉÚ ÐÒÅÄÍÅÔÎÏÇÏ ÕÒÏ×ÎÑ ÍÙ ÈÏÔÉÍ Ñ×ÎÏ ÕÞÅÓÔØ × ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÑÈ ÐÒÏÇÒÁÍÍ?}
íÙ ÂÕÄÅÍ ÉÓÓÌÅÄÏ×ÁÔØ ÁÂÓÔÒÁËÔÎÙÅ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ, ÐÏÚ×ÏÌÑÀÝÉÅ
ÕÞÉÔÙ×ÁÔØ Ó×ÏÊÓÔ×Á ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍ ÎÁÚ×ÁÎÎÙÅ ÎÁÍÉ 
\emph{ÞÁÓÔÉÞÎÏÊ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØÀ ÏÐÅÒÁÔÏÒÏ×} 
É \emph{(ÏÂÏÂÝ£ÎÎÏÊ) ÍÏÎÏÔÏÎÎÏÓÔØÀ ÏÐÅÒÁÔÏÒÏ×}, \te ÔÏ, ÞÔÏ ÎÅËÏÔÏÒÙÅ 
ÏÐÅÒÁÔÏÒÙ
\emph{ÎÅÚÁ×ÉÓÉÍÙ}, ÎÁÐÒÉÍÅÒ, × ÑÚÙËÅ ÔÉÐÁ Pascal ÎÅ×ÁÖÎÏ × ËÁËÏÍ
ÐÏÒÑÄËÅ ×ÙÐÏÌÎÅÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÉÚ ÓÌÅÄÕÀÝÉÈ Ä×ÕÈ ÏÐÅÒÁÔÏÒÏ×,
×ÙÐÏÌÎÅÎÉÅ ÐÒÉ×ÅÄ£Ô Ë ÏÄÎÏÍÕ É ÔÏÍÕ ÖÅ ÒÅÚÕÌØÔÁÔÕ:
\begin{align*}
&\parbox{.3\textwidth}{\ttfamily
  a := 6;\\
  b := c + d;
}
&&\parbox{.3\textwidth}{\ttfamily
  b := c + d;\\
  a := 6;
}
\end{align*}
É ÔÏ, ÞÔÏ ÎÅËÏÔÏÒÙÅ ÏÐÅÒÁÔÏÒÙ ÎÅ ÍÏÇÕÔ ÉÚÍÅÎÉÔØ ÚÎÁÞÅÎÉÅ ÌÏÇÉÞÅÓËÉÈ
ÐÒÏ×ÅÒÏË\T ÐÒÏÄÅÍÏÎÓÔÒÉÒÕÅÍ ÜÔÏ ÎÁ ÐÒÉÍÅÒÅ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÓÌÅÄÕÀÝÉÈ
Ä×ÕÈ ËÕÓËÏ× ËÏÄÁ ÎÁ Pascal'Å:
\begin{align*}
&\parbox{.3\textwidth}{\ttfamily
  if (n > 6) then begin\\
  \mbox{}\quad n := n + 2;\\
  \mbox{}\quad if (n > 6) then begin\\
  \mbox{}\quad\mbox{}\quad write(n);\\
  \mbox{}\quad end;\\
  end;
}
&&\parbox{.3\textwidth}{\ttfamily
  if (n > 6) then begin\\
  \mbox{}\quad n := n + 2;\\
  \mbox{}\quad write(n);\\
  end;
}
\end{align*}
\emph{ïÂÏÂÝ£ÎÎÏÊ}, ÐÏÔÏÍÕ ÞÔÏ ÉÍÅÅÔÓÑ × ×ÉÄÕ, ÞÔÏ ÍÏÖÅÔ ÐÒÉÓÕÔÓÔ×Ï×ÁÔØ
ÄÏÐÕÝÅÎÉÅ Ï ÔÏÍ, ÞÔÏ ÏÐÅÒÁÔÏÒ ÎÅ ÍÏÖÅÔ ÉÚÍÅÎÉÔØ ÚÎÁÞÅÎÉÅ $\True$
(ÍÏÎÏÔÏÎÎÏÓÔØ) ÉÌÉ ÞÔÏ ÏÎ ÎÅ ÍÏÖÅÔ ÉÚÍÅÎÉÔØ ÚÎÁÞÅÎÉÅ $\False$
(ÁÎÔÉÍÏÎÏÔÏÎÎÏÓÔØ) ÉÌÉ É ÔÏ, É ÄÒÕÇÏÅ ÏÄÎÏ×ÒÅÍÅÎÎÏ. <<é ÔÏ, É ÄÒÕÇÏÅ
ÏÄÎÏ×ÒÅÍÅÎÎÏ>> ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÐÒÉÍÅÒÕ Ó ÌÏÇÉÞÅÓËÏÊ ÐÒÏ×ÅÒËÏÊ,
ÓÏ×ÓÅÍ ÎÅÚÁ×ÉÓÉÍÏÊ ÏÔ ÏÐÅÒÁÔÏÒÁ:
\begin{align*}
&\parbox{.3\textwidth}{\ttfamily
  if (n > 6) then begin\\
  \mbox{}\quad write(n);\\
  end;\\
  if (n > 6) then begin\\
  \mbox{}\quad ok := true;\\
  end;
}
&&\parbox{.3\textwidth}{\ttfamily
  if (n > 6) then begin\\
  \mbox{}\quad write(n);\\
  \mbox{}\quad ok := true;\\
  end;
}
\end{align*}

ðÏÄÒÏÂÎÏÓÔÉ Ï ÎÁÛÅÍ ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ ÉÓÓÌÅÄÏ×ÁÎÉÑ É ÅÇÏ ÚÁÄÁÞÁÈ
ÂÕÄÅÔ ÒÁÓÓËÁÚÁÎÏ ÐÏÓÌÅ ÏÂÝÅÇÏ ÏÂÚÏÒÁ ÔÅÏÒÉÉ, Ó×ÑÚÁÎÎÏÊ Ó ðü,
× òÁÚÄÅÌÅ~\ref{sec:goals}.
%\section{ïÂÏÓÎÏ×ÁÎÉÅ ÉÎÔÅÒÅÓÎÏÓÔÉ}

%% \section{ïÂÝÁÑ ÔÅÏÒÅÔÉÞÅÓËÁÑ ÚÁÎÉÍÁÔÅÌØÎÏÓÔØ ðü}
%% \label{sec:interesting-theory}

\nocite{Rice-recenum,Usp-algo,VerShen-computable}
%\todo{[..., òÁÊÓÁ\EndrõÓÐÅÎÓËÏÇÏ, É Ô.Ð.]}

\section{ðÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞÉ}
\paragraph{ëÒÕÇ ÒÅÛÁÅÍÙÈ ÚÁÄÁÞ.}
õÖÅ ÇÏ×ÏÒÉÌÏÓØ, ÞÔÏ ÍÙ ÉÓÓÌÅÄÕÅÍ ÐÒÏÂÌÅÍÕ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ ×
ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÑÈ ÐÒÏÇÒÁÍÍ, ÐÏÚ×ÏÌÑÀÝÉÈ ÕÞÉÔÙ×ÁÔØ ÔÁËÉÅ ÐÒÅÄÍÅÔÎÙÅ
Ó×ÏÊÓÔ×Á, ËÁË ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØ ÏÐÅÒÁÔÏÒÏ× É ÏÂÏÂÝ£ÎÎÕÀ ÍÏÎÏÔÏÎÎÏÓÔØ
ÏÐÅÒÁÔÏÒÏ× ÐÏ ÏÔÎÏÛÅÎÉÀ Ë ÌÏÇÉÞÅÓËÉÍ ÐÒÏ×ÅÒËÁÍ (ÔÅÓÔÁÍ). 

þÔÏÂÙ
ÏËÏÎÞÁÔÅÌØÎÏ ÏÐÒÅÄÅÌÉÔØ ËÒÕÇ ÚÁÄÁÞ, ÓËÁÖÅÍ, ÞÔÏ × ÎÁÛÉÈ ÁÂÓÔÒÁËÃÉÑÈ ÍÙ
ÂÕÄÅÍ ÏÔ×ÌÅËÁÔØÓÑ ÏÔ ×ÎÕÔÒÅÎÎÅÇÏ ÕÓÔÒÏÊÓÔ×Ï ÏÐÅÒÁÔÏÒÏ× É ÐÒÏ×ÅÒÏË
(ÔÅÓÔÏ×), ÉÚ ËÏÔÏÒÙÈ ÓÏÓÔÁ×ÌÑÅÔÓÑ ÐÒÏÇÒÁÍÍÁ ËÁË Ä×ÕÓÔÏÒÏÎÎÑÑ ÓÕÝÎÏÓÔØ,
\te ÂÕÄÅÍ ×ÉÄÅÔØ ÏÐÅÒÁÔÏÒÙ É ÔÅÓÔÙ ËÁË
ÓÉÎÔÁËÓÉÞÅÓËÉ ÎÅÄÅÌÉÍÙÅ É ÓÅÍÁÎÔÉÞÅÓËÉ ÎÉ Ë ÞÅÍÕ ÎÅ Ó×ÏÄÉÍÙÅ. 
îÁ ÜÔÏÔ ÈÁÒÁËÔÅÒ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ ÁÂÓÔÒÁËÃÉÊ ÍÙ ÂÕÄÅÍ ÓÓÙÌÁÔØÓÑ ÓÌÏ×ÁÍÉ
\emph{ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÁÑ ÁÂÓÔÒÁËÔÎÁÑ ÐÒÏÇÒÁÍÍÁ} ÉÌÉ \tING{ÁÂÓÔÒÁËÔÎÁÑ
  ÐÒÏÇÒÁÍÍÁ 0\dÐÏÒÑÄËÁ} (× ÐÒÏÔÉ×Ï×ÅÓ ÓÌÕÞÁÀ \emph{1-ÇÏ ÐÏÒÑÄËÁ}, ÇÄÅ
× ÕÓÔÒÏÊÓÔ×Å ÐÒÏÇÒÁÍÍÙ ÅÓÔØ ÐÅÒÅÍÅÎÎÙÅ, ÐÒÅÄÉËÁÔÙ, ÆÕÎËÃÉÉ É ÓÏÓÔÁ×ÎÙÅ
ÔÅÒÍÙ, Ñ×ÌÑÀÝÉÅÓÑ ÏÐÅÒÁÔÏÒÁÍÉ).

îÁ ÐÒÅÄÍÅÔÎÏÍ ÕÒÏ×ÎÅ, ËÏÎÅÞÎÏ ÖÅ, Ó×ÏÊÓÔ×Á ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ É
ÍÏÎÏÔÏÎÎÏÓÔÉ ÉÍÅÀÔ <<ÏÂßÑÓÎÅÎÉÑ>> ×Ï ×ÎÕÔÒÅÎÎÅÍ ÕÓÔÒÏÊÓÔ×Å ÏÐÅÒÁÔÏÒÏ×
É ÌÏÇÉÞÅÓËÉÈ ÐÒÏ×ÅÒÏË (ÔÅÓÔÏ×). ÷×ÉÄÕ ÔÏÇÏ, ÞÔÏ ÎÁÛÉ ÁÂÓÔÒÁËÃÉÉ
<<0\dÐÏÒÑÄËÁ>>, ÎÁÍ ÏÎÉ ÄÏÓÔÕÐÎÙ ÎÁ ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ ÔÏÌØËÏ ËÁË ÎÉ
ÏÔ ÞÅÇÏ ÎÅ ÚÁ×ÉÓÉÍÙÅ ×ÎÅÛÎÉÅ \tING{ÓÅÍÁÎÔÉÞÅÓËÉÅ ÐÏÓÔÕÌÁÔÙ}. íÅÔÁÔÅÏÒÉÉ
ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ 0\dÐÏÒÑÄËÁ × ÐÒÉÓÕÔÓÔ×ÉÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×
ÐÏÓ×ÑÝÅÎÙ çÌÁ×Ù~\ref{cha:hypo-plain} É~\ref{cha:hypo-withTests}.

\paragraph{ëÏÎËÒÅÔÎÙÅ ÐÒÉÍÅÒÙ.}
ðÒÉ×ÅÄ£Í ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ× ËÏÎËÒÅÔÎÙÈ ÐÏÓÔÁÎÏ×ÏË ÚÁÄÁÞ Ï ÐÒÏÂÌÅÍÅ
ÜË×É×ÁÌÅÎÔÎÏÓÔÉ\T ÔÏÇÏ ÒÏÄÁ, ËÏÔÏÒÙÊ ÎÁÓ ÂÕÄÅÔ ÉÎÔÅÒÅÓÏ×ÁÔØ.

÷ÏÏÂÝÅ, ËÏÎËÒÅÔÎÁÑ ÐÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞÉ Ó×ÑÚÁÎÁ Ó ×ÙÂÏÒÏÍ ËÏÎËÒÅÔÎÏÊ
ÁÂÓÔÒÁËÔÎÏÊ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ ÉÌÉ ÓÅÍÅÊÓÔ×Á ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÅÊ
ÐÒÏÇÒÁÍÍ. ôÁËÏÅ ÓÅÍÅÊÓÔ×Ï ÂÕÄÅÔ ÏÐÉÓÁÎÏ ÄÁÌØÛÅ: Á ÓÌÅÄÕÀÝÅÍ ÐÁÒÁÇÒÁÆÅ
××ÅÄÅÎÉÑ É × ÏÓÎÏ×ÎÏÊ ÞÁÓÔÉ ÒÁÂÏÔÙ. 
ôÕÔ ÍÙ ÔÏÌØËÏ ÐÏËÁÖÅÍ ÎÅÓËÏÌØËÏ <<×ÎÅÛÎÉÈ>> ÐÏ ÏÔÎÏÛÅÎÉÀ Ë
ÏÓÎÏ×ÎÏÊ ÞÁÓÔÉ ÐÒÉÍÅÒÏ×, ×ÁÖÎÙÈ ËÁË ÚÁÄÁÀÝÉÈ ÎÁÐÒÁ×ÌÅÎÉÑ ÎÁÛÉÈ
ÉÓÓÌÅÄÏ×ÁÎÉÊ.

\begin{description}
\item[ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ 
  ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÍÎÏÇÏÌÅÎÔÏÞÎÙÈ Á×ÔÏÍÁÔÏ×] 
  üÔÏÔ ×ÉÄ ÁÂÓÔÒÁËÔÎÙÈ ×ÙÞÉÓÌÉÔÅÌØÎÙÈ ÍÁÛÉÎ\T \tNDNo{ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ
  ÍÎÏÇÏÌÅÎÔÏÞÎÙÅ Á×ÔÏÍÁÔÙ (DMTA)}\T ×ÐÅÒ×ÙÅ ÐÒÅÄÌÏÖÅÎ Ë
  ÉÚÕÞÅÎÉÀ  ×~\cite{RS}. 
  çÏÒÁÚÄÏ ÐÏÚÖÅ ×~\cite{HK} ÂÙÌÏ ÄÏËÁÚÁÎÏ ÕÔ×ÅÒÖÄÅÎÉÅ Ï 
  ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DMTA, ÐÒÉ ÜÔÏÍ ÉÚÌÏÖÅÎÉÅ ÂÙÌÏ ÏÓÎÏ×ÁÎÏ 
  ÎÁ ÏÐÉÓÁÎÉÉ ÉÈ ÓÅÍÁÎÔÉËÉ × ÄÒÕÇÉÈ ÔÅÒÍÉÎÁÈ (ÁÌÇÅÂÒÁÉÞÅÓËÉÈ).

  ðÏËÁÖÅÍ, ÐÏÞÅÍÕ ÜÔÏÔ ÐÒÉÍÅÒ ÐÏÐÁÄÁÅÔ × ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÅ ÎÁÍÉ
  ÓÌÕÞÁÉ. 

  íÎÏÇÏÌÅÎÔÏÞÎÙÊ Á×ÔÏÍÁÔ ÒÁÂÏÔÁÅÔ, ÎÅÚÁ×ÉÓÉÍÏ 
  ÐÅÒÅÍÅÝÁÑÓØ ÐÏ ÎÅÓËÏÌØËÉÍ ÌÅÎÔÁÍ ×  ÏÄÎÏÍ ÎÁÐÒÁ×ÌÅÎÉÉ, ÞÉÔÁÑ ÎÁ
  ËÁÖÄÏÍ ÛÁÇÅ ÏÄÎÕ ÂÕË×Õ Ó ÔÅËÕÝÅÊ ÐÏÚÉÃÉÉ ÎÁ ÏÄÎÏÊ ÉÚ ÌÅÎÔ.

  ðÏÓÍÏÔÒÉÍ ÎÁ (ÓÉÎÔÁËÓÉÞÅÓËÏÅ) ÕÓÔÒÏÊÓÔ×Ï 
  ÍÎÏÇÏÌÅÎÔÏÞÎÏÇÏ Á×ÔÏÍÁÔÁ ÔÁË. åÓÔØ \tNDNo{ÏÐÅÒÁÔÏÒÙ} ÛÁÇÁ ÄÌÑ ËÁÖÄÏÊ
  ÌÅÎÔÙ. ïÎÉ ËÏÍÍÕÔÁÔÉ×ÎÙ (ÎÅ×ÁÖÎÏ, ÓÄÅÌÁÌÉ ÍÙ ÓÎÁÞÁÌÁ ÛÁÇ ÎÁ ÐÅÒ×ÏÊ
  ÌÅÎÔÅ, Á ÐÏÔÏÍ\T ÎÁ ×ÔÏÒÏÊ, ÉÌÉ ÎÁÏÂÏÒÏÔ). åÓÔØ ÐÒÏ×ÅÒËÉ
  (\tNDNo{ÔÅÓÔÙ})
  ÔÏÇÏ, ËÁËÁÑ
  ÂÕË×Á ÎÁÐÉÓÁÎÁ × ÔÅËÕÝÅÊ ÐÏÚÉÃÉÉ ÄÌÑ ËÁÖÄÏÊ ÉÚ ÌÅÎÔ. ïÐÅÒÁÔÏÒ,
  ËÏÔÏÒÙÊ ÄÅÌÁÅÔ ÛÁÇ ÎÁ ÄÒÕÇÏÊ ÌÅÎÔÅ, ÎÉËÁË ÎÅ ÉÚÍÅÎÑÅÔ ÚÎÁÞÅÎÉÅ ÜÔÏÊ
  ÐÒÏ×ÅÒËÉ. ÷ ÎÁÛÅÍ ÆÏÒÍÁÌÉÚÍÅ ÜÔÏ ÂÕÄÅÔ ×ÙÒÁÖÅÎÏ
  × ðÒÉÍÅÒ~\ref{ex:nmta-KA-KAT}.

  ôÒÁÄÉÃÉÏÎÎÏ ×Ó£ ÖÅ × ôÅÏÒÉÉ Á×ÔÏÍÁÔÏ× ÕÓÔÒÏÊÓÔ×Ï ÍÎÏÇÏÌÅÎÔÏÞÎÏÇÏ
  Á×ÔÏÍÁÔÁ ÐÒÅÄÓÔÁ×ÌÑÀÔ ÓÅÂÅ ÎÅÍÎÏÇÏ ÐÏ-ÄÒÕÇÏÍÕ. ÷ ÔÅÈ ÔÅÒÍÉÎÁÈ,
  ËÏÔÏÒÙÅ ÍÙ ÐÒÉÎÑÌÉ, ÍÏÖÎÏ ÓËÁÚÁÔØ ÔÁË:
  äÌÑ ËÁÖÄÏÊ
  ÌÅÎÔÙ É ËÁÖÄÏÊ ÂÕË×Ù × Á×ÔÏÍÁÔÅ ÍÏÖÅÔ ÓÔÏÑÔØ ÏÐÅÒÁÔÏÒ, ÓÅÍÁÎÔÉËÁ
  ËÏÔÏÒÏÇÏ\T ÞÔÅÎÉÅ Ó ÌÅÎÔÙ ÉÍÅÎÎÏ ÜÔÏÊ ÂÕË×Ù, ÅÓÌÉ ÏÎÁ ÔÁÍ
  ÚÁÐÉÓÁÎÁ. ðÒÏ×ÅÒÏË (ÔÅÓÔÏ×)
  ÎÅÔ. (åÓÌÉ ÂÕË×Á ÎÅ ÔÁ, ×ÙÐÏÌÎÅÎÉÅ ÏÐÅÒÁÔÏÒÁ ÓÞÉÔÁÅÔÓÑ ÎÅÕÄÁÞÎÙÍ.)
  á×ÔÏÍÁÔ ÓÏÓÔÁ×ÌÅÎ ÉÚ ÔÁËÉÈ ÏÐÅÒÁÔÏÒÏ× Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÚÎÁËÁ
  \tNDNo{ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÇÏ ×ÙÂÏÒÁ}(ÏÂÙÞÎÏ $+$). 
  ôÁËÏÊ Á×ÔÏÍÁÔ ×Ó£ ÖÅ ÓÞÉÔÁÅÔÓÑ
  \tNDNo{ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÍ}, ÅÓÌÉ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÍ ×ÙÂÏÒÏÍ × Á×ÔÏÍÁÔÅ
  ÓÏÅÄÉÎÅÎÙ ÔÏÌØËÏ ÏÐÅÒÁÔÏÒÙ Ó ×ÚÁÉÍÏÉÓËÌÀÞÁÀÝÉÍ ÕÓÐÅÛÎÙÍ ×ÙÐÏÌÎÅÎÉÅÍ.
  ÷ÏÚÍÏÖÎÏ, ÂÏÌÅÅ ÉÎÔÕÉÔÉ×ÎÏ ÐÏÎÑÔÎÙÍ ÐÒÉ ÔÁËÏÍ ×ÚÇÌÑÄÅ ÎÁ ÒÁÂÏÔÕ
  Á×ÔÏÍÁÔÁ ÂÙÌÏ ÂÙ ÓÌÏ×Ï ÎÅ \emph{ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÊ}, Á
  \tNDNo{ÏÄÎÏÚÎÁÞÎÙÊ} × ÓÍÙÓÌÅ, ÞÔÏ ×ÓÅÇÄÁ ÅÓÔØ ÏÄÉÎ ×ÏÚÍÏÖÎÙÊ ÐÕÔØ
  ÕÓÐÅÛÎÏÇÏ ×ÙÐÏÌÎÅÎÉÑ. (÷ÐÒÏÞÅÍ, ÉÎÔÕÉÔÉ×ÎÏÅ ÐÏÎÉÍÁÎÉÅ ÅÇÏ ËÁË
  ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÇÏ ×ÏÚ×ÒÁÝÁÅÔÓÑ, ÅÓÌÉ ÐÏÄÕÍÁÔØ Ï ÜÔÉÈ ÏÐÅÒÁÔÏÒÁÈ
  ËÁË Ï ÐÒÏ×ÅÒËÁÈ, ÏÐÒÅÄÅÌÑÀÝÉÈ ÄÁÌØÎÅÊÛÉÊ ÈÏÄ ÒÁÂÏÔÙ Á×ÔÏÍÁÔÁ ÎÁ
  ËÁÖÄÏÍ ÏÞÅÒÅÄÎÏÍ ÛÁÇÅ.)
  ëÏÍÍÕÔÁÔÉ×ÎÏÓÔØ ÔÕÔ ÐÒÉÓÕÔÓÔ×ÕÅÔ ÍÅÖÄÕ ÏÐÅÒÁÔÏÒÁÍÉ, ÏÔÎÏÓÑÝÉÍÉÓÑ Ë
  ÒÁÚÎÙÍ ÌÅÎÔÁÍ. üÔÏÔ ×ÚÇÌÑÄ ÏÔÒÁÖ£Î × òÁÚÄÅÌÅ~\ref{def:monoid-hypo}.

\item[ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ 
  ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÈ ÐÒÏÇÒÁÍÍ ÎÁ ÛËÁÌÁÈ ëÒÉÐËÅ] (Ó
  ÄÏÐÕÝÅÎÉÑÍÉ Ï ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ É ÍÏÎÏÔÏÎÎÏÓÔÉ) ÏÐÉÓÁÎÁ, ÎÁÐÒÉÍÅÒ, ×
  \cite{Zakh-efficient-conserv}, 
  \cite{kurs4,ciaa-commut-monot,dm6-pcommut-monot}\T 
  ÐÒÅÄÛÅÓÔ×Ï×Á×ÛÉÈ ÎÁÛÅÊ ÒÁÂÏÔÁÈ. 
%%   ôÁËÏÊ ×ÉÄ
%%   ÐÒÏÇÒÁÍÍ É ÓÅÍÁÎÔÉËÉ ÂÙÌ ××ÅģΠ×~\cite{??}; 
  ûËÁÌÙ
  ëÒÉÐËÅ ÐÏÄÏÂÎÙÍ ÏÂÒÁÚÏÍ ÉÓÐÏÌØÚÕÀÔÓÑ × ÏÐÒÅÄÅÌÅÎÉÉ ÓÅÍÁÎÔÉËÉ ÄÉÎÁÍÉÞÅÓËÏÊ
  ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÌÏÇÉËÉ \cite{Harel-DL,Harel-DLnew}.

  ûËÁÌÁ ëÒÉÐËÅ ×ËÌÀÞÁÅÔ × ÓÅÂÑ (ÂÅÓËÏÎÅÞÎÏÅ) ÍÎÏÖÅÓÔ×Ï ×ÏÚÍÏÖÎÙÈ
  ÓÏÓÔÏÑÎÉÊ ×ÙÞÉÓÌÉÔÅÌØÎÏÇÏ ÕÓÔÒÏÊÓÔ×Á É ÐÒÁ×ÉÌÁ ÉÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ ÐÏÄ
  ÄÅÊÓÔ×ÉÅÍ ÏÐÅÒÁÔÏÒÏ×. ôÁËÖÅ ËÁÖÄÁÑ ÏÔÄÅÌØÎÁÑ ÛËÁÌÁ\footnote{÷
  ÔÅÒÍÉÎÏÌÏÇÉÉ, ÐÒÉÎÑÔÏÊ × ÄÁÎÎÏÊ ÒÁÂÏÔÅ. ïÎÁ ÍÏÖÅÔ ÏÔÌÉÞÁÔØÓÑ ÏÔ
  ÔÅÒÍÉÎÏÌÏÇÉÊ ÄÒÕÇÉÈ ÒÁÂÏÔ, ËÏÔÏÒÙÅ, ÏÄÎÁËÏ, ÎÅ ÎÁÓÔÏÌØËÏ ÕÓÔÏÑ×ÛÉÅÓÑ
  ÞÔÏÂÙ ÓÌÕÖÉÔØ Ô×£ÒÄÏÊ ÐÒÉÍÅÒÏÍ ÔÏÇÏ, ËÁË ÞÔÏ ÎÁÚÙ×ÁÔØ.}  
  ÚÁÄÁ£Ô ÚÎÁÞÅÎÉÑ
  ÌÏÇÉÞÅÓËÉÈ ÐÒÏ×ÅÒÏË (ÔÅÓÔÏ×) × ËÁÖÄÏÍ ÓÏÓÔÏÑÎÉÉ. ÷ÙÞÉÓÌÅÎÉÅ
  ÐÒÏÇÒÁÍÍÙ\T ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÅÒÅÈÏÄÏ× ÉÚ ÓÏÓÔÏÑÎÉÑ × ÓÏÓÔÏÑÎÉÅ ×
  ÔÁËÏÊ ÛËÁÌÅ, ÕÐÒÁ×ÌÑÅÍÁÑ ËÏÄÏÍ ÐÒÏÇÒÁÍÍÙ.

  ðÏÎÑÔÎÏ, ÞÔÏ ÜÔÏ ÄÏ×ÏÌØÎÏ ÏÂÝÉÊ ÐÏÄÈÏÄ Ë ÐÏÓÔÒÏÅÎÉÀ ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÅÊ
  ÐÒÏÇÒÁÍÍ, ÏÎ ÏÔ×ÅÞÁÅÔ ÎÁÛÅÍÕ ÏÂÝÅÍÕ ÉÎÔÕÉÔÉ×ÎÏÍÕ ÐÒÅÄÓÔÁ×ÌÅÎÉÀ Ï
  ÔÏÍ, ËÁË ÐÒÏÉÓÈÏÄÑÔ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ ×ÙÞÉÓÌÅÎÉÑ (Á ÚÎÁÞÉÔ, ÂÕÄÅÔ
  ÎÅÕÄÉ×ÉÔÅÌØÎÏ ÅÓÌÉ ÎÅËÏÔÏÒÙÅ ÄÒÕÇÉÅ ÆÏÒÍÁÌØÎÙÅ ÁÂÓÔÒÁËÔÎÙÅ ÍÏÄÅÌÉ
  ÐÒÏÇÒÁÍÍ É ×ÙÞÉÓÌÅÎÉÊ ÕÄÁÓÔÓÑ × Î£Í ÐÒÏÍÏÄÅÌÉÒÏ×ÁÔØ). 
  æÏÒÍÁÌØÎÏ ÏÎ ÕÞԣΠïÐÒÅÄÅÌÅÎÉÅÍ~\ref{def:SIMPLET-under-E}
  ÎÁÓÔÏÑÝÅÊ ÒÁÂÏÔÙ. 
\end{description}

\paragraph{ïÂÝÁÑ ÐÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞÉ, ÉÓÓÌÅÄÕÅÍÏÊ × ÄÁÎÎÏÊ ÒÁÂÏÔÅ.}
\label{sec:intro-problems}
íÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ÐÒÏÂÌÅÍÕ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ × ÓÅÍÁÎÔÉËÁÈ,
ÏÓÎÏ×ÁÎÎÙÈ ÎÁ \tNDNo{ÁÌÇÅÂÒÁÈ ëÌÉÎÉ} 
\cite{??}
É \tNDNo{ÁÌÇÅÂÒÁÈ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ}
\cite{KAT-complete-decidable}. 
úÁÍÅÔÉÍ, 
ÞÔÏ × ÜÔÉÈ ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÓÉÓÔÅÍÁÈ ÐÏÓÔÕÌÉÒÕÀÔÓÑ ËÒÁÊÎÅ ÏÂÝÉÅ Ó×ÏÊÓÔ×Á,
ËÏÔÏÒÙÅ ÍÙ ÍÏÖÅÍ ÏÖÉÄÁÔØ ÏÔ ÐÒÏÃÅÓÓÏ× ×ÙÞÉÓÌÅÎÉÑ (ÒÅÁÌØÎÙÈ) ÐÒÏÇÒÁÍÍ
×ÍÅÓÔÅ Ó ÒÅÚÕÌØÔÁÔÁÍÉ ÜÔÉÈ ×ÙÞÉÓÌÅÎÉÊ. 

éÔÁË, ÐÏ ÐÏÒÑÄËÕ, ÐÏÌÎÁÑ ÐÏÓÔÁÎÏ×ËÁ ÉÎÔÅÒÅÓÕÀÝÉÈ ÎÁÓ ×ÏÐÒÏÓÏ×.

\begin{itemize}
\item 
áÂÓÔÒÁËÃÉÉ <<0\dÇÏ ÐÏÒÑÄËÁ>>.

\item 
óÉÎÔÁËÓÉÞÅÓËÉ ÐÒÏÇÒÁÍÍÙ × ÎÁÛÉÈ ÁÂÓÔÒÁËÃÉÑÈ ÐÏ ÓÕÔÉ Ä×ÕÈ ×ÉÄÏ×:
\begin{itemize}
\item 
\tING{ÚÁÐÉÓÁÎÎÙÅ <<ÌÉÎÅÊÎÏ>>} (× ÓÔÒÏËÕ, ÔÁË, ËÁË ÜÔÏ ÏÂÙÞÎÏ Ó ÐÒÏÓÔÙÍÉ ÐÒÏÇÒÁÍÍÁÍÉ,
ÚÁÐÉÓÁÎÎÙÍÉ ÎÁ ËÁËÏÍ-ÔÏ ÑÚÙËÅ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ)\T 
\tND{ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ Ó ÔÅÓÔÁÍÉ}{def:regexp-t};
\item ÐÒÅÄÓÔÁ×ÌÅÎÎÙÅ × ×ÉÄÅ ÇÒÁÆÁ (ÔÁË ÞÁÓÔÏ ÍÙÓÌÑÔÓÑ ËÏÎÅÞÎÙÅ
  Á×ÔÏÍÁÔÙ, Á ÔÁËÖÅ ÂÌÏË-ÓÈÅÍÙ ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ), \tING{ÓÈÅÍÙ}\T
  \tND{ÓÈÅÍÙ Ó ÔÅÓÔÁÍÉ}{def:schemes-t}.
\end{itemize}

\item ðÒÏÇÒÁÍÍÙ ÉÎÔÅÒÐÒÅÔÉÒÕÀÔÓÑ × \tND{ÁÌÇÅÂÒÁÈ ëÌÉÎÉ}{def:KA} 
  ÉÌÉ \tND{ÁÌÇÅÂÒÁÈ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ}{def:KAT}.

\item ëÏÍÍÕÔÁÔÉ×ÎÏÓÔØ É ÍÏÎÏÔÏÎÎÏÓÔØ\T ÓÅÍÁÎÔÉÞÅÓËÉÅ ÐÏÓÔÕÌÁÔÙ,
  ËÏÔÏÒÙÅ ÎÁËÌÁÄÙ×ÁÀÔ ÄÏÐÏÌÎÉÔÅÌØÎÙÅ ÏÇÒÁÎÉÞÅÎÉÑ ÎÁ ÁÌÇÅÂÒÙ.

\item üË×É×ÁÌÅÎÔÎÏÓÔØ ÐÒÏÇÒÁÍÍ\T ÒÁ×ÅÎÓÔ×Ï ÉÎÔÅÒÐÒÅÔÁÃÉÊ ÐÒÏÇÒÁÍÍ ×
  ÎÅËÏÔÏÒÏÍ ËÌÁÓÓÅ ÁÌÇÅÂÒ ëÌÉÎÉ (Ó ÔÅÓÔÁÍÉ).

\item îÁÓ ÉÎÔÅÒÅÓÕÅÔ ÒÁÚÒÅÛÉÍÏÓÔØ ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ\T ÍÙ
  ÇÏ×ÏÒÉÍ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ÜË×ÁÃÉÏÎÁÌØÎÙÈ ÔÅÏÒÉÊ ËÌÁÓÓÏ× ÁÌÇÅÂÒ ëÌÉÎÉ (Ó
  ÔÅÓÔÁÍÉ), ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÐÒÉÎÑÔÙÍ ÓÅÍÁÎÔÉÞÅÓËÉÍ ÐÏÓÔÕÌÁÔÁÍ.

  æÏÒÍÕÌÉÒÏ×ËÕ ÐÒÏÂÌÅÍÙ
  ÜË×É×ÁÌÅÎÔÎÏÓÔÉ, ÐÒÉÎÑÔÕÀ ÎÁÍÉ ÚÁ ÏÓÎÏ×ÎÕÀ, ÓÍ.\ ×
  ïÐÒÅÄÅÌÅÎÉÑÈ~\ref{def:KA-Equa}, \ref{def:KAT-Equa}, \ref{def:KA-Horn},
  \ref{def:KAT-Horn}.

\item 
  \label{2-problems}
  íÙ ÈÏÔÉÍ ÎÁÊÔÉ ÕÓÌÏ×ÉÑ ÎÁ ×ÉÄ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×, ×ÙÒÁÖÁÀÝÉÈ
  ÞÁÓÔÉÞÎÕÀ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØ ÏÐÅÒÁÔÏÒÏ× É ÏÂÏÂÝ£ÎÎÕÀ ÍÏÎÏÔÏÎÎÏÓÔØ,
  ÎÅÏÂÈÏÄÉÍÙÅ É ÄÏÓÔÁÔÏÞÎÙÅ ÄÌÑ ÒÁÚÒÅÛÉÍÏÓÔÉ ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
  ÐÒÏÇÒÁÍÍ (× ÓÅÍÁÎÔÉËÅ, ÏÓÎÏ×ÁÎÎÏÊ ÎÁ ËÌÁÓÓÅ ÁÌÇÅÂÒ ëÌÉÎÉ (Ó
  ÔÅÓÔÁÍÉ), ÏÔ×ÅÞÁÀÝÅÍ ÜÔÉÍ ÓÅÍÁÎÔÉÞÅÓËÉÍ ÐÏÓÔÕÌÁÔÁÍ). üÔÁ ÚÁÄÁÞÁ ÍÏÖÅÔ
  ÂÙÔØ ÕÔÏÞÎÅÎÁ Ä×ÕÍÑ ÏÂÒÁÚÁÍÉ:
  \begin{enumerate}
  \item ðÒÏÂÌÅÍÁ 1: 
    \begin{quote}
      \emph{<<îÁ ×ÈÏÄ ÐÏÄÁÀÔÓÑ Ä×Å ÐÒÏÇÒÁÍÍÙ. ïÐÒÅÄÅÌÉÔØ,
        ÜË×É×ÁÌÅÎÔÎÙ ÌÉ ÏÎÉ ÐÒÉ ÄÏÐÕÝÅÎÉÑÈ $\Phi$.>>} 
    \end{quote}
    $\Phi$\T ÎÅÉÚÍÅÎÎÙÊ
    ÄÌÑ ËÁÖÄÏÇÏ ÁÌÇÏÒÉÔÍÁ, ÒÅÛÁÀÝÅÇÏ ÐÒÏÂÌÅÍÕ,
    ÎÁÂÏÒ ÄÏÐÕÝÅÎÉÊ (ÆÏÒÍÕÌ), ÏÔ×ÅÞÁÀÝÉÊ ÐÒÉÎÑÔÙÍ ÓÅÍÁÎÔÉÞÅÓËÉÍ
    ÐÏÓÔÕÌÁÔÁÍ. ÷ÏÐÒÏÓ: ÐÒÉ ËÁËÉÈ $\Phi$ ÐÒÏÂÌÅÍÁ ÒÁÚÒÅÛÉÍÁ, Á ÐÒÉ
    ËÁËÉÈ\T ÎÅÔ. ïÔ×ÅÔÏÍ ÍÏÖÅÔ ÂÙÔØ ÎÅËÏÔÏÒÙÊ ËÌÁÓÓ $\thclass c = \{
      \Phi_1, \Phi_2, \dotsc \}$   ÄÏÐÕÝÅÎÉÊ.

    ðÏÌÎÙÍ ÏÔ×ÅÔÏÍ ÂÕÄÅÔ ÔÁËÏÊ ËÌÁÓÓ $\thclass c$, ÍÁËÓÉÍÁÌØÎÙÊ ÐÏ ×ÌÏÖÅÎÉÀ.
  \item ðÒÏÂÌÅÍÁ 2: 
    \begin{quote}
    \emph{<<îÁ ×ÈÏÄ ÐÏÄÁÀÔÓÑ ÄÏÐÕÝÅÎÉÑ~$\Phi$ ÉÚ ËÌÁÓÓÁ
    $\thclass c$ É Ä×Å ÐÒÏÇÒÁÍÍÙ. 
    ïÐÒÅÄÅÌÉÔØ, ÜË×É×ÁÌÅÎÔÎÙ ÌÉ ÏÎÉ ÐÒÉ ÄÏÐÕÝÅÎÉÑÈ $\Phi$.>>}
    \end{quote}
    $\Phi$\T ÔÏÖÅ Ñ×ÌÑÅÔÓÑ ×ÈÏÄÎÙÍÉ ÄÁÎÎÙÍÉ ÁÌÇÏÒÉÔÍÁ. 
    $\thclass c$\T ÎÅÉÚÍÅÎÎÙÊ  ÄÌÑ ËÁÖÄÏÇÏ ÁÌÇÏÒÉÔÍÁ, ÒÅÛÁÀÝÅÇÏ ÐÒÏÂÌÅÍÕ.
    ÷ÏÐÒÏÓ: ÐÒÉ \emph{ËÁËÏÇÏ ×ÉÄÁ} ÄÏÐÕÓÔÉÍÙÈ $\Phi$ ÐÒÏÂÌÅÍÁ ÒÁÚÒÅÛÉÍÁ, Á ÐÒÉ
    ËÁËÏÇÏ\T ÕÖÅ ÎÅÔ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÐÒÉ ËÁËÉÈ $\thclass c$ ÐÒÏÂÌÅÍÁ ÒÁÚÒÅÛÉÍÁ?
    ïÔ×ÅÔ ÄÏÌÖÅÎ ÏÐÒÅÄÅÌÉÔØ ÎÅËÏÔÏÒÏÅ ÍÎÏÖÅÓÔ×Ï ËÌÁÓÓÏ× ÄÏÐÕÝÅÎÉÊ $\{\thclass
    c_1, \thclass c_2, \dotsc, \}$, ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ËÏÔÏÒÏÇÏ ÍÙ
    ÐÏÌÕÞÁÅÍ ÒÁÚÒÅÛÉÍÕÀ ÐÒÏÂÌÅÍÕ. îÁÉÂÏÌÅÅ ÅÓÔÅÓÔ×ÅÎÎÏ 
    ÔÁËÏÅ ÍÎÏÖÅÓÔ×Ï ÚÁÄÁÔØ ÎÁÂÏÒÏÍ ÅÇÏ ÍÁËÓÉÍÁÌØÎÙÈ ÐÏ ×ÌÏÖÅÎÉÀ
    ÜÌÅÍÅÎÔÏ×. (òÁÚÒÅÛÉÍÏÓÔØ ÄÌÑ Â\'ÏÌØÛÅÇÏ ËÌÁÓÓÁ ×ÌÅÞ£Ô ÒÁÚÒÅÛÉÍÏÓÔØ
    ÄÌÑ ÍÅÎØÛÅÇÏ, ÐÏÔÏÍÕ ÞÔÏ ÁÌÇÏÒÉÔÍ ÄÌÑ Â\'ÏÌØÛÅÇÏ ËÌÁÓÓÁ ÐÒÏÓÔÏ
    ÎÉÞÅÇÏ ÎÅ ÚÁÍÅÔÉÔ, ÅÓÌÉ ÍÙ ÂÕÄÅÍ ÐÏÄÁ×ÁÔØ ÅÍÕ ÎÁ ×ÈÏÄ ÔÏÌØËÏ
    ÜÌÅÍÅÎÔÙ ÍÅÎØÛÅÇÏ.)

    ðÏÌÎÙÍ ÏÔ×ÅÔÏÍ ÂÕÄÅÔ ÚÁÄÁÎÉÅ ÍÎÏÖÅÓÔ×Á ×ÓÅÈ ËÌÁÓÓÏ× ÄÏÐÕÝÅÎÉÊ, 
    ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ËÏÔÏÒÏÇÏ ÍÙ
    ÐÏÌÕÞÁÅÍ ÒÁÚÒÅÛÉÍÕÀ ÐÒÏÂÌÅÍÕ.

  \end{enumerate}

  ëÁË ÕÖÅ ÄÏÌÖÎÏ ÂÙÔØ ÑÓÎÏ, 
  ÍÙ ÏÇÒÁÎÉÞÉ×ÁÅÍ ÏÂÌÁÓÔØ, × ËÏÔÏÒÏÊ ÎÁÓ ÜÔÉ ×ÏÐÒÏÓÙ ÉÎÔÅÒÅÓÕÀÔ, 
  ÐÏÓÔÕÌÁÔÁÍÉ, ×ÙÒÁÖÁÀÝÉÍÉ <<ÞÁÓÔÉÞÎÕÀ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØ 
  É ÏÂÏÂÝ£ÎÎÕÀ ÍÏÎÏÔÏÎÎÏÓÔØ ÏÐÅÒÁÔÏÒÏ×>>.

\item îÁÓ ÉÎÔÅÒÅÓÕÅÔ ×ÏÐÒÏÓ Ï ÓÌÏÖÎÏÓÔÉ ÒÁÚÒÅÛÅÎÉÑ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
  ÐÒÏÇÒÁÍÍ ×
  ÔÅÈ ÓÌÕÞÁÑÈ, ËÏÇÄÁ ÏÎÁ  ÒÁÚÒÅÛÉÍÁ (ÅÓÌÉ ÎÅÒÁÚÒÅÛÉÍÁ\T ÔÏ ÍÅÓÔÏ ×
  ÉÅÒÁÒÈÉÉ ÎÅÒÁÚÒÅÛÉÍÙÈ ÐÒÏÂÌÅÍ).

\item ÷ ËÁÞÅÓÔ×Å ÐÒÁËÔÉÞÅÓËÉ ÐÏÌÅÚÎÏÇÏ ÒÅÚÕÌØÔÁÔÁ ÔÁËÏÊ ÒÁÂÏÔÙ ÍÙ
  ÚÁÉÎÔÅÒÅÓÏ×ÁÎÙ × ÏÐÉÓÁÎÉÑÈ ÜÆÆÅËÔÉ×ÎÙÈ ÁÌÇÏÒÉÔÍÏ×, ÒÁÚÒÅÛÁÀÝÉÈ ðü ×
  ÉÓÓÌÅÄÏ×ÁÎÎÙÈ ÓÌÕÞÁÑÈ.

\end{itemize}

\paragraph{óÏÏÔÎÏÛÅÎÉÅ ÍÅÖÄÕ Ä×ÕÍÑ ×ÏÐÒÏÓÁÍÉ.}
ðÏÎÑÔÎÏ, ÞÔÏ ËÌÁÓÓ $\thclass c$, Ñ×ÌÑÀÝÉÊÓÑ ÏÔ×ÅÔÏÍ ÎÁ ×ÏÐÒÏÓ ÉÚ
ÐÕÎËÔÁ~1, ÎÅÏÂÑÚÁÔÅÌØÎÏ ÐÏÐÁÄ£Ô × ÍÎÏÖÅÓÔ×Ï\dÐÏÌÎÙÊ ÏÔ×ÅÔ ÎÁ ×ÏÐÒÏÓ ÉÚ
ÐÕÎËÔÁ~2. ðÏÔÏÍÕ ÞÔÏ $\thclass c$ ÄÏÐÕÓËÁÅÔ ÓÕÝÅÓÔ×Ï×ÁÎÉÅ ÒÁÚÎÙÈ
ÁÌÇÏÒÉÔÍÏ× ÄÌÑ ÒÁÚÎÙÈ $\Phi \in \thclass c$ (É ÉÈ ÈÒÁÎÅÎÉÅ × ÏÄÎÏÊ
ÐÒÏÇÒÁÍÍÅ É ×ÙÂÏÒ ÍÅÖÄÕ ÎÉÍÉ ÍÏÖÅÔ ÂÙÔØ ÎÅ×ÙÞÉÓÌÉÍÙÍ). 

úÁÔÏ ËÁÖÄÏÅ
$\Phi \in \thclass c$ ÄÁÓÔ ÜÌÅÍÅÎÔ $\{ \Phi \}$ ÏÔ×ÅÔÁ ÎÁ ×ÔÏÒÏÊ
×ÏÐÒÏÓ. $\thclass c$\T ÜÔÏ ÒÏ×ÎÏ ×ÓÅ ÍÉÎÉÍÁÌØÎÙÅ ÜÌÅÍÅÎÔÙ
ÍÎÏÖÅÓÔ×Á\dÐÏÌÎÏÇÏ ÏÔ×ÅÔÁ ÎÁ ×ÔÏÒÏÊ ×ÏÐÒÏÓ. $\thclass c$\T ÏÂßÅÄÉÎÅÎÉÅ
×ÓÅÈ ËÌÁÓÓÏ×\dÜÌÅÍÅÎÔÏ× ÐÏÌÎÏÇÏ ÏÔ×ÅÔÁ ÎÁ ×ÔÏÒÏÊ ×ÏÐÒÏÓ.

ôÅÍÁ Ó×ÑÚÉ ÍÅÖÄÕ ÜÔÉÍÉ Ä×ÕÍÑ ×ÏÐÒÏÓÁÍÉ ÏÓ×ÅÝÅÎÁ × ÏÓÎÏ×ÎÏÊ ÞÁÓÔÉ 
× ÎÁÛÉÈ ÔÅÈÎÉÞÅÓËÉÈ ÔÅÒÍÉÎÁÈ
ÎÁ ÓÔÒ.~\pageref{problems-connections} ×
òÁÚÄÅÌÅ~\ref{sec:hypo-theories}.


\paragraph{÷ÏÐÒÏÓ Ï ÐÒÉÍÅÎÉÍÏÓÔÉ ÍÅÔÏÄÏ× ÒÅÛÅÎÉÑ.} ðÏËÁ Õ ÎÁÓ ÎÅÔ
ÐÏÌÎÙÈ ÏÔ×ÅÔÏ× ÎÁ ÐÏÓÔÁ×ÌÅÎÎÙÅ ×ÏÐÒÏÓÙ, ÎÁÍ ÍÏÖÅÔ ÂÙÔØ ÉÎÔÅÒÅÓÎÏ É
ÔÁËÁÑ ÆÏÒÍÁ ÉÓÓÌÅÄÏ×ÁÎÉÑ: ÐÕÓÔØ ÍÙ ÚÎÁÅÍ ÓÐÏÓÏ ÐÏÓÔÒÏÅÎÉÑ ÁÌÇÏÒÉÔÍÁ
ÐÒÏ×ÅÒËÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ × ÎÅËÏÔÏÒÏÍ ÓÌÕÞÁÅ. ôÏÇÄÁ ÔÒÅÂÕÅÔÓÑ
ÍÁËÓÉÍÁÌØÎÏ ÒÁÓÛÉÒÉÔØ ÏÂÌÁÓÔØ ÐÒÉÍÅÎÉÍÏÓÔÉ ÜÔÏÇÏ ÓÐÏÓÏÂÁ, ÎÁÊÔÉ
ÎÅÏÂÈÏÄÉÍÙÅ É ÄÏÓÔÁÔÏÞÎÙÅ ÕÓÌÏ×ÉÑ ÔÏÇÏ, ÞÔÏ ÜÔÏÔ ÓÐÏÓÏ ÐÏÓÔÒÏÅÎÉÑ
ÁÌÇÏÒÉÔÍÁ ÄÁÓÔ ËÏÒÒÅËÔÎÙÊ É ÐÏÌÎÙÊ ÁÌÇÏÒÉÔÍ ÄÌÑ ÒÅÛÅÎÉÑ ðü. 

ôÁËÏÇÏ ÖÅ ÒÏÄÁ ×ÏÐÒÏÓÙ ÉÎÔÅÒÅÓÎÙ É Ï ÉÚ×ÅÓÔÎÙÈ ÍÅÔÏÄÁÈ ÄÏËÁÚÁÔÅÌØÓÔ×Á
ÒÁÚÒÅÛÉÍÏÓÔÉ ÉÌÉ ÎÅÒÁÚÒÅÛÉÍÏÓÔÉ. îÁÐÒÉÍÅÒ, × ËÁËÉÈ ÓÌÕÞÁÑÈ ÍÙ ÍÏÖÅÍ
ÐÒÏ×ÅÓÔÉ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü ÓÌÅÄÕÑ ÔÏÊ ÖÅ ÓÈÅÍÅ, ÞÔÏ É
\cite{HK}, ÉÓÐÏÌØÚÏ×Á×ÛÉÅ ÔÅÏÒÅÍÕ üÊÌÅÎÂÅÒÇÁ \cite{E} ÄÌÑ
ÄÏËÁÚÁÔÅÌØÓÔ×Á ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DMTA?

\paragraph{úÁÍÅÞÁÎÉÅ Ï ÓÌÉÛËÏÍ ÂÏÌØÛÏÊ ÏÂÝÎÏÓÔÉ ÁÂÓÔÒÁËÃÉÉ ÎÁ ÏÓÎÏ×Å
  ÁÌÇÅÂÒ ëÌÉÎÉ.}\todo{[ÎÁÚ×?]}
÷ ËÁÞÅÓÔ×Å ÄÅÍÏÎÓÔÒÁÃÉÉ ËÒÁÊÎÅÊ ÏÂÝÎÏÓÔÉ Ó×ÏÊÓÔ× ×ÙÞÉÓÌÅÎÉÊ ÐÒÏÇÒÁÍÍ, 
ÐÏÓÔÕÌÉÒÕÅÍÙÈ × ÜÔÉÈ ÓÉÓÔÅÍÁÈ,
ÐÒÉ×ÅÄ£Í ÔÏÔ ÆÁËÔ, ÞÔÏ ÎÅ ×Ó£, ÞÔÏ ×ÐÉÓÙ×ÁÅÔÓÑ × ÒÁÍËÉ
ÔÁËÏÊ ÓÅÍÁÎÔÉËÉ, Ñ×ÌÑÅÔÓÑ ×ÙÞÉÓÌÅÎÉÅÍ ÐÒÏÇÒÁÍÍÙ × ÎÁÛÅÍ ÏÂÙÞÎÏÍ
ÉÎÔÕÉÔÉ×ÎÏÍ ÐÏÎÉÍÁÎÉÉ, ÎÁÐÒÉÍÅÒ, ÐÒÉ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÐÒÏÇÒÁÍÍÙ\dÇÒÁÆÁ
× ÔÁË ÎÁÚÙ×ÁÅÍÏÊ \tNDNo{$(\min, +)$\dÁÌÇÅÂÒÅ ëÌÉÎÉ} ÍÙ ÐÏÌÕÞÉÍ
× ËÁÞÅÓÔ×Å ÒÅÚÕÌØÔÁÔÁ ÚÎÁÞÅÎÉÅ\T ÍÉÎÉÍÁÌØÎÕÀ ÓÔÏÉÍÏÓÔØ ÐÕÔÉ ÞÅÒÅÚ ÇÒÁÆ
(Ò£ÂÒÁÍ ÐÒÉÐÉÓÁÎÙ ÓÔÏÉÍÏÓÔÉ; ÓÍ.~ðÒÉÍÅÒ~\ref{ex:KA-minimal-cost}).

îÏ ÔÁËÉÅ ÄÁÌ£ËÉÅ ÏÔ ×ÙÞÉÓÌÅÎÉÊ ÓÌÕÞÁÉ ÎÁÓ ÐÒÁËÔÉÞÅÓËÉ ÉÎÔÅÒÅÓÏ×ÁÔØ ÎÅ
ÂÕÄÕÔ. ðÏÓÔÕÌÉÒÕÑ × ÉÓÓÌÅÄÕÅÍÙÈ ÁÌÇÅÂÒÁÈ ÂÏÌÅÅ ÓÉÌØÎÙÅ Ó×ÏÊÓÔ×Á
(ÎÁÐÒÉÍÅÒ, \tND{*-\dÎÅÐÒÅÒÙ×ÎÏÓÔØ}{def:KAc}), 
ÍÙ ÉÓËÌÀÞÁÅÍ ÜÔÉ ÓÌÕÞÁÉ.
(÷Ó£ ÖÅ, 
×Ï-ÐÅÒ×ÙÈ, ÎÅËÏÔÏÒÙÅ ÒÅÚÕÌØÔÁÔÙ ÒÁÓÐÒÏÓÔÒÁÎÑÔÓÑ ÎÁ
ÎÉÈ ÂÌÁÇÏÄÁÒÑ ÕÓÔÁÎÏ×ÌÅÎÎÙÍ ÒÁÎÅÅ ÆÁËÔÁÍ ÓÏ×ÐÁÄÅÎÉÑ Ó×ÏÊÓÔ× 
ÏÐÒÅÄÅÌ£ÎÎÏÇÏ ×ÉÄÁ ÂÏÌÅÅ
ÛÉÒÏËÏÇÏ ËÌÁÓÓÁ É ÂÏÌÅÅ ÕÚËÏÇÏ \T \sm, ÎÁÐÒÉÍÅÒ,
ôÅÏÒÅÍÕ~\ref{th:EKA-EKAc},
×Ï-×ÔÏÒÙÈ,
ÉÚÕÞÅÎÉÅ ×ÏÚÍÏÖÎÏÓÔÉ ÏÂÏÂÝÅÎÉÊ ÒÅÚÕÌØÔÁÔÏ× ÎÁ ÅÓÔÅÓÔ×ÅÎÎÏ ÏÐÒÅÄÅÌ£ÎÎÙÊ
ÂÏÌÅÅ ÛÉÒÏËÉÊ ËÌÁÓÓ
ÐÒÅÄÓÔÁ×ÌÑÅÔ ÉÎÔÅÒÅÓ.)

\paragraph{úÎÁËÏÍÓÔ×Ï Ó ×ÎÅÛÎÉÍ ×ÉÄÏÍ ÆÏÒÍÁÌÉÚÍÏ×.}
ëÁË ÕÖÅ ÇÏ×ÏÒÉÌÏÓØ, ÎÁÛÁ ÁÂÓÔÒÁËÃÉÑ <<0\dÇÏ ÐÏÒÑÄËÁ>>.
îÁ ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ ÜÔÁ ÐÒÉÒÏÄÁ ÁÂÓÔÒÁËÃÉÊ ÈÏÒÏÛÏ ÚÁÍÅÔÎÁ: ×
ÓÉÎÔÁËÓÉÓÅ ÕÞÁÓÔ×ÕÀÔ ÏÐÅÒÁÔÏÒÙ
É ÔÅÓÔÙ, ÏÂÏÚÎÁÞÅÎÎÙÅ ÐÒÏÓÔÏ ÂÕË×ÁÍÉ (ÎÅÄÅÌÉÍÙ ÓÉÎÔÁËÓÉÞÅÓËÉ), ÎÁÐÒÉÍÅÒ:
\begin{align*}
  &a, b, c, \dotsc,
  &
  &p, q, \dotsc
\end{align*}
\T ÎÁÚ×ÁÎÎÙÅ \tNDNo{ÂÁÚÏ×ÙÍÉ ÏÐÅÒÁÔÏÒÁÍÉ} É \tNDNo{ÂÁÚÏ×ÙÍÉ ÔÅÓÔÁÍÉ}\T
\sm ïÐÒÅÄÅÌÅÎÉÑ~\ref{def:regexp} É \ref{def:regexp-t}, × ÓÅÍÁÎÔÉËÅ
×ÁÖÎÏ ÚÁÄÁÎÉÅ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ× É ÔÅÓÔÏ×\T
\sm ïÐÒÅÄÅÌÅÎÉÑ~\ref{def:regexp-interp} É \ref{def:regexp-t-interp}.

óÅÍÁÎÔÉÞÅÓËÉÅ Ó×ÏÊÓÔ×Á, ÔÉÐÁ ÉÚÕÞÁÅÍÙÈ ÎÁÍÉ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ É ÍÏÎÏÔÏÎÎÏÓÔÉ,
ÄÏÓÔÕÐÎÙ  
ËÁË \tDJust{ÓÅÍÁÎÔÉÞÅÓËÉÅ ÐÏÓÔÕÌÁÔÙ}. îÁ
ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ ÍÙ ÐÒÅÄÓÔÁ×ÌÑÅÍ ÜÔÉ ÄÏÐÕÝÅÎÉÑ Ï ÓÅÍÁÎÔÉËÅ
× ×ÉÄÅ ÆÏÒÍÕÌ ×ÒÏÄÅ:
\begin{align*}
  ab &= ba,
  &
  pa\n{p} = 0.
\end{align*}
(\Sm ïÐÒÅÄÅÌÅÎÉÑ~\ref{def:thclasses} É \ref{def:thclasses-t}.)
ðÅÒ×ÁÑ ÓÌÕÖÉÔ ÄÌÑ ÏÂÏÚÎÁÞÅÎÉÑ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ $a$ É $b$, 
×ÔÏÒÁÑ\T ÍÏÎÏÔÏÎÎÏÓÔÉ ÏÐÅÒÁÔÏÒÁ~$a$ ÐÏ ÏÔÎÏÛÅÎÉÀ Ë ÔÅÓÔÕ~$p$ ($0$\T
<<ÎÅ×ÏÚÍÏÖÎÏÓÔØ ÕÓÐÅÛÎÏÇÏ ×ÙÐÏÌÎÅÎÉÑ ÔÁËÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
ÄÅÊÓÔ×ÉÊ>>, × ÄÁÎÎÏÍ ÐÒÉÍÅÒÅ, ÔÏÊ, 
ÐÒÉ ËÏÔÏÒÏÊ ÚÎÁÞÅÎÉÅ $p$ ÐÏÍÅÎÑÅÔÓÑ Ó $\True$ ÎÁ $\False$; 
ÓÕÔØ ÜÔÉÈ ÆÏÒÍÕÌ ÍÏÖÎÏ ÌÕÞÛÅ ÐÏÎÑÔØ ÐÏÓÌÅ ÚÎÁËÏÍÓÔ×Á Ó
ÏÓÎÏ×ÎÙÍ ÔÅÈÎÉÞÅÓËÉÍ ÓÒÅÄÓÔ×ÏÍ ÜÔÏÊ ÒÁÂÏÔÙ\T ÁÌÇÅÂÒÁÍÉ ëÌÉÎÉ É
ÁÌÇÅÂÒÁÍÉ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ). åÓÌÉ ÂÙ ÍÙ ÒÁÂÏÔÁÌÉ Ó ÓÅÍÁÎÔÉËÏÊ ÎÁ ÏÓÎÏ×Å
ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÛËÁÌ ëÒÉÐËÅ \cite{ciaa-commut-monot}, 
ÔÏ ÔÅ ÖÅ ÓÁÍÙÅ ÐÏ ÓÍÙÓÌÕ ÄÏÐÕÝÅÎÉÑ ÍÏÇÌÉ ÂÙ ÂÙÔØ ÚÁÐÉÓÁÎÙ
ËÁË ÁËÓÉÏÍÙ ÄÉÎÁÍÉÞÅÓËÏÊ ÌÏÇÉËÉ \cite{Harel-DL,Harel-DLnew}: 
\begin{align*}
  \langle a; b \rangle \bt s  &= \langle b; a\rangle \bt s,
  &
  p \implic \langle a\rangle p.
\end{align*}
÷ÏÏÂÝÅ ÜË×ÁÃÉÏÎÁÌØÎÁÑ ÔÅÏÒÉÑ ÁÌÇÅÂÒ ëÌÉÎÉ (Ó ÔÅÓÔÁÍÉ) 
Ó×ÏÄÉÔÓÑ Ë \tNDNo{ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÄÉÎÁÍÉÞÅÓËÏÊ ÌÏÇÉËÅ} 
\cite{KAT-complete-decidable}. 
îÏ ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÉÍÅÎÎÏ \KAT
ËÁË ÑÚÙËÁ ÎÁÛÅÊ ÒÁÂÏÔÙ, Á ÎÅ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÄÉÎÁÍÉÞÅÓËÏÊ ÌÏÇÉËÉ,
ÄÌÑ ÎÁÓ ×ÁÖÎÏ ÈÏÔÑ ÂÙ ×ÏÚÍÏÖÎÏÓÔØÀ ÁÌÇÅÂÒÁÉÞÅÓËÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ
ÓÅÍÁÎÔÉËÉ Á×ÔÏÍÁÔÏ× É ÓÈÅÍ Ó ÔÅÓÔÁÍÉ 
É ×ÏÚÍÏÖÎÏÓÔØÀ ÐÅÒÅÈÏÄÁ ÏÔ ÎÉÈ Ë Á×ÔÏÍÁÔÁÍ (ÉÌÉ ÓÈÅÍÁÍ) 
× ÓÅÍÁÎÔÉËÅ Ó ËÒÁÔÎÏÓÔÑÍÉ, ÄÌÑ
ËÏÔÏÒÙÈ ÅÓÔØ ×ÁÖÎÙÅ ÍÅÔÏÄÙ ÐÒÏ×ÅÒËÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ \cite{HK} (ÜÔÏ
ÐÒÅÉÍÕÝÅÓÔ×Ï \KAT ÏÔÍÅÞÁÌÏÓØ É \cite{KAT-Hoare}).

÷ÎÅÛÎÅ ÜË×É×ÁÌÅÎÔÎÏÓÔØ, ÓËÁÖÅÍ,
Ä×ÕÈ ÐÒÏÇÒÁÍÍ ÐÒÉ ÄÏÐÕÝÅÎÉÉ Ï
ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ Ä×ÕÈ ×ÙÂÒÁÎÎÙÈ ÏÐÅÒÁÔÏÒÏ× ÂÕÄÅÔ ×ÙÒÁÖÁÔØÓÑ ÆÏÒÍÕÌÁÍÉ
(\tND{Horn\dÆÏÒÍÕÌÁÍÉ}{def:Horn-formula}) ×ÒÏÄÅ:
$$
ab = ba \implic s = t,
$$
ÇÄÅ × ÐÏÓÙÌËÅ ÓÔÏÉÔ ÕÖÅ ÚÎÁËÏÍÏÅ ÐÏ ×ÉÄÕ ÄÏÐÕÝÅÎÉÅ, Á $s$ É $t$\T
ÔÅÒÍÙ\dÐÒÏÇÒÁÍÍÙ. (ï ×ÙÒÁÖÅÎÉÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ ÔÁËÉÍÉ
ÆÏÒÍÕÌÁÍÉ \sm ïÐÒÅÄÅÌÅÎÉÑ~\ref{def:HKA} É \ref{def:HKAT}.)

åÓÌÉ ÐÒÅÎÅÂÒÅÞØ ÎÅËÏÔÏÒÙÍÉ ÕÔÏÞÎÅÎÉÑÍÉ, ÔÏ ÍÏÖÎÏ ÓËÁÚÁÔØ, ÞÔÏ
ÄÌÑ ÐÒÉÎÑÔÏÇÏ ÎÁÍÉ ÆÏÒÍÁÌÉÚÍÁ ×ÏÐÒÏÓ 1 ÍÏÖÅÔ ÂÙÔØ ÓÆÏÒÍÕÌÉÒÏ×ÁÎ ËÁË ×ÏÐÒÏÓ 
Ï ÕÓÌÏ×ÉÑÈ  ÒÁÚÒÅÛÉÍÏÓÔÉ \tND{ÜË×ÁÃÉÏÎÁÌØÎÙÈ ÔÅÏÒÉÊ
ËÌÁÓÓÏ× ÁÌÇÅÂÒ ëÌÉÎÉ}{def:EKA} (ÕÓÌÏ×ÉÑ ÎÁËÌÁÄÙ×ÁÀÔÓÑ ÎÁ ËÌÁÓÓ ÁÌÇÅÂÒ,
ÏÔ×ÅÞÁÀÝÉÈ~$\Phi$); 
×ÏÐÒÏÓ~2\T ËÁË ×ÏÐÒÏÓ Ï ÕÓÌÏ×ÉÑÈ  ÒÁÚÒÅÛÉÍÏÓÔÉ \tND{Horn\dÔÅÏÒÉÊ
ÁÌÇÅÂÒÙ ëÌÉÎÉ}{def:HKA} (ÕÓÌÏ×ÉÑ ÎÁËÌÁÄÙ×ÁÀÔÓÑ ÎÁ ×ÉÄ ÐÏÓÙÌÏË, 
ËÏÔÏÒÙÅ ÒÁÚÒÅÛÅÎÙ × Horn\dÆÏÒÍÕÌÁÈ). 

óÔÏÉÔ ÐÏÍÎÉÔØ, ÞÔÏ 
ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ ×ÏÐÒÏÓÁ Ï
ÒÁÚÒÅÛÉÍÏÓÔÉ ðü ËÁË ×ÏÐÒÏÓÁ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ÔÅÏÒÉÊ ÎÅ Ñ×ÌÑÅÔÓÑ
ÓÕÝÅÓÔ×ÅÎÎÙÍ ÛÁÇÏÍ ÉÓÓÌÅÄÏ×ÁÎÉÑ, Á ÓÌÕÖÉÔ ÔÏÌØËÏ ÄÌÑ ÂÏÌÅÅ ÑÓÎÏÇÏ
ÐÒÅÄÓÔÁ×ÌÅÎÉÑ ÒÅÚÕÌØÔÁÔÏ× × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÐÒÉÎÑÔÏÊ ×ÎÕÔÒÉ
ÉÓÓÌÅÄÏ×ÁÎÉÑ ÔÏÞËÏÊ ÚÒÅÎÉÑ. ë ÐÒÉÍÅÒÕ, ÎÁÍ ÕÄÏÂÎÏ ÎÅ ÇÏ×ÏÒÉÔØ ÌÉÛÎÉÈ
ÓÌÏ×  É ÎÅ ××ÏÄÉÔØ ÌÉÛÎÉÈ ÐÏÎÑÔÉÊ × ÓÌÕÞÁÅ, 
ËÏÇÄÁ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÐÒÏÇÒÁÍÍ × ÏÄÎÏÊ ÓÅÍÁÎÔÉËÅ ÒÁ×ÎÏÓÉÌØÎÁ (ÉÌÉ
Ó×ÏÄÉÔÓÑ Ë)
ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ × ÄÒÕÇÏÊ ÓÅÍÁÎÔÉËÅ: ÍÙ ÐÒÏÓÔÏ ÏÂßÑ×ÌÑÅÍ ÆÁËÔ
ÓÏ×ÐÁÄÅÎÉÑ ÜË×ÁÃÉÏÎÁÌØÎÙÈ ÔÅÏÒÉÊ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ËÌÁÓÓÏ× ÍÏÄÅÌÅÊ É
ÄÁÌØÛÅ ÏÂÓÕÖÄÁÅÍ ×ÏÐÒÏÓ Ï ţ ÒÁÚÒÅÛÉÍÏÓÔÉ (ÐÏÎÉÍÁÑ, ÞÔÏ ÍÙ ÍÏÖÅÍ
ÐÏÌØÚÏ×ÁÔØÓÑ ÌÀÂÙÍ ËÌÁÓÓÏÍ ÍÏÄÅÌÅÊ × ÒÁÓÓÕÖÄÅÎÉÑÈ) É ÎÅ ÚÁÇÒÏÍÏÖÄÁÅÍ
ÒÁÓÓËÁÚ ÏÂÏÚÎÁÞÅÎÉÑÍÉ ÄÌÑ ÐÅÒÅÈÏÄÁ ÍÅÖÄÕ ÒÁÚÎÙÍÉ <<ÔÉÐÁÍÉ>>
ÓÅÍÁÎÔÉÞÅÓËÉ ÎÁÇÒÕÖÅÎÎÙÈ ÐÒÏÇÒÁÍÍ.

\section{ãÅÌÉ ÄÁÎÎÏÊ ÒÁÂÏÔÙ}
\label{sec:goals}
\paragraph{þÔÏ ÐÏÂÕÄÉÌÏ Å£ ÓÏÚÄÁÎÉÅ?}
\begin{itemize}
\item 
ó ÏÄÎÏÊ ÓÔÏÒÏÎÙ, ÍÙ ÚÁÎÉÍÁÌÉÓØ ÉÓÓÌÅÄÏ×ÁÎÉÅÍ ÐÒÏÇÒÁÍÍ Ó ÓÅÍÁÎÔÉËÁÍÉ ÎÁ
ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ (ÕÐÏÍÑÎÕÔÙ × ÐÒÅÄÙÄÕÝÅÍ òÁÚÄÅÌÅ ÎÁ
ÓÔÒ.~\pageref{words:kf-semantics}), É ÓÔÁ×ÉÌÉ × ÉÈ ÔÅÒÍÉÎÁÈ
ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÅ 
×ÏÐÒÏÓÙ \cite{kurs4,ciaa-commut-monot,dm6-pcommut-monot}, É ÎÁÍ ÂÙÌÉ
ÉÚ×ÅÓÔÎÙ ÎÅËÏÔÏÒÙÅ ÒÅÚÕÌØÔÁÔÙ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü. 

\item ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ×
ÏÂÌÁÓÔØ, ÏÞÅÒÞÉ×ÁÅÍÕÀ ÔÅÍÉ ÖÅ ×ÉÄÁÍÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×,
ÐÏÐÁÄÁÌÉ ÄÒÕÇÉÅ ÉÚ×ÅÓÔÎÙÅ ÒÅÚÕÌØÔÁÔÙ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü\T ÍÙ ÉÍÅÅÍ ×
×ÉÄÕ ðü ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÍÎÏÇÏÌÅÎÔÏÞÎÙÈ Á×ÔÏÍÁÔÏ× (ÏÎÁ ÔÏÖÅ ÕÐÏÍÑÎÕÔÁ
× ÐÒÅÄÙÄÕÝÅÍ òÁÚÄÅÌÅ ÎÁ ÓÔÒ.~\pageref{words:dmta-problem}).
îÁÊÄÅÎÎÏÅ ×
\cite{HK} ÒÅÛÅÎÉÅ ÚÁÄÁÞÉ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DMTA 
ÎÅÌØÚÑ ÓÞÉÔÁÔØ ÔÒÉ×ÉÁÌØÎÙÍ ÈÏÔÑ ÂÙ ÐÏÔÏÍÕ, ÞÔÏ ÏÎÏ ÂÙÌÏ ÐÏÌÕÞÅÎÏ
ÓÐÕÓÔÑ ÍÎÏÇÏ ×ÒÅÍÅÎÉ ÐÏÓÌÅ ÐÏÓÔÁÎÏ×ËÉ ÚÁÄÁÞÉ, × ÔÅÞÅÎÉÅ ËÏÔÏÒÏÇÏ
ÓÏ×ÅÒÛÁÌÉÓØ ÐÏÐÙÔËÉ Å£ ÒÅÛÉÔØ. òÅÛÅÎÉÅ \cite{HK} ÂÙÌÏ ÐÏÌÕÞÅÎÏ ×
ÒÁÍËÁÈ ÐÏÎÑÔÉÊ É ÐÒÉ ÐÏÍÏÝÉ ÔÅÈÎÉËÉ (\emph{ÁÌÇÅÂÒ Ó ËÒÁÔÎÏÓÔÑÍÉ}), 
ÚÎÁÞÉÔÅÌØÎÏ ÏÔÌÉÞÁÀÝÉÈÓÑ ÏÔ ÔÅÈ, ËÏÔÏÒÙÍÉ ÂÙÌÏ
ÐÒÉ×ÙÞÎÏ ÐÏÌØÚÏ×ÁÔØÓÑ ÐÒÉ ÉÓÓÌÅÄÏ×ÁÎÉÉ ÐÒÏÇÒÁÍÍ Ó ÓÅÍÁÎÔÉËÁÍÉ ÎÁ
ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ (\emph{ÔÒÁÓÓ × ÛËÁÌÁÈ ëÒÉÐËÅ}).
\end{itemize}
\noindent
óÏÚÄÁÎÉÅ ÜÔÏÊ ÒÁÂÏÔÙ ÐÏÂÕÄÉÌÏ ÖÅÌÁÎÉÅ ×ÙÑÓÎÉÔØ, ËÁË ÍÏÖÎÏ ÂÙÌÏ ÂÙ
ÐÒÉÍÅÎÑÔØ ÍÅÔÏÄÙ, ÐÒÉ×ÅÄÛÉÅ × ÕÓÐÅÈÕ × ÓÌÕÞÁÅ DMTA, × ÏÓÔÁÌØÎÙÈ
ÉÎÔÅÒÅÓÎÙÈ ÎÁÍ ÓÌÕÞÁÑÈ.

ïÔÍÅÔÉÍ, 
\begin{itemize}
\item 
×Ï-ÐÅÒ×ÙÈ, ÞÔÏ ÐÏÌÎÏÅ ÒÅÛÅÎÉÅ ÚÁÄÁÞÉ, ËÏÔÏÒÕÀ ÍÙ ÐÅÒÅÄ ÓÏÂÏÊ
ÓÔÁ×ÉÍ, ÎÅ×ÏÚÍÏÖÎÏ ÂÅÚ ×ËÌÀÞÅÎÉÑ ÒÅÚÕÌØÔÁÔÁ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ \cite{HK},
\item 
×Ï-×ÔÏÒÙÈ, ÞÔÏ ÏÎ ÎÅÐÒÏÓÔ, É ÚÎÁÞÉÔ, × ÏÂÌÁÓÔÉ ÎÁÛÅÊ ÚÁÄÁÞÉ ÍÏÇÕÔ ÂÙÔØ
ÅÝ£ ÔÁËÉÅ ÖÅ ÎÅÐÒÏÓÔÙÅ ÓÌÕÞÁÉ, Ë ËÏÔÏÒÙÍ, ×ÏÚÍÏÖÎÏ, ÐÒÉÍÅÎÉÍÙ ÔÅ ÖÅ
ÍÅÔÏÄÙ ÒÅÛÅÎÉÑ, 
\item Á ×-ÔÒÅÔØÉÈ, ÞÔÏ ÐÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞÉ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ
ÜË×É×ÁÌÅÎÔÎÏÓÔÉ DMTA ÐÒÏÝÅ, ÞÅÍ ÎÁÛÁ ÏÂÝÁÑ ÚÁÄÁÞÁ: Õ ÎÁÓ ÓÔÒÕËÔÕÒÁ
ÐÒÏÇÒÁÍÍ ÓÌÏÖÎÅÅ, ÞÅÍ ÓÔÒÕËÔÕÒÁ Á×ÔÏÍÁÔÏ×, ÔÅÍ, ÞÔÏ × ÎÉÈ ÅÓÔØ ÅÝ£
ÔÅÓÔÙ. 
\end{itemize}
\noindent
ðÏÓÌÅÄÎÅÅ ÏÂÓÔÏÑÔÅÌØÓÔ×Ï ÄÅÌÁÌÏ ÎÅÑÓÎÙÍ 
×ÏÐÒÏÓ Ï ÔÏÍ, ËÁË ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÐÒÉÍÅÎÉÔØ ÍÅÔÏÄÙ \cite{HK} Ë ÓÈÅÍÁÍ Ó
ÔÅÓÔÁÍÉ: × \cite{HK} ÉÓÐÏÌØÚÏ×ÁÎÙ ÁÌÇÅÂÒÙ Ó ÔÅÓÔÁÍÉ, Á ÍÙ ÐÒÉ×ÙËÌÉ
ÏÐÉÓÙ×ÁÔØ ÓÅÍÁÎÔÉËÕ ÓÈÅÍ ÐÒÉ ÐÏÍÏÝÉ ÛËÁÌ ëÒÉÐËÅ.

åÝ£ ÏÄÎÏ ÒÏÄÓÔ×ÅÎÎÏÅ ÖÅÌÁÎÉÅ\T ÓÉÓÔÅÍÁÔÉÚÉÒÏ×ÁÔØ ÉÎÔÅÒÅÓÕÀÝÉÅ ÎÁÓ 
ÉÚ×ÅÓÔÎÙÅ ÒÅÚÕÌØÔÁÔÙ Ï ðü ÐÒÏÇÒÁÍÍ, ÏÐÉÓÁÔØ ÉÈ × ÅÄÉÎÏÊ ÓÉÓÔÅÍÅ
ÐÏÎÑÔÉÊ, ÔÁËÏÊ, ËÏÔÏÒÁÑ ÂÙ ÐÏÍÏÇÁÌÁ × ÄÅÌÅ ÒÁÓÐÒÏÓÔÒÁÎÅÎÉÑ ÉÄÅÊ ÒÅÛÅÎÉÊ ÄÌÑ
ÞÁÓÔÎÙÈ ÓÌÕÞÁÅ× ÎÁ ÂÏÌÅÅ ÏÂÝÉÅ.

öÅÌÁÎÉÅ ÓÏÏÔÎÅÓÔÉ Ä×Á ÐÏÄÈÏÄÁ Ë ÉÓÓÌÅÄÏ×ÁÎÉÀ ðü ÕÖÅ ÐÒÏÑ×ÌÑÌÏÓØ
×~\cite{ciaa-commut-monot}.

\paragraph{ëÁË ÐÒÏÉÚ×ÅÄÅÎÁ ÒÁÂÏÔÁ.}
äÌÑ ÉÓÓÌÅÄÏ×ÁÎÉÑ ÁÂÓÔÒÁËÃÉÊ ÐÒÏÇÒÁÍÍ É ðü ×ÙÂÒÁÎ ÏÓÎÏ×ÎÏÊ ÐÏÄÈÏÄ ÎÁ
ÏÓÎÏ×Å ÁÌÇÅÂÒ ëÌÉÎÉ É ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ. (áÌÇÅÂÒÙ É ÐÏÓÔÁÎÏ×ËÁ
×ÏÐÒÏÓÏ× Ï ðü ÐÒÏÇÒÁÍÍ × ÎÉÈ ÐÒÅÄÓÔÁ×ÌÅÎÙ ÞÉÔÁÔÅÌÀ × ÐÒÅÄÙÄÕÝÉÈ
ÒÁÚÄÅÌÁÈ ÷×ÅÄÅÎÉÑ.)

÷ ÒÁÂÏÔÅ ÍÙ ÓÔÒÅÍÉÍÓÑ ÏÔ×ÅÞÁÔØ ÎÁ ×ÏÐÒÏÓÙ, ×ÏÚÎÉËÁÀÝÉÅ ÐÒÉ
ÉÓÓÌÅÄÏ×ÁÎÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ É ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ, ÉÍÅÀÝÉÈ ÏÔÎÏÛÅÎÉÅ
Ë ÎÁÛÅÊ ÚÁÄÁÞÅ. ÷×ÉÄÕ ÂÏÌØÛÅÊ ÏÂÝÎÏÓÔÉ ÐÏÄÈÏÄÁ, ÞÅÍ, ÓËÁÖÅÍ, × ÓÌÕÞÁÅ
ÓÅÍÁÎÔÉË ÐÒÏÇÒÁÍÍ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ, ×ÏÚÎÉËÁÀÝÉÅ ×ÏÐÒÏÓÙ ÔÏÖÅ
ÂÏÌÅÅ ÏÂÝÉÅ.

\paragraph{÷ÁÖÎÙÅ ÓÏÓÔÁ×ÌÑÀÝÉÅ ÒÁÂÏÔÙ.}
ïÂÁ ÐÏÄÈÏÄÁ Ë ÉÓÓÌÅÄÏ×ÁÎÉÀ ðü, ÖÅÌÁÎÉÅ ÓÏÅÄÉÎÉÔØ ËÏÔÏÒÙÅ ÐÏÂÕÄÉÌÏ ÓÏÚÄÁÎÉÅ
ÒÁÂÏÔÙ, ÚÁÎÉÍÁÀÔ × ÒÁÂÏÔÅ ×ÁÖÎÏÅ ÍÅÓÔÏ. òÏÌØ ËÏÍÐÏÎÅÎÔ ÒÁÂÏÔÙ:
\begin{itemize}
\item 
  áÌÇÅÂÒÙ ëÌÉÎÉ (Ó ÔÅÓÔÁÍÉ)\T ÁÌÇÅÂÒÁÉÞÅÓËÉÅ ÓÉÓÔÅÍÙ × ÔÅÒÍÉÎÁÈ
  ËÏÔÏÒÙÈ ÕÄÏÂÎÏ ÒÁÂÏÔÁÔØ; ÏÎÉ ÐÒÅÄÌÁÇÁÀÔ ÕÄÏÂÎÏÅ ÄÌÑ ÏÂÏÂÝÅÎÉÑ
  ÒÅÚÕÌØÔÁÔÏ× ×ÉÄÅÎÉÅ ×ÏÐÒÏÓÏ× ÐÒÏ×ÏÄÉÍÏÇÏ 
  ÉÓÓÌÅÄÏ×ÁÎÉÑ. óÁÍÉ ÐÏ ÓÅÂÅ ÐÏÎÑÔÉÑ ÏÂ
  ÜÔÉÈ ÁÌÇÅÂÒÁÈ ÌÉÛÅÎÙ ËÏÎËÒÅÔÎÙÈ ÐÏÓÔÒÏÅÎÉÊ.
\item 
  ôÅÈÎÉËÁ \cite{E} É ÒÅÛÅÎÉÅ \cite{HK} 
  ðü DMTA ÎÁ Å£ ÏÓÎÏ×Å ÐÒÅÄÓÔÁ×ÌÅÎÙ ×
  òÁÚÄÅÌÁÈ~\ref{sec:free-plain-multi} É \ref{sec:hypo-plain-multi}.
  äÁÌØÛÅ ÎÁÓ ÚÁÎÉÍÁÅÔ ×ÏÐÒÏÓ Ï ÔÏÍ, ÎÁÓËÏÌØËÏ ÏÎÉ ÐÒÉÍÅÎÉÍÙ Ë
  ÁÌÇÅÂÒÁÉÞÅÓËÉÍ ÐÏÓÔÒÏÅÎÉÑÍ, ËÏÔÏÒÙÅ ÍÙ ÄÅÌÁÅÍ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ.
\item ûËÁÌÙ ëÒÉÐËÅ ÐÒÅÄÓÔÁ×ÌÑÀÔ ÓÏÂÏÊ ×ÁÖÎÙÅ ÐÏÓÔÒÏÅÎÉÑ ÄÌÑ ÒÅÛÅÎÉÑ
  ×ÏÚÎÉËÁÀÝÉÈ ×ÏÐÒÏÓÏ× ÍÅÔÁÔÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ (Ó ÔÅÓÔÁÍÉ), ËÏÔÏÒÁÑ
  ÓÁÍÁ ÐÏ ÓÅÂÅ ÓÔÁ×ÉÔ ×ÏÐÒÏÓÙ ÂÅÚÏÔÎÏÓÉÔÅÌØÎÏ ËÏÎËÒÅÔÎÙÈ ÐÏÓÔÒÏÅÎÉÊ\T ÍÙ 
  ÏÔ×ÏÄÉÍ × ÎÁÛÅÊ ÒÁÂÏÔÅ ÛËÁÌÁÍ ëÒÉÐËÅ 
  ÒÏÌØ ÁÎÁÌÏÇÏ× ÂÏÌÅÅ ÐÒÏÓÔÙÈ ËÏÎÓÔÒÕËÃÉÊ ×ÏÚÎÉËÁÀÝÉÈ × ÂÏÌÅÅ
  ÐÒÏÓÔÙÈ ÓÌÕÞÁÑÈ (ÎÁÐÒÉÍÅÒ, 
  ÓÌÏ× × ÓÌÕÞÁÅ ÉÓÓÌÅÄÏ×ÁÎÉÑ ðü ËÏÎÅÞÎÙÈ Á×ÔÏÍÁÔÏ×).

  úÄÅÓØ ÎÁÍ ÐÒÉÇÏÄÉÔÓÑ ÏÐÙÔ, ÎÁËÏÐÌÅÎÎÙÊ ÉÓÓÌÅÄÏ×ÁÎÉÑÍÉ ðü ÐÒÏÇÒÁÍÍ Ó
  ÓÅÍÁÎÔÉËÁÍÉ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ.
\end{itemize}

\paragraph{ëÁËÏÇÏ ÒÏÄÁ ÒÁÓÓÕÖÄÅÎÉÑ ÏËÁÚÙ×ÁÀÔÓÑ ×ÁÖÎÙ.}
èÁÒÁËÔÅÒ ÒÁÂÏÔÙ ÔÁËÏ×, ÞÔÏ ÍÙ ÈÏÔÉÍ ÐÏËÁÚÁÔØ ÍÅÓÔÏ ÏÔÄÅÌØÎÙÈ ÒÅÛÅÎÉÊ É
ÐÏÓÔÒÏÅÎÉÊ × ÏÂÝÅÊ ÓÉÓÔÅÍÅ. ðÒÉ ÜÔÏÍ × ËÁÖÄÏÍ ÏÔÄÅÌØÎÏÍ ÓÌÕÞÁÅ
ÏÓÔÁÎÕÔÓÑ ÔÒÕÄÎÏÓÔÉ, Ó×ÑÚÁÎÎÙÅ Ó ÒÅÛÅÎÉÅÍ.
îÁÍ ×ÁÖÎÏ Õ×ÉÄÅÔØ ÏÂÝÉÅ Ó×ÑÚÉ ÍÅÖÄÕ Ó×ÏÊÓÔ×ÁÍÉ ÒÁÚÎÙÈ
ÐÏÓÔÒÏÅÎÉÊ. âÏÌÅÅ ËÏÎËÒÅÔÎÏ: ÓÔÁÎÏ×ÉÔÓÑ ×ÉÄÎÏ, ÞÔÏ ÜË×É×ÁÌÅÎÔÎÏÓÔØ
ÐÒÏÇÒÁÍÍ ÏÔÎÏÓÉÔÅÌØÎÏ ÏÄÎÏÇÏ ËÌÁÓÓÁ ÍÏÄÅÌÅÊ (ÁÌÇÅÂÒ ëÌÉÎÉ) 
ÒÁ×ÎÏÓÉÌØÎÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
ÐÒÏÇÒÁÍÍ ÏÔÎÏÓÉÔÅÌØÎÏ ÄÒÕÇÏÇÏ ËÌÁÓÓÁ ÍÏÄÅÌÅÊ (ÁÌÇÅÂÒ ëÌÉÎÉ), É ÜÔÏ
ÉÍÅÅÔ ÏÂßÑÓÎÅÎÉÅ × Ó×ÑÚÑÈ É ÓÔÒÏÅÎÉÉ ÜÔÉÈ ÁÌÇÅÂÒ ëÌÉÎÉ. 

îÁÐÒÉÍÅÒ,
ÔÅÏÒÅÍÕ üÊÌÅÎÂÅÒÇÁ \cite{E} ÍÏÖÎÏ ÐÒÉÍÅÎÉÔØ Ä×ÕÍÑ ÒÁÚÎÙÍÉ ÓÐÏÓÏÂÁÍÉ,
ÞÔÏÂÙ ÐÏËÁÚÁÔØ ÒÁÚÒÅÛÉÍÏÓÔØ ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ËÏÎÅÞÎÙÈ
ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ Á×ÔÏÍÁÔÏ×\T ÐÒÉ ÎÁÛÅÍ ×ÚÇÌÑÄÅ ÎÁ ×ÅÝÉ
ÜÔÏ ÐÒÉÍÅÎÅÎÉÅ ÔÅÏÒÅÍÙ ÏÔÎÏÓÉÔÅÌØÎÏ Ä×ÕÈ ÒÁÚÎÙÈ ËÌÁÓÓÏ×
ÁÌÇÅÂÒ ëÌÉÎÉ: Ó ÏÄÎÏÊ ÓÔÏÒÏÎÙ, ÅÓÌÉ ÇÏ×ÏÒÉÔØ ÎÅÆÏÒÍÁÌØÎÏ, 
ÏÔÎÏÓÉÔÅÌØÎÏ ËÌÁÓÓÁ ÁÌÇÅÂÒ ëÌÉÎÉ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÏÔÄÅÌØÎÙÍ ÓÌÏ×ÁÍ, 
Ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ÏÔÎÏÓÉÔÅÌØÎÏ ÏÄÎÏÊ ÁÌÇÅÂÒÙ ëÌÉÎÉ\T 
×ÓÅÈ (ÒÅÇÕÌÑÒÎÙÈ) ÆÏÒÍÁÌØÎÙÈ ÑÚÙËÏ×. 
÷ ÏÂÏÉÈ ÓÌÕÞÁÑÈ ÔÅÏÒÅÍÁ ÏËÁÚÙ×ÁÅÔÓÑ ÐÒÉÍÅÎÉÍÁ, ÐÒÁ×ÄÁ, ×Ï ×ÔÏÒÏÍ\T Ó
ÇÏÒÁÚÄÏ ÂÏÌØÛÉÍÉ ÔÒÕÄÎÏÓÔÑÍÉ × ÏÂÏÓÎÏ×ÁÎÉÉ ÐÒÉÍÅÎÉÍÏÓÔÉ; 
ÎÏ ÐÒÉÍÅÎÅÎÉÅ ÐÒÉ×ÏÄÉÔ Ë ÏÄÉÎÁËÏ×ÙÍ
ÓÏÄÅÒÖÁÔÅÌØÎÙÍ ÒÅÚÕÌØÔÁÔÁÍ. ÷ ÓÌÕÞÁÅ DMTA ÐÒÉÍÅÎÅÎÉÅ ÔÅÏÒÅÍÙ
ÁÎÁÌÏÇÉÞÎÙÍ ÐÅÒ×ÙÍ ÏÂÒÁÚÏÍ 
ÏËÁÚÙ×ÁÅÔÓÑ ÎÅ×ÏÚÍÏÖÎÙÍ ××ÉÄÕ ÉÎÙÈ Ó×ÏÊÓÔ× ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÁÌÇÅÂÒ, ÎÏ
×ÔÏÒÏÊ (ÂÏÌÅÅ ÔÒÕÄÎÙÊ) ÓÐÏÓÏ ţ ÐÒÉÍÅÎÅÎÉÑ ×Ó£ ÅÝ£ ÒÁÂÏÔÁÅÔ, ÞÔÏ É
ÏÂÎÁÒÕÖÉÌÉ \cite{HK}. (ðÏ ÓÕÔÉ ÏÎÉ ÏÂÒÁÔÉÌÉ ×ÎÉÍÁÎÉÅ ×ÏÏÂÝÅ ÎÁ
×ÏÚÍÏÖÎÏÓÔØ ÐÒÉÍÅÎÅÎÉÑ ÔÅÏÒÅÍÙ üÊÌÅÎÂÅÒÇÁ <<×ÔÏÒÙÍ ÏÂÒÁÚÏÍ>> É
ÏÂÏÓÎÏ×ÁÌÉ Å£ ÐÒÉÍÅÎÉÍÏÓÔØ ÎÅÐÒÏÓÔÙÍÉ ÁÌÇÅÂÒÁÉÞÅÓËÉÍÉ ÓÒÅÄÓÔ×ÁÍÉ,
ÏÔÎÏÓÑÝÉÍÉÓÑ Ë ôÅÏÒÉÉ ËÏÌÅà ÆÏÒÍÁÌØÎÙÈ ÓÕÍÍ (ÓÔÅÐÅÎÎÙÈ ÒÑÄÏ×) 
É ÕÐÏÒÑÄÏÞÅÎÎÙÈ ÇÒÕÐÐ.)
(üÔÏ ÏÐÉÓÁÎÏ × òÁÚÄÅÌÁÈ~\ref{sec:dfa-E} É~\ref{sec:dmta-E}.)

äÌÑ ÓÅÂÑ ÍÙ ÏÔÍÅÔÉÌÉ ÉÎÔÅÒÅÓÎÕÀ
Ó×ÑÚØ ÍÅÖÄÕ ×ÓÔÕÐÉ×ÛÉÍÉ ÔÕÔ × ÉÇÒÕ ËÌÁÓÓÁÍÉ ÁÌÇÅÂÒ ëÌÉÎÉ: 
<<×ÔÏÒÁÑ>> ÁÌÇÅÂÒÁ (ÎÁÐÒÉÍÅÒ, ÁÌÇÅÂÒÁ ÒÅÇÕÌÑÒÎÙÈ ÑÚÙËÏ×)\T 
\emph{Ó×ÏÂÏÄÎÁÑ ÁÌÇÅÂÒÁ} × ËÌÁÓÓÅ ÁÌÇÅÂÒ ëÌÉÎÉ,
ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ×ÚÑÔÙÍ ÓÅÍÁÎÔÉÞÅÓËÉÍ ÐÏÓÔÕÌÁÔÁÍ (ÎÁÐÒÉÍÅÒ, ÎÉËÁËÉÍ ×
ÓÌÕÞÁÅ Ó ÒÅÇÕÌÑÒÎÙÍÉ ÑÚÙËÁÍÉ).
\Te ÁÌÇÅÂÒÁ ÒÅÇÕÌÑÒÎÙÈ ÑÚÙËÏ×\T Ó×ÏÂÏÄÎÁÑ ÁÌÇÅÂÒÁ ëÌÉÎÉ;
ÁÌÇÅÂÒÁ, ×ÏÚÎÉËÁÀÝÁÑ ÐÒÉ ÐÒÉÍÅÎÅÎÉÉ ÔÅÏÒÅÍÙ üÊÌÅÎÂÅÒÇÁ Ë DMTA,\T
ÁÌÇÅÂÒÁ, Ó×ÏÂÏÄÎÁÑ × ËÌÁÓÓÅ ÁÌÇÅÂÒ ëÌÉÎÉ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÍ ÐÏÓÔÕÌÁÔÁÍ,
ÏÐÉÓÙ×ÁÀÝÉÍ ÓÅÍÁÎÔÉËÕ DMTA. üÔÏ ÔÏÌØËÏ ÐÏÌÏ×ÉÎÁ ÄÅÌÁ. ÷ÔÏÒÁÑ
ÐÏÌÏ×ÉÎÁ\T ÜÔÏ ÔÏ, ÞÔÏ É ÔÁ, É ÄÒÕÇÁÑ ÐÏÓÔÒÏÅÎÙ ÓÔÁÎÄÁÒÔÎÙÍ ÏÂÒÁÚÏÍ\T
ÎÁ ÔÅÈÎÉÞÅÓËÏÍ ÕÒÏ×ÎÅ ÅÍÕ ÏÔ×ÅÞÁÅÔ ÆÕÎËÔÏÒ $\REG$ \cite{KA-complexity} 
ÉÚ ËÁÔÅÇÏÒÉÉ
ÍÏÎÏÉÄÏ× (É ÉÈ ÇÏÍÏÍÏÒÆÉÚÍÏ×) × ËÁÔÅÇÏÒÉÀ ÁÌÇÅÂÒ ëÌÉÎÉ (É ÉÈ
ÇÏÍÏÍÏÒÆÉÚÍÏ×), 
É ÔÅÍ ÓÁÍÙÍ ÞÕÔØ ×ÙÛÅ ÍÙ ÇÏ×ÏÒÉÌÉ ÐÒÏ ÁÌÇÅÂÒÙ
\begin{align*}
  &\REG \Sigma^*,
  &
  &\REG (\Sigma_1^* \oplus \dotsb \oplus \Sigma_k^*)
\end{align*}
(×ÔÏÒÏÊ ÐÒÉÍÅÒ\T ÄÌÑ ÎÅËÏÔÏÒÏÇÏ $k$\dÌÅÎÔÏÞÎÏÇÏ Á×ÔÏÍÁÔÁ, $\Sigma$\T
ÁÌÆÁ×ÉÔ ÂÕË×).

÷ ÄÒÕÇÉÈ ÓÌÕÞÁÑÈ ÍÙ ÓÔÒÅÍÉÍÓÑ ÏÔÙÓËÁÔØ ÐÏÄÏÂÎÙÍ ÏÂÒÁÚÏÍ
Ó×ÑÚÁÎÎÙÅ ËÌÁÓÓÙ ÁÌÇÅÂÒ.

íÙ ÐÒÅÄÐÏÌÁÇÁÅÍ, ÞÔÏ ÄÌÑ ×ÙÐÏÌÎÅÎÉÑ ÜÔÏÊ ÃÅÌÉ ×ÁÖÎÙ ÁÌÇÅÂÒÙ, ËÏÔÏÒÙÅ
ÍÙ ÓÔÒÏÉÍ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ, ÏÂÏÂÝÁÑ ÐÏÓÔÒÏÅÎÉÅ Ó×ÏÂÏÄÎÏÊ ÁÌÇÅÂÒÙ
ÎÁ ÏÓÎÏ×Å ÓÌÏ× × ÂÏÌÅÅ ÐÒÏÓÔÙÈ ÓÌÕÞÁÑÈ.  

ðÏÞÅÍÕ ÉÍ ÍÏÖÎÏ ÐÒÏÞÉÔØ ÃÅÎÔÒÁÌØÎÏÅ ÍÅÓÔÏ? ðÒÅÄÌÁÇÁÅÍ ÔÁËÏÅ
ÎÅÆÏÒÍÁÌØÎÏÅ ÏÂÏÓÎÏ×ÁÎÉÅ.

%\todo{[ÃÅÎÔÒÁÌØÎÏÓÔØ ÏÂßÑÓÎÉÔØ. ÷ ÄÒÕÇÏÅ ÍÅÓÔÏ? ÕÎÉ×ÅÒÓÁÌØÎÏÓÔØ?]}

íÙ ÕÖÅ ÏÔÍÅÞÁÌÉ, ÞÔÏ 
ÓÅÍÁÎÔÉËÁ ÐÒÏÇÒÁÍÍ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ 
ÈÏÒÏÛÏ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÏÂÝÅÍÕ ÉÎÔÕÉÔÉ×ÎÏÍÕ ÐÒÅÄÓÔÁ×ÌÅÎÉÀ Ï ÔÏÍ, ËÁË
ÐÒÏÈÏÄÉÔ ×ÙÞÉÓÌÅÎÉÅ ÐÒÏÇÒÁÍÍÙ ÎÁ ×ÙÞÉÓÌÉÔÅÌØÎÏÍ ÕÓÔÒÏÊÓÔ×Å.
éÚ-ÚÁ ÜÔÏÇÏ ÍÏÖÎÏ ÏÖÉÄÁÔØ, ÞÔÏ ÍÎÏÇÉÅ ÄÒÕÇÉÅ <<ÒÁÚÕÍÎÙÅ>>
ÁÂÓÔÒÁËÔÎÙÅ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ ÍÏÖÎÏ ÐÒÏÍÏÄÅÌÉÒÏ×ÁÔØ × ÎÅÊ, ÄÒÕÇÉÍÉ
ÓÌÏ×ÁÍÉ, ÞÔÏ ÆÁËÔÙ, ËÁÓÁÀÝÉÅÓÑ ÐÒÏÇÒÁÍÍ, ÕÓÔÁÎÏ×ÌÅÎÎÙÅ ÐÒÉ 
ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÓÅÍÁÎÔÉË ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ 
ÄÏÌÖÎÙ ÂÕÄÕÔ ÂÙÔØ ×ÅÒÎÙ É × ÄÒÕÇÉÈ <<ÒÁÚÕÍÎÙÈ>> ÁÂÓÔÒÁËÔÎÙÈ ÍÏÄÅÌÑÈ
ÐÒÏÇÒÁÍÍ.

åÓÌÉ, ËÁË ÐÒÉÎÑÔÏ × ÎÁÛÅÍ ÉÓÓÌÅÄÏ×ÁÎÉÉ, <<ÒÁÚÕÍÎÏÓÔØ>> ÁÂÓÔÒÁËÔÎÏÊ ÍÏÄÅÌÉ
ÐÒÏÇÒÁÍÍ ÐÏÎÉÍÁÔØ ËÁË ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÁËÓÉÏÍÁÍ ÁÌÇÅÂÒÙ ëÌÉÎÉ, ÔÏ
ÎÅÕÄÉ×ÉÔÅÌØÎÏ, ÞÔÏ ÁÌÇÅÂÒÙ ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ ÚÁÊÍÕÔ ÃÅÎÔÒÁÌØÎÏÅ
ÍÅÓÔÏ × ÉÓÓÌÅÄÏ×ÁÎÉÉ.

÷ ÉÔÏÇÅ ÍÙ ÐÒÅÄÌÏÖÉÌÉ ÏÂÏÂÝÅÎÉÅ $\REG$\T ÆÕÎËÔÏÒ $\REGT$ ÉÚ ËÁÔÅÇÏÒÉÉ
ÍÏÎÏÉÄÏ× × ËÁÔÅÇÏÒÉÀ ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ. (÷ ÏÔÌÉÞÉÅ ÏÔ Á×ÔÏÍÁÔÏ× Õ
ÎÁÓ ×ÄÏÂÁ×ÏË Ë ÏÐÅÒÁÔÏÒÁÍ ÅÝ£ ÅÓÔØ ÔÅÓÔÙ.)

\section{÷ÎÅÛÎÉÅ Ó×ÑÚÉ ÒÁÂÏÔÙ (ÍÅÔÏÄÙ)}

äÌÑ ÉÓÓÌÅÄÕÅÍÏÊ ÚÁÄÁÞÉ ÏËÁÚÙ×ÁÀÔÓÑ ×ÁÖÎÙ ÔÁËÉÅ ÏÂÌÁÓÔÉ, ÍÅÔÏÄÙ É
ÒÅÚÕÌØÔÁÔÙ ÉÚ ÎÉÈ:
\begin{itemize}
\item 
ÔÅÏÒÉÑ ÆÏÒÍÁÌØÎÙÈ ÑÚÙËÏ×
\item 
ÕÎÉ×ÅÒÓÁÌØÎÁÑ ÁÌÇÅÂÒÁ, ÔÅÏÒÉÑ ËÁÔÅÇÏÒÉÊ, ÍÏÄÅÌÉ É ÁÌÇÅÂÒÁ

\item 
ÔÅÏÒÉÉ É ÍÏÄÅÌÉ

\item 
ÒÅÌÑÃÉÏÎÎÙÅ ÍÏÄÅÌÉ ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍ

\item 
trace monoids


\item ÞÁÓÔÉÞÎÏ ËÏÍÍÕÔÁÔÉ×ÎÙÅ ÍÏÎÏÉÄÙ, ÐÏÌÕËÏÌØÃÁ, ËÏÌØÃÁ; ÍÏÄÕÌÉ ÎÁÄ
(ÞÁÓÔÉÞÎÏ ËÏÍÍÕÔÁÔÉ×ÎÙÍÉ) ËÏÌØÃÁÍÉ


\item ÐÒÏÂÌÅÍÁ ÇÒÕÐÐÙ ÄÌÑ ÍÏÎÏÉÄÏ×, ×ÏÚÍÏÖÎÏÓÔÉ ÄÅÌÅÎÉÑ ÄÌÑ ËÏÌÅÃ,
ÕÐÏÒÑÄÏÞÅÎÎÙÅ ÇÒÕÐÐÙ

\item 
ÌÉÎÅÊÎÁÑ ÁÌÇÅÂÒÁ, ÁÌÇÅÂÒÁ ÍÁÔÒÉÃ, ×ÙÞÉÓÌÉÔÅÌØÎÁÑ ÁÌÇÅÂÒÁ\T 
ÐÏÓÔÒÏÅÎÉÅ ÒÁÚÒÅÛÁÀÝÉÈ ÁÌÇÏÒÉÔÍÏ×
ÎÉÚËÏÊ ÓÌÏÖÎÏÓÔÉ (ÎÁÐÒÉÍÅÒ, \cite{Arch-algo} ÐÒÅÄÌÁÇÁÅÔ ÐÏÌÉÎÏÍÉÁÌØÎÙÊ
ÐÏ ×ÒÅÍÅÎÉ ÏÔ ÒÁÚÍÅÒÁ Á×ÔÏÍÁÔÏ× ÁÌÇÏÒÉÔÍ ÐÒÏ×ÅÒËÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
$\bbZ$-$\Sigma^*$\dÁ×ÔÏÍÁÔÏ×\footnote{÷ ÎÁÛÅÊ ÔÅÒÍÉÎÏÌÏÇÉÉ\T
  \emph{ÁÌÇÏÒÉÔÍ, ÒÁÚÒÅÛÁÀÝÉÊ $\EquaOf^\AExp \bbZ\series{\Sigma^*}$}.}, 
ÏÐÉÓÁÎÎÙÊ × ÔÅÒÍÉÎÁÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ ÍÁÔÒÉÃ).


\item 
ÐÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ, ËÏÍÂÉÎÁÔÏÒÉËÁ\T Ó×ÑÚØ Ó ÐÒÅÄÓÔÁ×ÌÅÎÉÅÍ
ÆÏÒÍÁÌØÎÙÈ ÓÕÍÍ, Ñ×ÌÑÀÝÉÈÓÑ ÓÅÍÁÎÔÉËÏÊ ÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ

\item 
ËÏÁÌÇÅÂÒÁÉÞÅÓËÉÊ ÐÏÄÈÏÄ Ë ×ÙÞÉÓÌÉÔÅÌØÎÙÍ ÍÁÛÉÎÁÍ (ÉÎÔÅÒÅÓÎÏ, ÎÏ ÎÁÍÉ
Ó×ÑÚØ Ó ÜÔÉÍ ÐÏÄÈÏÄÏÍ ÎÉËÁË ÎÅ ÚÁÔÒÏÎÕÔÁ \cite{KAT-coalgebraic})
\end{itemize}

\section{÷ÎÕÔÒÅÎÎÅÅ ÕÓÔÒÏÊÓÔ×Ï ÒÁÂÏÔÙ}
%ïÂßÑÓÎÅÎÉÑ ÎÁÚ×ÁÎÉÑÍ çÌÁ× ÒÁÂÏÔÙ ÍÙ ÕÖÅ ÄÁÌÉ ÐÏ ÈÏÄÕ ÷×ÅÄÅÎÉÑ

îÁ ÜÌÅÍÅÎÔÙ ÎÁÓÔÏÑÝÅÊ ÒÁÂÏÔÙ ÍÙ ÂÕÄÅÍ ÓÓÙÌÁÔØÓÑ ÓÌÏ×ÁÍÉ c
<<ÍÅÔÁ->>: \tING{ÍÅÔÁÔÅÏÒÅÍÙ}, \tING{ÍÅÔÁÐÅÒÅÍÅÎÎÙÅ} \itp 
üÔÏ ÏÂßÑÓÎÑÅÔÓÑ, ×
ÞÁÓÔÎÏÓÔÉ, ÖÅÌÁÎÉÅÍ ÉÚÂÅÖÁÔØ ÐÕÔÁÎÉÃÙ Ó ÏÂßÅËÔÁÍÉ, Ï ËÏÔÏÒÙÈ ÍÙ
ÒÁÓÓÕÖÄÁÅÍ × ÜÔÏÊ ÒÁÂÏÔÅ\T 
ÓÒÅÄÉ ËÏÔÏÒÙÈ ÂÕÄÕÔ \tND{ÔÅÏÒÉÉ}{def:theory},
\tND{ÆÏÒÍÕÌÙ}{def:formula} \itp 
éÎÏÇÄÁ, ËÏÇÄÁ
ÐÕÔÁÎÉÃÙ ÎÅ ×ÏÚÎÉËÁÅÔ, ÄÏÂÁ×ËÁ <<ÍÅÔÁ->> ÂÕÄÅÔ ÏÐÕÓËÁÔØÓÑ (ÎÁÐÒÉÍÅÒ, ×
ÏÆÏÒÍÌÅÎÉÉ ÆÏÒÍÕÌÉÒÏ×ÏË ÍÅÔÁÔÅÏÒÅÍ), ÉÌÉ ÏÂßÅËÔÙ ÍÅÔÁÏÂÌÁÓÔÉ ÂÕÄÕÔ ÅÝ£
ËÁË-ÔÏ ÏÓÏÂÅÎÎÏ ×ÙÄÅÌÅÎÙ, ÎÁÐÒÉÍÅÒ, <<ôÅÏÒÉÑ ËÁÔÅÇÏÒÉÊ>> Ó ÂÏÌØÛÏÊ
ÂÕË×Ù ËÁË ÍÅÔÁÔÅÏÒÉÑ ÄÌÑ ÎÁÓ.

éÚÌÏÖÅÎÉÅ ÂÕÄÅÔ ×ÅÓÔÉÓØ ÏÔ ÐÒÏÓÔÏÇÏ Ë ÂÏÌÅÅ ÓÌÏÖÎÏÍÕ, ÐÒÉ ÜÔÏÍ ÓÎÁÞÁÌÁ
(× çÌÁ×Å~\ref{cha:free-plain}) ÂÕÄÅÔ ÐÏÌÎÏÓÔØÀ ÉÚÌÏÖÅÎÁ ÍÅÔÁÔÅÏÒÉÑ ÄÌÑ
ÓÁÍÏÇÏ ÐÒÏÓÔÏÇÏ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÇÏ ÓÌÕÞÁÑ. ðÏ ÎÅÊ ÍÏÖÎÏ ÓÏÓÔÁ×ÉÔØ
× ÎÅËÏÔÏÒÏÍ ÓÍÙÓÌÅ ÐÏÌÎÏÅ ÐÒÅÄÓÔÁ×ÌÅÎÉÅ Ï ÕÓÔÒÏÊÓÔ×Å ×ÓÅÊ ÎÁÛÅÊ
ÍÅÔÁÔÅÏÒÉÉ. äÁÌÅÅ, ×
çÌÁ×ÁÈ~\ref{cha:free-withTests}, \ref{cha:hypo-plain}
É~\ref{cha:hypo-withTests}, ÉÚÌÁÇÁÀÔÓÑ Å£ ÕÓÌÏÖÎÅÎÉÑ.
îÏ×ÉÚÎÁ ÓËÏÎÃÅÎÔÒÉÒÏ×ÁÎÁ × çÌÁ×ÁÈ~\ref{cha:hypo-plain}
É~\ref{cha:hypo-withTests}, × ÏÓÎÏ×ÎÏÍ\T × ÐÏÓÌÅÄÎÅÊ.

ðÏ ÍÅÒÅ ÐÒÏÄ×ÉÖÅÎÉÑ ÐÏ ÜÔÉÍ ÕÒÏ×ÎÑÍ ÕÓÌÏÖΣÎÎÏÓÔÉ ÍÅÔÁÔÅÏÒÉÉ
ÐÒÏÉÓÈÏÄÉÔ
\begin{itemize}
\item ÄÏÂÁ×ÌÅÎÉÅ ÕÞÉÔÙ×ÁÅÍÙÈ × ÁÂÓÔÒÁËÃÉÉ 
  ÁÓÐÅËÔÏ× ÐÒÅÄÍÅÔÎÏÇÏ ÕÒÏ×ÎÑ (ÒÁÓÓÍÏÔÒÅÎÉÅ
  ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×);
\item ÕÓÌÏÖÎÅÎÉÅ ÔÅÈÎÉÞÅÓËÉÈ ËÏÎÓÔÒÕËÃÉÊ ÉÌÉ ××ÅÄÅÎÉÅ × ÒÁÓÓÍÏÔÒÅÎÉÅ
  ÎÏ×ÙÈ, ÉÇÒÁÀÝÉÈ ÒÏÌØ ÁÎÁÌÏÇÏ× ÕÖÅ ÒÁÓÓÍÏÔÒÅÎÎÙÈ × ÂÏÌÅÅ ÐÒÏÓÔÏÍ
  ÓÌÕÞÁÅ;
\item Õ×ÅÌÉÞÅÎÉÅ ÞÉÓÌÁ ÏÔËÒÙÔÙÈ ×ÏÐÒÏÓÏ×.
\end{itemize}

\todo{[ÎÁ ÐÒÅÄÍÅÔÎÏÍ ÕÒÏ×ÎÅ (ÉÓÓÌÅÄÕÅÍÏÊ ÚÁÄÁÞÉ), ×ÎÅÛÎÅÍ --- ÎÁ ÕÒÏ×ÎÅ
  ÔÅÈÎÉËÉ (ÓÐÏÓÏÂÁ,. ÐÏÄÈÏÄÁ, ÒÅÁÌÉÚÁÃÉÉ), ×ÎÕÔÒ.]}

íÅÓÔÏ ÉÓÓÌÅÄÏ×ÁÎÎÙÈ × ÒÁÂÏÔÅ ÓÌÕÞÁÅ× ÍÏÖÎÏ ÕËÁÚÁÔØ 
× 4 ÉÌÉ 5 ÉÚÍÅÒÅÎÉÑÈ:

\begin{description}
\item[<<ÐÏÒÑÄÏË>> ÁÂÓÔÒÁËÃÉÉ:] 0\dÏÊ (ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÊ) ÉÌÉ 1\dÙÊ (Õ
  ÎÁÓ ÚÁÔÒÏÎÕÔ ÔÏÌØËÏ 0-ÏÊ);
\item[ÓÅÍÁÎÔÉÞÅÓËÉÅ ÐÏÓÔÕÌÁÔÙ, ×ËÌÀÞÁÅÍÙÅ × ÁÂÓÔÒÁËÃÉÀ:] ÏÔÓÕÔÓÔ×ÕÀÔ ÉÌÉ ÐÒÉÓÕÔÓÔ×ÕÀÔ (× ÐÅÒ×ÕÀ
  ÏÞÅÒÅÄØ, ÎÁÓ ÉÎÔÅÒÅÓÕÅÔ ÐÒÉÓÕÔÓÔ×ÉÅ ÐÏÓÔÕÌÁÔÏ× Ï ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ É
  ÍÏÎÏÔÏÎÎÏÓÔÉ);
\item[ÕÓÔÒÏÊÓÔ×Ï ÐÒÏÇÒÁÍÍ\T ×ÙÄÅÌÅÎÙ ÌÉ ÔÅÓÔÙ × ÁÂÓÔÒÁËÃÉÉ:] ÐÏÓÔÒÏÅÎÙ ÌÉ
  ÉÓÓÌÅÄÕÅÍÙÅ ÁÂÓÔÒÁËÔÎÙÅ ÐÒÏÇÒÁÍÍÙ ÉÚ ÏÄÎÏÒÏÄÎÙÈ ÏÐÅÒÁÔÏÒÏ× ÉÌÉ ÉÚ
  ÂÁÚÏ×ÙÈ ÜÌÅÍÅÎÔÏ× Ä×ÕÈ ÒÏÄÏ×\T ÏÐÅÒÁÔÏÒÏ× É ÔÅÓÔÏ×;
\item[ÐÒÅÄÓÔÁ×ÌÅÎÉÅ ÐÒÏÇÒÁÍÍÙ:] <<ÌÉÎÅÊÎÏ>> ÚÁÐÉÓÁÎÎÁÑ ÉÌÉ × ×ÉÄÅ
  ÇÒÁÆÁ (ÓÈÅÍÙ) (× ÐÏÓÌÅÄÎÅÍ ÓÌÕÞÁÅ ÔÅÈÎÉÞÅÓËÉ ÄÌÑ ÎÁÓ ÜÔÏ ÏÂÙÞÎÏ
  ÍÁÔÒÉÃÁ, ÈÏÔÑ ÉÎÏÇÄÁ, ËÏÇÄÁ ÜÔÏ ÕÄÏÂÎÏ, ÍÙ × ÉÚÌÏÖÅÎÉÉ ÇÏ×ÏÒÉÍ ÎÅ Ï
  ÍÁÔÒÉÃÁÈ, Á Ï ÇÒÁÆÁÈ\DÓÉÓÔÅÍÁÈ ÐÅÒÅÈÏÄÏ×)
  \begin{center}
    \begin{tabular}{l|l}
      \multicolumn{2}{c}{ÐÒÏÇÒÁÍÍÙ (ÓÉÎÔÁËÓÉÞÅÓËÏÅ ÐÒÅÄÓÔÁ×ÌÅÎÉÅ)}
      \\
      <<ÌÉÎÅÊÎÏ>> ÚÁÐÉÓÁÎÎÙÅ ×ÙÒÁÖÅÎÉÑ
      &
      ÓÉÓÔÅÍÙ ÐÅÒÅÈÏÄÏ×
      \\
      \hline
      ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ
      &
      Á×ÔÏÍÁÔÙ
      \\
      ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ Ó ÔÅÓÔÁÍÉ
      &
      ÓÈÅÍÙ (Ó ÔÅÓÔÁÍÉ)
    \end{tabular}
  \end{center}
\item[ÏÓÏÂÅÎÎÏÓÔÉ ÓÅÍÁÎÔÉËÉ É ÓÅÍÁÎÔÉÞÅÓËÉÅ ÏÓÏÂÅÎÎÏÓÔÉ ÐÒÏÇÒÁÍÍ:]
  ÍÙ ÔÕÔ ÉÍÅÅÍ × ×ÉÄÕ ÄÅÌÅÎÉÅ, ËÏÔÏÒÏÅ ÏÐÉÓÙ×ÁÅÔÓÑ ÓÌÅÄÕÀÝÉÍÉ 
  ËÌÀÞÅ×ÙÍÉ ÓÌÏ×ÁÍÉ, ÐÒÉÎÑÔÙÍÉ × ÎÁÛÅÊ ÏÂÌÁÓÔÉ ÉÓÓÌÅÄÏ×ÁÎÉÑ:
  \begin{itemize}
  \item 
    <<ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ>>\T Ó <<ÉÄÅÍÐÏÔÅÎÔÎÏÊ>> ÓÅÍÁÎÔÉËÏÊ,
  \item 
    ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ, Á ÔÁËÖÅ ÏÄÎÏÚÎÁÞÎÙÅ (unambiguous) ÐÒÏÇÒÁÍÍÙ
  \item É ÐÒÏÇÒÁÍÍÙ Ó ÓÅÍÁÎÔÉËÏÊ Ó ËÒÁÔÎÏÓÔÑÍÉ. 
  \end{itemize}
  ðÒÉÎÑ× ÔÏÞËÕ ÚÒÅÎÉÑ ÎÁÛÅÇÏ ÉÓÓÌÅÄÏ×ÁÎÉÑ, ÜÔÉ ÔÒÉ ÓÌÕÞÁÑ
  ÍÏÖÎÏ ÐÏÑÓÎÉÔØ ÔÁË.

  ÷ ÐÅÒ×ÏÍ ÓÌÕÞÁÅ (\emph{<<ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ>> Ó
  <<ÉÄÅÍÐÏÔÅÎÔÎÏÊ>> ÓÅÍÁÎÔÉËÏÊ}) 
  ÍÙ ÉÍÅÅÍ ÄÅÌÏ Ó ÐÒÏÉÚ×ÏÌØÎÙÍÉ ÐÒÏÇÒÁÍÍÁÍÉ\T ×ÓÅÍÉ
  ÓÉÎÔÁËÓÉÞÅÓËÉ ÐÒÁ×ÉÌØÎÏ ÓÏÓÔÁ×ÌÅÎÎÙÍÉ ÐÒÏÇÒÁÍÍÁÍÉ, Á × ÓÅÍÁÎÔÉÞÅÓËÉÈ ÍÏÄÅÌÑÈ
  ÏÐÅÒÁÃÉÑ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÇÏ ×ÙÂÏÒÁ 
  ÉÎÔÅÒÐÒÅÔÉÒÕÅÔÓÑ ÉÄÅÍÐÏÔÅÎÔÎÏ 
  ($x + x = x$). üÔÏ\T \emph{ÏÓÏÂÅÎÎÏÓÔØ ÓÅÍÁÎÔÉËÉ}, 
  × ËÏÔÏÒÏÊ ÍÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ÐÒÏÇÒÁÍÍÙ, ÓÏÂÓÔ×ÅÎÎÏ ÎÉËÁËÉÈ
  \emph{ÏÓÏÂÅÎÎÏÓÔÅÊ ÐÒÏÇÒÁÍÍ}
  × ÜÔÏÍ ÓÌÕÞÁÅ ÍÙ ÎÅ ÕÓÍÁÔÒÉ×ÁÅÍ.

  ôÒÅÔÉÊ ÓÌÕÞÁÊ (\emph{ÐÒÏÇÒÁÍÍÙ Ó ÓÅÍÁÎÔÉËÏÊ Ó ËÒÁÔÎÏÓÔÑÍÉ})
  ÓÉÍÍÅÔÒÉÞÅÎ ÐÅÒ×ÏÍÕ. ÷ Î£Í × ÓÅÍÁÎÔÉÞÅÓËÉÈ ÍÏÄÅÌÑÈ
  ÐÒÉ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÇÏ ×ÙÂÏÒÁ
  ÕÞÉÔÙ×ÁÅÔÓÑ ËÒÁÔÎÏÓÔØ ÚÎÁÞÅÎÉÊ, ÏÂÙÞÎÏ\T × ÐÒÏÔÉ×ÏÐÏÌÏÖÎÏÓÔØ ÐÅÒ×ÏÍÕ
  ÓÌÕÞÁÀ\T ÎÅ ÉÄÅÍÐÏÔÅÎÔÎÙÍ ÏÂÒÁÚÏÍ (ÎÁÐÒÉÍÅÒ, $x + x = 2x$).
  ðÒÏÇÒÁÍÍÙ ÏÐÑÔØ ÉÍÅÀÔ ÓÁÍÙÊ ÏÂÝÉÊ ×ÉÄ. (÷ÏÚÍÏÖÎÏÓÔØ ÒÁÓÛÉÒÅÎÉÑ
  ÓÉÎÔÁËÓÉÓÁ ÐÒÏÇÒÁÍÍ ÚÁ ÓÞ£Ô Ñ×ÎÏÇÏ ÄÏÂÁ×ÌÅÎÉÑ ËÒÁÔÎÏÓÔÅÊ × ÜÔÏÍ
  ÓÌÕÞÁÅ ÄÌÑ ÎÁÓ ÎÅ ÐÒÉÎÃÉÐÉÁÌØÎÁ.) \Te É × ÜÔÏÍ ÓÌÕÞÁÅ ÍÙ ÉÍÅÅÍ ×
  ×ÉÄÕ \emph{ÏÓÏÂÅÎÎÏÓÔØ ÓÅÍÁÎÔÉËÉ}, ÎÏ ÎÅ ËÁËÉÅ-ÔÏ \emph{ÏÓÏÂÅÎÎÏÓÔÉ
    ÐÒÏÇÒÁÍÍ}.
  
  ïÂÁ ÜÔÉÈ ÓÌÕÞÁÑ\T ÓÉÌØÎÙÅ ÏÂÏÂÝÅÎÉÑ, ÓÄÅÌÁÎÎÙÅ × ÒÁÍËÁÈ ÍÅÔÁÔÅÏÒÉÉ 
  ÁÂÓÔÒÁËÃÉÊ ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ. (ðÏ ËÒÁÊÎÅÊ ÍÅÒÅ, ÍÙ ÐÒÉÍÅÍ ÔÁËÏÊ
  ×ÚÇÌÑÄ ÎÁ ×ÅÝÉ.) ÷ÔÏÒÏÊ ÓÌÕÞÁÊ (\emph{ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ
    É ÏÄÎÏÚÎÁÞÎÙÅ ÐÒÏÇÒÁÍÍÙ})
  ÂÏÌØÛÅ ÐÒÉÂÌÉÖÅÎ Ë Ó×ÏÊÓÔ×ÁÍ ÒÅÁÌØÎÙÈ
  ÐÒÏÇÒÁÍÍ. \emph{äÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ} ÎÁÐÉÓÁÎÙ ÔÁË,
  ÞÔÏÂÙ ×ÅÓÔÉ ÓÅÂÑ ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÍ ÏÂÒÁÚÏÍ ÐÒÉ ×ÙÞÉÓÌÅÎÉÉ, 
  \te ÞÔÏÂÙ ÓÌÅÄÕÀÝÉÊ ÛÁÇ
  ×ÙÞÉÓÌÅÎÉÑ × ËÁÖÄÙÊ ÍÏÍÅÎÔ ×ÙÞÉÓÌÅÎÉÑ ÏÐÒÅÄÅÌÑÌÓÑ ÅÄÉÎÓÔ×ÅÎÎÙÍ
  ÏÂÒÁÚÏÍ (ÐÒÉ ÎÅËÏÔÏÒÙÈ ÏÓÏÂÙÈ ÏÇÏ×ÏÒÅÎÎÙÈ ÚÁÒÁÎÅÅ ÉÎÔÅÒÐÒÅÔÁÃÉÑÈ,
  ÐÒÅÄÓÔÁ×ÌÑÀÝÉÈ ÓÏÂÏÊ ÎÅËÏÔÏÒÕÀ <<ÓÔÁÎÄÁÒÔÎÕÀ>> ÓÅÍÁÎÔÉËÕ). ôÅÍ ÓÁÍÙÍ
  × ÜÔÏÍ ÓÌÕÞÁÅ ÍÙ ÏÇÒÁÎÉÞÉ×ÁÅÍ ËÒÕÇ ÐÒÉÎÉÍÁÅÍÙÈ Ë ÒÁÓÓÍÏÔÒÅÎÉÀ
  ÐÒÏÇÒÁÍÍ ÕËÁÚÁÎÎÙÍ ×ÙÛÅ \emph{ÓÅÍÁÎÔÉÞÅÓËÉÍ Ó×ÏÊÓÔ×ÏÍ ÐÒÏÇÒÁÍÍ}
  (\emph{ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÓÔØÀ}). \emph{ïÄÎÏÚÎÁÞÎÏÓÔØ}\T ÔÏÖÅ
  \emph{ÓÅÍÁÎÔÉÞÅÓËÏÅ Ó×ÏÊÓÔ×Ï ÐÒÏÇÒÁÍÍ}\T ÕÄÏÂÎÏÅ
  ÔÅÏÒÅÔÉÞÅÓËÏÅ  ÏÂÏÂÝÅÎÉÅ Ó×ÏÊÓÔ×Á ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÓÔÉ ÐÒÏÇÒÁÍÍ.
  úÁ ÂÏÌÅÅ ÔÏÞÎÙÍÉ ÏÐÒÅÄÅÌÅÎÉÑÍÉ ÍÙ ÏÔÓÙÌÁÅÍ ÞÉÔÁÔÅÌÑ Ë ÏÓÎÏ×ÎÏÊ
  ÞÁÓÔÉ\T òÁÚÄÅÌÁÍ~\ref{sec:free-plain-det},
  \ref{sec:free-withTests-det}, \ref{sec:hypo-plain-det},
  \ref{sec:hypo-withTests-det}; ÚÄÅÓØ ÌÉÛØ ÐÏÑÓÎÉÍ ÓÏÏÔÎÏÛÅÎÉÅ ÍÅÖÄÕ
  ÎÉÍÉ ÔÁË: ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÓÔØ\T Ó×ÏÊÓÔ×Ï, ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÑÅÔÓÑ ÐÏ
  ÐÒÏÇÒÁÍÍÅ ÓÉÎÔÁËÓÉÞÅÓËÉ <<ÌÏËÁÌØÎÏ>> (ÄÏÓÔÁÔÏÞÎÏ ÐÏÓÍÏÔÒÅÔØ ÎÁ
  ÓÅÍÁÎÔÉÞÅÓËÉÅ Ó×ÏÊÓÔ×Á ËÁÖÄÏÇÏ ÏÔÄÅÌØÎÏÇÏ ÕÚÌÁ ÐÒÏÇÒÁÍÍÙ), 
  Á ÏÄÎÏÚÎÁÞÎÏÓÔØ\T <<ÇÌÏÂÁÌØÎÏ>> (ÎÕÖÎÏ ÐÒÏ×ÅÒÉÔØ Ó×ÏÊÓÔ×Ï ×ÓÅÈ ÔÒÁÓÓ
  ×ÙÞÉÓÌÅÎÉÊ, ÉÄÕÝÉÈ ÞÅÒÅÚ ÓÔÒÕËÔÕÒÕ ÐÒÏÇÒÁÍÍÙ, × ÓÔÁÎÄÁÒÔÎÏÊ ÓÅÍÁÎÔÉËÅ).

  ÷ÔÏÒÏÊ ÓÌÕÞÁÊ\T ÜÔÏ ÔÅ ÐÒÏÇÒÁÍÍÙ, ÇÄÅ ÏÂÁ ÏÂÝÉÈ ×ÚÇÌÑÄÁ ÎÁ ÐÒÏÇÒÁÍÍÙ
  ÐÅÒ×ÏÇÏ É ÔÒÅÔØÅÇÏ ÓÌÕÞÁÑ\T
  ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ × <<ÉÄÅÍÐÏÔÅÎÔÎÏÊ>> ÓÅÍÁÎÔÉËÅ É × ÓÅÍÁÎÔÉËÅ Ó
  ËÒÁÔÎÏÓÔÑÍÉ\T
  <<ÓÏ×ÐÁÄÁÀÔ>>. 
  äÌÑ ÎÁÛÅÇÏ ÉÓÓÌÅÄÏ×ÁÎÉÑ ÜÔÏÔ ÓÌÕÞÁÊ, ×Ï-ÐÅÒ×ÙÈ,
  ÐÒÅÄÓÔÁ×ÌÑÅÔ ÂÏÌØÛÏÊ ÓÁÍÏÓÔÏÑÔÅÌØÎÙÊ ÉÎÔÅÒÅÓ (××ÉÄÕ ÐÒÁËÔÉÞÅÓËÏÊ
  ÐÒÉÍÅÎÉÍÏÓÔÉ ÒÅÚÕÌØÔÁÔÏ× × Î£Í), ×Ï-×ÔÏÒÙÈ, ÚÁÎÉÍÁÅÔ
  ÐÅÒÅÈÏÄÎÏÅ ÍÅÓÔÏ ÍÅÖÄÕ Ä×ÕÍÑ ÍÅÔÁÔÅÏÒÉÑÍÉ, ÏÔ×ÅÞÁÀÝÉÍÉ Ä×ÕÍ ÄÒÕÇÉÍ
  ÓÌÕÞÁÑÍ, × Î£Í ÍÏÖÎÏ ÓÏÅÄÉÎÑÔØ ÍÅÔÏÄÙ É ÒÅÚÕÌØÔÁÔÙ ÉÚ ÎÉÈ ÏÂÏÉÈ,
  ÓÔÁ×ÉÔØ ÄÌÑ ÎÉÈ ×ÏÐÒÏÓÙ.

  ïÔÍÅÔÉÍ, ÞÔÏ ÐÒÉÎÑÔÙÅ <<ËÌÀÞÅ×ÙÅ ÓÌÏ×Á>> ÎÅ ÌÕÞÛÉÍ ÏÂÒÁÚÏÍ ÏÔÒÁÖÁÀÔ
  ÎÁÛÕ ÔÏÞËÕ ÚÒÅÎÉÑ ÎÁ ÜÔÏ ÄÅÌÅÎÉÅ, ÎÁÐÒÉÍÅÒ, ÓÌÕÞÁÊ, ÎÁÚ×ÁÎÎÙÊ
  <<ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ>>, ÐÒÉ ÎÁÛÅÊ ÔÏÞËÅ ÚÒÅÎÉÑ ÎÅ Ó×ÑÚÁÎ
  Ó ÏÓÏÂÙÍÉ Ó×ÏÊÓÔ×ÁÍÉ ÐÒÏÇÒÁÍÍ, Á Ó×ÑÚÁÎ ÓÏ Ó×ÏÊÓÔ×ÁÍÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ
  ÍÏÄÅÌÅÊ, × ËÏÔÏÒÙÈ ÉÈ ÉÎÔÅÒÐÒÅÔÉÒÕÀÔ.

  ðÒÉÍÅÒ ÜÔÏÇÏ ÄÅÌÅÎÉÑ × ÐÒÏÓÔÏÍ ÓÌÕÞÁÅ (çÌÁ×Ù~\ref{cha:free-plain}): 
  ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ËÏÎÅÞÎÙÅ Á×ÔÏÍÁÔÙ (ËÁË
  Ä×ÕÓÔÏÒÏÎÎÉÅ ÓÕÝÎÏÓÔÉ Ó ÓÉÎÔÁËÓÉÓÏÍ É ÓÅÍÁÎÔÉËÏÊ), ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ
  ËÏÎÅÞÎÙÅ Á×ÔÏÍÁÔÙ, Á×ÔÏÍÁÔÙ Ó ËÒÁÔÎÏÓÔÑÍÉ.
\end{description}
\begin{table}[htbp]
  \centering
\begin{tabular}{p{.08\textwidth}|c||p{.15\textwidth}|p{.15\textwidth}|p{.15\textwidth}||p{.1\textwidth}|}
\multicolumn{2}{c||}{áÂÓÔÒÁËÃÉÉ}\\
ÐÏÒÑÄÏË
É ÐÏÓÔÕÌÁÔÙ
& ÔÅÓÔÙ?
& ÎÅÄÅÔÅÒÍ.
& ÏÄÎÏÚÎÁÞÎ. $\supset$ ÄÅÔÅÒÍ.
& Ó ËÒÁÔÎÏÓÔÑÍÉ
& ×ÎÉÍÁÎÉÅ Ë\\
\hline\hline
\multirow{2}{*}{0}
& $\Sigma$
& 
\begin{tabular}{l}
$\RExp_{\Sigma}$\\
\hline
$\NFA_{\Sigma}$
\end{tabular}
& $\DFA_{\Sigma}$
& 
& 
$\EOf\KA$, $\preS\EOf\KA$
\\
\hhline{~-*{4}{-}}
& $\Sigma,T$
& 
\begin{tabular}{l}
$\RExp_{\Sigma,T}$\\
\hline
%$\NPS_{\Sigma,T}$ 
AGS
\end{tabular}
& 
%$\DPS_{\Sigma,T}$ 
DAGS
& 
& 
$\EOf\KAT$, $\preS\EOf\KAT$
\\
\hline\hline
\multirow{2}{*}{0, ÐÏÓÔ.}
& $\Sigma$
& 
\begin{tabular}{l}
$\RExp_{\Sigma}$\\
\hline
(NMTA)
\end{tabular}
& (DMTA)
& 
& $\HOf\KA$, $\preS\HOf\KA$
\\
\hhline{~-*{4}{-}}
& $\Sigma, T$
& 
& 
& 
& 
$\HOf\KAT$, $\preS\HOf\KAT$
\\
\hline\hline
$$
\begin{array}{c}
1 \\
\vdots
\end{array}
$$
& % tests
& \multicolumn{3}{|c|}{}
%& % ndet
%& % det
%& % multi
& % by what kind of theory
\end{tabular}
  \caption{ëÁÒÔÁ ÒÁÂÏÔÙ}
  \label{tab:map}
\end{table}

÷Ï ×ÓÅÈ ÓÌÕÞÁÑÈ ÍÙ ÎÁÃÅÌÅÎÙ ÎÁ ÉÓÓÌÅÄÏ×ÁÎÉÅ ðü, ËÁË ÜÔÏ ÂÙÌÏ ÚÁÑ×ÌÅÎÏ
ÐÒÉ ÐÏÓÔÁÎÏ×ËÅ ÉÎÔÅÒÅÓÕÀÝÉÈ ÎÁÓ ×ÏÐÒÏÓÏ×, ÉÓÓÌÅÄÏ×ÁÎÉÅ ÏÓÎÏ×ÁÎÏ ÎÁ
ÉÚÕÞÅÎÉÉ Ó×ÏÊÓÔ× ÁÌÇÅÂÒ ëÌÉÎÉ É ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ, × ÞÁÓÔÎÏÓÔÉ,
ÎÁÓ ÉÎÔÅÒÅÓÕÀÔ ÏÔÎÏÛÅÎÉÑ ÍÅÖÄÕ ÍÏÄÅÌÑÍÉ É ÉÈ ÓÔÒÏÅÎÉÅ, ÒÁÓÐÒÏÓÔÒÁÎÅÎÉÅ
ÉÚ×ÅÓÔÎÙÈ Ó×ÑÚÅÊ ÎÁ ÓÌÕÞÁÉ ÎÅÉÚ×ÅÓÔÎÏÓÔÉ (ÜÔÏ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÖÅÌÁÎÉÀ
ÐÏÎÑÔØ, ËÁË ÍÏÖÎÏ ÐÒÉÍÅÎÑÔØ ÍÅÔÏÄ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DMTA
×Ï ×ÓÅÊ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÊ ÏÂÌÁÓÔÉ, ÐÒÏ ËÏÔÏÒÏÅ ÕÖÅ ÇÏ×ÏÒÉÌÏÓØ
ÐÏÄÒÏÂÎÅÅ).
éÚ×ÅÓÔÎÙÅ É ÎÏ×ÙÅ ÆÁËÔÙ ÍÙ ÈÏÔÉÍ ÐÒÅÄÓÔÁ×ÉÔØ ÓÉÓÔÅÍÁÔÉÞÅÓËÉ.

\paragraph{õÒÏ×ÎÉ ÕÓÌÏÖΣÎÎÏÓÔÉ.}
\begin{description}
\item[$\Sigma$ (ÏÐÅÒÁÔÏÒÙ), ÂÅÚ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×.] 
  óÏÄÅÒÖÁÎÉÅ çÌÁ×Ù~\ref{cha:free-plain} ÏÓÎÏ×ÁÎÏ ÎÁ ËÌÁÓÓÉÞÅÓËÏÊ ôÅÏÒÉÉ
  Á×ÔÏÍÁÔÏ× (ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ, ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ, Ó ËÒÁÔÎÏÓÔÑÍÉ) É
  ÒÅÇÕÌÑÒÎÙÈ ÑÚÙËÏ×,
  ÉÚÌÏÖÅÎÎÏÊ × ÐÒÉÌÏÖÅÎÉÉ Ë ÉÓÓÌÅÄÏ×ÁÎÉÀ Ó×ÏÊÓÔ× ÍÏÄÅÌÅÊ ÁÌÇÅÂÒ ëÌÉÎÉ,
  ÜË×ÁÃÉÏÎÁÌØÎÙÈ ÔÅÏÒÉÊ ÉÈ ËÌÁÓÓÏ× (ÐÒÅÄÓÔÁ×ÌÑÀÝÉÈ ðü × ÜÔÏÊ ÒÁÂÏÔÅ).
  úÁÔÒÏÎÕÔÙÅ ×ÏÐÒÏÓÙ ôÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ × ÔÁËÏÊ ÐÏÓÔÁÎÏ×ËÅ ÂÙÌÉ × ÎÅËÏÔÏÒÏÍ
  ÓÍÙÓÌÅ ÐÏÌÎÏÓÔØÀ ÚÁËÒÙÔÙ × ÎÅ ÔÁËÏÊ ÄÁ×ÎÅÊ ÒÁÂÏÔÅ \cite{KA-regevents-complete}
  ÐÒÉÍÅÎÅÎÉÅÍ ËÌÁÓÓÉÞÅÓËÉÈ ÒÅÚÕÌØÔÁÔÏ× ôÅÏÒÉÉ Á×ÔÏÍÁÔÏ×.
\item [$\Sigma, T$ (ÏÐÅÒÁÔÏÒÙ É ÔÅÓÔÙ), ÂÅÚ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×.]
  çÌÁ×Á~\ref{cha:free-withTests} ÐÏÓ×ÑÝÅÎÁ ÕÖÅ ôÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ Ó
  ÔÅÓÔÁÍÉ \cite{KAT??}, ÓÌÕÖÁÝÉÈ ÄÌÑ ÁÎÁÌÉÚÁ ÂÏÌÅÅ ÓÌÏÖÎÏ ÕÓÔÒÏÅÎÎÙÈ
  ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ (Ó ÔÅÓÔÁÍÉ). äÏ×ÏÌØÎÏ ÂÙÓÔÒÏ ÐÏÓÌÅ ÎÁÞÁÌØÎÏÊ ÐÏÓÔÁÎÏ×ËÉ
  ×ÏÐÒÏÓÙ ôÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ ÂÙÌÉ ÚÁËÒÙÔÙ \cite{KAT-??,
  AGS, ??} ÍÅÔÏÄÁÍÉ,
  ÐÅÒÅÎÅÓ£ÎÎÙÍÉ ÉÚ ôÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ.
  îÁÍ ×ÁÖÎÏ ÐÏÎÑÔØ, ÞÔÏ ÐÒÏÉÓÈÏÄÉÔ ÐÒÉ ÔÁËÏÍ ÕÓÌÏÖÎÅÎÉÉ ÍÅÔÁÔÅÏÒÉÉ.
\item[$\Sigma$ (ÏÐÅÒÁÔÏÒÙ), Ó ÓÅÍÁÎÔÉÞÅÓËÉÍÉ ÐÏÓÔÕÌÁÔÁÍÉ] 
  ÷ÏÐÒÏÓÙ çÌÁ×Ù~\ref{cha:hypo-plain}
  Ó×ÑÚÁÎÙ Ó ÏÂÏÂÝÅÎÉÅÍ ôÅÏÒÉÉ Á×ÔÏÍÁÔÏ× (ÎÁÐÒÉÍÅÒ, ÎÁ
  ÐÒÏÉÚ×ÏÌØÎÙÅ ÍÏÎÏÉÄÙ ×ÍÅÓÔÏ ÍÏÎÏÉÄÁ ËÏÎÅÞÎÙÈ ÓÔÒÏË~$\Sigma^*$, 
  × ÔÏÍ ÞÉÓÌÅ, ÍÎÏÇÏÌÅÎÔÏÞÎÙÅ Á×ÔÏÍÁÔÙ). 
  ïÔÄÅÌØÎÙÅ ×ÏÐÒÏÓÙ ÓÔÏÑÌÉ ÄÏÌÇÏ (ðü DMTA \cite{RS}\T ËÁËÏ×Ï ÂÙÌÏ
  ÐÒÏÍÅÖÕÔÏÞÎÏÅ ÓÏÓÔÏÑÎÉÅ ÉÓÓÌÅÄÏ×ÁÎÉÊ ÍÏÖÎÏ ÕÚÎÁÔØ ÉÚ \cite[çÌÁ×Á~3]{KotSab}), 
  ÂÙÌÉ ÒÅÛÅÎÙ ÎÅÄÁ×ÎÏ (\cite{HK}), É ÔÅÍÁ ÎÁÛÉÈ ÉÓÓÌÅÄÏ×ÁÎÉÊ ÉÈ
  ÂÅÚÕÓÌÏ×ÎÏ ÚÁÈ×ÁÔÙ×ÁÅÔ. 
  
  ôÕÔ ÍÙ ÓÉÓÔÅÍÁÔÉÚÉÒÕÅÍ ÉÚ×ÅÓÔÎÙÅ ÒÁÚÎÏÒÏÄÎÙÅ ÒÅÚÕÌØÔÁÔÙ × ÐÒÉÍÅÎÅÎÉÉ
  Ë ×ÏÐÒÏÓÁÍ ôÅÏÒÉÉ ÁÌÇÅÂÒ ëÌÉÎÉ, ÐÏÌÕÞÁÅÍ ÓÌÅÄÓÔ×ÉÑ ÉÚ
  ÎÉÈ, ÞÔÏÂÙ ÍÁËÓÉÍÁÌØÎÏ ÐÏËÒÙÔØ ÉÓÓÌÅÄÕÅÍÏÅ ÐÏÌÅ.

\item[$\Sigma,T$ (ÏÐÅÒÁÔÏÒÙ É ÔÅÓÔÙ), Ó ÓÅÍÁÎÔÉÞÅÓËÉÍÉ ÐÏÓÔÕÌÁÔÁÍÉ] 
  çÌÁ×Á~\ref{cha:hypo-withTests} ÚÁÎÉÍÁÅÔÓÑ  
  ÎÁÉÂÏÌÅÅ ÓÌÏÖÎÙÍÉ ÁÂÓÔÒÁËÃÉÑÍÉ ÐÒÏÇÒÁÍÍ × ÉÓÓÌÅÄÕÅÍÏÍ ÐÏÌÅ. 
  úÄÅÓØ ÂÙÌÉ É ÏÓÔÁÀÔÓÑ ÏÔËÒÙÔÙÅ ×ÏÐÒÏÓÙ ÒÁÚÎÏÇÏ ÒÏÄÁ. 
  íÙ ÐÒÅÄÌÁÇÁÅÍ ÐÕÔÉ ÐÏÉÓËÁ ÏÔ×ÅÔÏ× ÎÁ ÎÉÈ, ÚÁÍÅÞÁÑ ÎÅËÏÔÏÒÙÅ ÎÏ×ÙÅ
  ÐÏÓÔÒÏÅÎÉÑ. ÷ ÐÒÅÄÙÄÕÝÉÈ 3 çÌÁ×ÁÈ ÓÏÄÅÒÖÁÔÓÑ ÍÅÔÏÄÙ  É ÒÅÚÕÌØÔÁÔÙ,
  ÐÅÒÅÎÏÓ ËÏÔÏÒÙÈ ÎÁ ÜÔÏÔ ÓÌÕÞÁÊ ÎÁÓ ÚÁÎÉÍÁÅÔ.

  îÁÐÒÉÍÅÒ, × çÌÁ×Å~\ref{cha:hypo-withTests} ÍÅÓÔÏ \tND{ÎÁÓÙÝÅÎÎÙÈ
    ÓÔÒÏË}{def:gs} ÉÚ  çÌÁ×Ù~\ref{cha:free-withTests}
  ÚÁÎÉÍÁÀÔ ÐÏÓÔÒÏÅÎÉÑ ÎÁ ÏÓÎÏ×Å \tND{ÛËÁÌ ëÒÉÐËÅ}{def:kf-Sigma-T},
  ÐÒÉ ÜÔÏÍ ÄÌÑ ÕÓÌÏÖΣÎÎÏÊ ËÏÎÓÔÒÕËÃÉÉ ÏÓÔÁÀÔÓÑ ÏÔËÒÙÔÙÍÉ ×ÏÐÒÏÓÙ,
  ÏÔ×ÅÔÙ ÎÁ ËÏÔÏÒÙÅ ÍÙ ÚÎÁÅÍ × ÂÏÌÅÅ ÐÒÏÓÔÏÍ ÓÌÕÞÁÅ:
  ÁÌÇÅÂÒÁ 
  ÍÎÏÖÅÓÔ× \tND{ÎÁÓÙÝÅÎÎÙÈ ÓÔÒÏË}{def:gs} ÉÚ
  çÌÁ×Ù~\ref{cha:free-withTests} Ñ×ÌÑÅÔÓÑ Ó×ÏÂÏÄÎÏÊ × ÔÒ£È ×ÁÖÎÙÈ
  ËÌÁÓÓÁÈ ÁÌÇÅÂÒ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ, Á ÐÒÏ Å£ ÁÎÁÌÏÇ ×
  çÌÁ×Å~\ref{cha:hypo-withTests} ÎÁ ÏÓÎÏ×Å ÛËÁÌ ëÒÉÐËÅ ÐÏÄÏÂÎÙÅ ÆÁËÔÙ
  ÎÅÉÚ×ÅÓÔÎÙ\T ÓÍ. ïÔËÒÙÔÙÊ ×ÏÐÒÏÓ~\ref{pro:Reg-t-E-free}.
\end{description}

÷ÏÏÂÝÅ, ÍÅÔÁÔÅÏÒÉÑ \KAT ÕÓÌÏÖÎÑÌÁÓØ, ÞÔÏÂÙ ÒÁÂÏÔÁÔØ É Ó ÁÂÓÔÒÁËÃÉÑÍÉ
ÐÒÏÇÒÁÍÍ 1\dÇÏ ÐÏÒÑÄËÁ \cite{KAT-schematology,dynamic-model}, ÎÏ ÍÙ ×
ÜÔÉÈ ×ÏÐÒÏÓÏ× ÎÅ ËÁÓÁÅÍÓÑ.

\paragraph{òÁÚÎÏ×ÉÄÎÏÓÔÉ ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ.}
äÌÑ ËÁÖÄÏÇÏ ÓÌÕÞÁÑ, Ó×ÑÚÁÎÎÏÇÏ Ó ÏÓÏÂÅÎÎÏÓÔÑÍÉ ÓÅÍÁÎÔÉËÉ\T
ÓÌÕÞÁÑ <<ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ>>, ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÐÒÏÇÒÁÍÍ É <<ÐÒÏÇÒÁÍÍ Ó
ËÒÁÔÎÏÓÔÑÍÉ>>\T ÐÒÏÂÌÅÍÙ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÓÏ×ÅÒÛÅÎÎÏ ÎÅÐÏÈÏÖÉ, ÎÁËÏÐÌÅÎÙ
ÒÁÚÎÙÅ ÐÏÄÈÏÄÙ Ë ÉÈ ÉÓÓÌÅÄÏ×ÁÎÉÀ É ÎÅÐÏÈÏÖÉÅ ÒÅÚÕÌØÔÁÔÙ.

\begin{description}
\item[óÌÕÞÁÊ Ó ËÒÁÔÎÏÓÔÑÍÉ]\T ÜÔÁ ÏÂÌÁÓÔØ ÉÓÓÌÅÄÏ×ÁÎÉÑ ÄÌÑ ÎÁÓ,
  ÓËÏÒÅÅ, ÉÓÔÏÞÎÉË ×ÓÐÏÍÏÇÁÔÅÌØÎÏÊ ÔÅÈÎÉËÉ ÄÌÑ ÒÅÛÅÎÉÑ ðü
  ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ É ÏÄÎÏÚÎÁÞÎÙÈ ÐÒÏÇÒÁÍÍ.
\item[óÌÕÞÁÊ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÓÔÉ]\T Ó ÜÔÏÇÏ ÓÌÕÞÁÑ ÍÙ ÎÁÞÉÎÁÅÍ
  ÒÁÓÓÍÏÔÒÅÎÉÅ. îÁ Î£Í ÍÙ ÉÚÕÞÁÅÍ ×ÙÂÒÁÎÎÙÊ ÐÏÄÈÏÄ Ë ÏÐÒÅÄÅÌÅÎÉÀ
  ÓÅÍÁÎÔÉËÉ ÐÒÏÇÒÁÍÍ, ÕÓÔÒÏÊÓÔ×Ï ÍÏÄÅÌÅÊ ÁÌÇÅÂÒ ëÌÉÎÉ (Ó ÔÅÓÔÁÍÉ), 
  ÓÏÏÔÎÏÛÅÎÉÅ ÍÅÖÄÕ ÎÉÍÉ, ×ÙÑÓÎÑÅÍ ×ÚÁÉÍÎÏÅ ÒÁÓÐÏÌÏÖÅÎÉÅ
  ÒÁÚÎÙÈ ÓÌÕÞÁÅ× ÐÏ ÓÌÏÖÎÏÓÔÉ ÒÅÛÅÎÉÑ ðü. üÔÏ ÐÏÍÏÇÁÅÔ ×ÙÄÅÌÉÔØ 
  ËÌÁÓÓÙ ÍÏÄÅÌÅÊ É Ó×ÑÚÉ ÍÅÖÄÕ ÎÉÍÉ, ËÏÔÏÒÙÅ ÏÓÔÁÎÕÔÓÑ ×ÁÖÎÙÍÉ É
  ÉÓÓÌÅÄÏ×ÁÎÉÑÈ ×ÎÅ ÜÔÏÇÏ ÓÌÕÞÁÑ, ÎÁÐÒÉÍÅÒ, ÐÒÉ
  ÉÚÕÞÅÎÉÉ ðü ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÐÒÏÇÒÁÍÍ. ðÒÉ ÜÔÏÍ ÐÏÌÏÖÉÔÅÌØÎÙÈ
  ÒÅÚÕÌØÔÁÔÏ× Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü × ÓËÏÌØ-ÎÉÂÕÄØ ÓÌÏÖÎÙÈ ÍÏÄÅÌÑÈ × ÜÔÏÍ
  ÓÌÕÞÁÅ ÏÖÉÄÁÔØ ÎÅ ÐÒÉÈÏÄÉÔÓÑ (ÎÏ ÏÎÉ ×Ó£ ÒÁ×ÎÏ ËÌÁÓÓÉÆÉÃÉÒÕÀÔÓÑ ÐÏ
  ÎÅÒÁÚÒÅÛÉÍÙÍ ÓÌÏÖÎÏÓÔÑÍ).
\item[óÌÕÞÁÊ ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÐÒÏÇÒÁÍÍ]\T
  ÓÌÕÞÁÊ, ÐÒÅÄÓÔÁ×ÌÑÀÝÉÊ ÏÓÎÏ×ÎÏÊ ÐÒÁËÔÉÞÅÓËÉÊ ÉÎÔÅÒÅÓ. úÄÅÓØ É
  ÅÓÔØ ÓÕÝÅÓÔ×ÅÎÎÙÅ ÐÏÌÏÖÉÔÅÌØÎÙÅ ÒÅÚÕÌØÔÁÔÙ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ. òÁÚÎÏÂÏÊ É
  ÎÅÄÏÓÔÁÔÏÞÎÁÑ ÏÂÝÎÏÓÔØ ÐÒÅÄÌÁÇÁÅÍÙÈ ÆÏÒÍÁÌÉÚÁÃÉÊ
  ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÓÔÉ É ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÏÔÞÁÓÔÉ ÏÂßÑÓÎÑÅÔÓÑ ÔÅÍ, ÞÔÏ ÜÔÏ ÐÏÐÙÔËÉ
  ÐÒÉÂÌÉÚÉÔØÓÑ Ë ×ÏÚÎÉËÁÀÝÉÍ ÎÁ ÐÒÁËÔÉËÅ ÕÓÌÏ×ÉÑÍ, ÔÁË, ÞÔÏÂÙ ÏÂÝÎÏÓÔØ
  ÎÅ ÐÒÅÐÑÔÓÔ×Ï×ÁÌÁ ÐÏÌÕÞÅÎÉÀ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÒÅÚÕÌØÔÁÔÏ×. ÷ ÜÔÏÍ ÓÌÕÞÁÅ
  ÎÁÈÏÄÉÔÓÑ ÏÓÎÏ×ÎÁÑ ÍÁÓÓÁ ÏÔËÒÙÔÙÈ ×ÏÐÒÏÓÏ× Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü,
  ËÏÔÏÒÙÅ ÓÔÏÑÔ ÐÅÒÅÄ ÎÁÍÉ.
\end{description}


%\section{óÐÉÓÏË (ÏÂÚÏÒ) ÒÁÓÓÍÏÔÒÅÎÎÙÈ ÐÏÄÈÏÄÏ× É ÒÅÚÕÌØÔÁÔÏ×}

%% ÄÏ×ÏÌØÎÏ ÎÏ×ÙÊ ÐÏÄÈÏÄ -- ËÏÌØÃÏ Ó ÄÅÌÅÎÉÑÍÉ \cite{HK} 
%% KAT \cite{KAT} ....

%\section{÷ËÌÁÄ ÄÁÎÎÏÊ ÒÁÂÏÔÙ (ÃÅÎÎÏÓÔØ, ÎÏ×ÉÚÎÁ)}
%\label{sec:contributions}




%% \section{ðÒÉÌÏÖÅÎÉÑ ÎÁ ÐÒÁËÔÉËÅ}
%% \label{sec:applications}

%% \todo{[..]}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: