free-plain-multi.tex

   1 \subsection{áÌÇÅÂÒÙ Ó ËÒÁÔÎÏÓÔÑÍÉ ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ}
   2 \label{sec:S-KA}
   3
   4 \todo{[ÎÁÊÔÉ ÔÅÒÍÉÎÏÌÏÇÉÀ/ÏÂÏÚÎÁÞÅÎÉÑ ÄÒÕÇÉÈ Á×ÔÏÒÏ× ÄÌÑ ÔÁËÉÈ
   5   ÁÌÇÅÂÒ]}
   6
   7
   8 ôÅÐÅÒØ ÍÙ ÂÕÄÅÍ ÄÏÐÕÓËÁÔØ × ËÁÞÅÓÔ×Å ÍÏÄÅÌÅÊ, ÓÌÕÖÁÝÉÈ ÄÌÑ ÉÎÔÅÒÐÒÅÔÁÃÉÉ
   9 ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ, ÂÏÌÅÅ ÛÉÒÏËÉÊ ËÌÁÓÓ ÏÂßÅËÔÏ×, ÞÅÍ ÁÌÇÅÂÒÙ ëÌÉÎÉ,
  10 ÏÐÉÓÁÎÎÙÅ ×~òÁÚÄÅÌÅ~\ref{sec:KA}. íÙ ÂÕÄÅÍ ÎÁÚÙ×ÁÔØ ÉÈ \tING{ÁÌÇÅÂÒÁÍÉ Ó
  11   ËÒÁÔÎÏÓÔÑÍÉ ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ},\footnote{îÅ ÎÁÄÏ ÄÕÍÁÔØ, ÞÔÏ ÜÔÏ
  12 ÏÂÝÅÐÒÉÎÑÔÏÅ ÎÁÚ×ÁÎÉÅ, ÏÎÏ ×ÙÂÒÁÎÏ ÄÌÑ ÕÄÏÂÓÔ×Á ÉÚÌÏÖÅÎÉÑ × ÜÔÏÊ
  13 ÒÁÂÏÔÅ.}
  14 ÉÌÉ ÐÒÏÓÔÏ \tING{ÁÌÇÅÂÒÁÍÉ Ó ËÒÁÔÎÏÓÔÑÍÉ},
  15 ÉÌÉ \tING{$\sr S$\dÁÌÇÅÂÒÁÍÉ}, ÉÍÅÑ × ×ÉÄÕ, ÞÔÏ $\sr
  16 S$\T ÍÅÔÁÐÅÒÅÍÅÎÎÁÑ ÐÏ ÐÏÌÕËÏÌØÃÁÍ. ôÅÐÅÒØ ÐÏÑÓÎÉÍ.
  17
  18 üÔÏ ÁÌÇÅÂÒÙ ÔÏÊ ÖÅ ÓÉÇÎÁÔÕÒÙ, ÞÔÏ É ÁÌÇÅÂÒÙ ëÌÉÎÉ, Ó ÏÄÎÏÊ ÄÏÂÁ×ÌÅÎÎÏÊ
  19 ×ÎÅÛÎÅÊ ÏÐÅÒÁÃÉÅÊ. (ðÏÜÔÏÍÕ ÏÎÉ ÏÓÔÁÀÔÓÑ ÐÒÉÇÏÄÎÙ ÄÌÑ ÉÎÔÅÒÐÒÅÔÁÃÉÉ
  20 ××ÅÄ£ÎÎÙÈ ÒÁÎÅÅ ÐÒÏÇÒÁÍÍ\T ÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ É Á×ÔÏÍÁÔÏ×.)
  21
  22 åÓÌÉ ÇÏ×ÏÒÉÔØ ÎÅÆÏÒÍÁÌØÎÏ, ÔÏ
  23 ÏÂÏÂÝÅÎÉÅ ÐÏ ÏÔÎÏÛÅÎÉÀ Ë ÁÌÇÅÂÒÁÍ ëÌÉÎÉ ÓÏÓÔÏÉÔ × ÔÏÍ, ÞÔÏ ÚÁËÏÎ
  24 ÉÄÅÍÐÏÔÅÎÔÎÏÓÔÉ ÓÌÏÖÅÎÉÑ:
  25 \begin{equation}
  26   \tag{\ref{eq:ISr-idempotence}}
  27   x + x = x
  28 \end{equation}
  29 × ÎÉÈ ÚÁÍÅÎ£Î ÎÁ <<×ÎÅÛÎÉÊ ÚÁËÏÎ ÕÞ£ÔÁ \emph{ËÒÁÔÎÏÓÔÅÊ} ÜÌÅÍÅÎÔÁ>>.
  30 äÌÑ ÜÔÏÇÏ ÉÓÐÏÌØÚÕÅÔÓÑ ÎÅËÏÔÏÒÏÅ ÐÏÌÕËÏÌØÃÏ $\sr S$
  31 ËÒÁÔÎÏÓÔÅÊ. ÷ÏÏÂÝÅ, ÅÓÌÉ ×
  32 Î£Í ÓÏÂÌÀÄÁÅÔÓÑ ÚÁËÏÎ ÉÄÅÍÐÏÔÅÎÔÎÏÓÔÉ, ÔÏ É $\sr S$\dÁÌÇÅÂÒÁ ÂÕÄÅÔ
  33 ÉÄÅÍÐÏÔÅÎÔÎÏÊ. \tDJust{áÌÇÅÂÒÙ ëÌÉÎÉ}\T ÜÔÏ \tDJust{$\bbB$\dÁÌÇÅÂÒÙ
  34   ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ},
  35 ÇÄÅ $\bbB$\T ÐÒÉ×ÙÞÎÏÅ ÉÄÅÍÐÏÔÅÎÔÎÏÅ \tD{<<ÂÕÌÅ×Ï>> ÐÏÌÕËÏÌØÃÏ}{def:Bool-Sr}
  36 $(\{ \False, \True \}; \vee, \wedge, \False, \True)$.
  37 äÏÐÏÌÎÉÔÅÌØÎÁÑ ×ÎÅÛÎÑÑ ÏÐÅÒÁÃÉÑ ÐÏ
  38 ÓÒÁ×ÎÅÎÉÀ Ó ÓÉÇÎÁÔÕÒÏÊ \KA\T ÜÔÏ \tND{ÕÍÎÏÖÅÎÉÅ ÎÁ
  39   ÞÉÓÌÏ}{def:S-KA-multiply}
  40 (ËÒÁÔÎÏÓÔØ),
  41 ÜÌÅÍÅÎÔ $\sr S$.
  42
  43 íÙ ÎÅ ÂÕÄÅÍ ÆÏÒÍÁÌØÎÏ ÏÐÉÓÙ×ÁÔØ ËÌÁÓÓ $\sr S$\dÁÌÇÅÂÒ, ËÁË ÍÙ ÜÔÏ
  44 ÓÄÅÌÁÌÉ Ó \KA, É ÎÅ ÂÕÄÅÍ ÉÓÓÌÅÄÏ×ÁÔØ ÏÂÝÉÅ Ó×ÏÊÓÔ×Á ÍÏÄÅÌÅÊ\d$\sr
  45 S$\dÁÌÇÅÂÒ. ÷ ÒÁÚÄÅÌÁÈ, ÐÏÓ×ÑÝ£ÎÎÙÈ ÁÌÇÅÂÒÁÍ Ó ËÒÁÔÎÏÓÔÑÍÉ,
  46 ÍÙ ÏÐÉÛÅÍ ÎÅÓËÏÌØËÏ ÍÏÄÅÌÅÊ, ËÏÔÏÒÙÅ ÂÕÄÕÔ ×ÁÖÎÙ Ó×ÏÅÊ
  47 Ó×ÑÚØÀ Ó ÒÁÚÒÅÛÉÍÏÓÔØÀ ðü ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÐÒÏÇÒÁÍÍ × ÁÌÇÅÂÒÁÈ
  48 ëÌÉÎÉ.
  49 ïÎÉ ÂÕÄÕÔ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ ÎÅËÏÔÏÒÙÍ ÓÔÁÎÄÁÒÔÎÙÍ ÍÏÄÅÌÑÍ\dÁÌÇÅÂÒÁÍ ëÌÉÎÉ, ËÏÔÏÒÙÅ
  50 ÍÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ × ÄÒÕÇÉÈ ÒÁÚÄÅÌÁÈ.
  51
  52 òÅÚÕÌØÔÁÔÙ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ÂÕÄÕÔ ×ÅÒÎÙ ÐÒÉ ÎÁÌÏÖÅÎÉÉ Ö£ÓÔËÉÈ ÕÓÌÏ×ÉÊ ÎÁ
  53 $\sr S$ (Á ÎÅ ÄÌÑ ×ÓÅÇÏ ÛÉÒÏËÏÇÏ ËÌÁÓÓÁ ÁÌÇÅÂÒ Ó ËÒÁÔÎÏÓÔÑÍÉ).
  54
  55 á×ÔÏÍÁÔÙ Ó ËÒÁÔÎÏÓÔÑÍÉ, ÓÅÍÁÎÔÉËÁ ËÏÔÏÒÙÈ ÏÐÉÓÙ×ÁÅÔÓÑ × ÁÌÇÅÂÒÁÈ Ó
  56 ËÒÁÔÎÏÓÔÑÍÉ (ÉÌÉ ÆÏÒÍÁÌØÎÙÈ ÒÑÄÁÈ), ÐÒÅÄÓÔÁ×ÌÅÎÙ, ÎÁÐÒÉÍÅÒ, ×
  57 \cite{E}, Ï ÆÏÒÍÁÌØÎÙÈ ÒÑÄÁÈ × ÐÒÉÍÅÎÅÎÉÉ Ë ôÅÏÒÉÉ ÆÏÒÍÁÌØÎÙÈ ÑÚÙËÏ×\T
  58 \cite{BerstelR-rational} (ËÏÒÏÔËÏÅ ×ÅÄÅÎÉÅ ×
  59 \cite{perrin:automata-formallangs}).
  60
  61 \subsubsection{ó×ÏÊÓÔ×Á ÁÌÇÅÂÒÙ Ó ËÒÁÔÎÏÓÔÑÍÉ ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ}
  62
  63 ðÕÓÔØ $\ka K = (K; +, \cdot, ^*, 0, 1, \cdot)$\T $\sr S$\dÁÌÇÅÂÒÁ
  64 ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ.
  65
  66 $\ka K$\T \todo{ÍÏÄÕÌØ ÎÁÄ ÐÏÌÕËÏÌØÃÏÍ $\sr S$ (ËÁË ÂÙ <<ÌÉÎÅÊÎÏÅ
  67   ÐÒÏÓÔÒÁÎÓÔ×Ï ÎÁÄ ÐÏÌÕËÏÌØÃÏÍ $\sr S$>>; ÏÐÒÅÄÅÌÅÎÉÑ ÓÍ., ÎÁÐÒÉÍÅÒ,
  68   ×~\cite{modules}).}
  69
  70 äÁÌØÛÅ × ÔÅËÓÔÅ, ÅÓÌÉ ÎÅ ÓËÁÚÁÎÏ  ÄÒÕÇÏÅ, ÂÕÄÅÍ ÓÞÉÔÁÔØ, ÞÔÏ $\sr s$\T
  71 ÎÅËÏÔÏÒÏÅ ÐÏÌÕËÏÌØÃÏ $\sr S = (S; +_{\sr S}, \cdot_{\sr S}, 0_{\sr S},
  72 1_{\sr S})$. (ë ÓÏÖÁÌÅÎÉÀ, ÏÂÏÚÎÁÞÅÎÉÅ ÐÒÏÓÔÙÈ ËÒÁÔÎÏÓÔÅÊ ÕÓÌÏÖÎÅÎÏ
  73 ÉÎÄÅËÓÏÍ.)
  74
  75 äÌÑ $k,l \in \sr S$, $x, y \in \ka K$:
  76 \begin{align}
  77   \label{eq:S-KA-mult}
  78   (k \cdot x) \cdot (l \cdot y) &= (k \cdot_{\sr S} l) \cdot (x \cdot
  79   y)
  80   &&\text{(???)}
  81 \end{align}
  82 \todo{\cite{modules}}
  83
  84 üÌÅÍÅÎÔÙ $\ka K$ ×ÉÄÁ $k \cdot 1$, ÇÄÅ $k \in \sr S$,
  85 ÂÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ ÐÒÏÓÔÏ $k$.
  86
  87 \subsection{óÉÎÔÁËÓÉÓ: ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ É Á×ÔÏÍÁÔÙ Ó ËÒÁÔÎÏÓÔÑÍÉ}
  88 \label{sec:S-Sigma-syntax}
  89
  90 ÷ ÓÉÎÔÁËÓÉÓ ÄÏÂÁ×ÉÍ ÕÍÎÏÖÅÎÉÅ ÎÁ ËÒÁÔÎÏÓÔÉ. äÌÑ ÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ
  91 (ÓÍ.~ïÐÒ.~\ref{def:regexp}, ôÁÂÌ.~\ref{tab:regexp-bnf}):
  92
  93 \begin{definition}\label{def:S-regexp}
  94 ðÕÓÔØ $\Sigma$\T ËÏÎÅÞÎÙÊ ÎÁÂÏÒ ÓÉÍ×ÏÌÏ×\DËÏÎÓÔÁÎÔ (<<ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ×>>).
  95 ôÅÒÍÙ ÓÉÇÎÁÔÕÒÙ $\sr S$\dÁÌÇÅÂÒÙ ëÌÉÎÉ
  96 (\te $+, \cdot, ^*, 0, 1, \cdot$),
  97 ÄÏÐÏÌÎÅÎÎÏÊ ËÏÎÓÔÁÎÔÁÍÉ ÉÚ~$\Sigma$, ÎÁÚÙ×ÁÀÔÓÑ \tING{$\sr S$-ÒÅÇÕÌÑÒÎÙÍÉ
  98   ×ÙÒÁÖÅÎÉÑÍÉ ÎÁÄ $\Sigma$}. (÷ ÔÅÒÍÁÈ ÒÁÚÒÅÛÅÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÜÌÅÍÅÎÔÙ
  99 $\sr S$ ÔÁÍ, ÇÄÅ ÜÔÏ ÄÏÐÕÓÔÉÍÏ ÚÎÁËÏÍ ÏÐÅÒÁÃÉÉ.)
 100 íÎÏÖÅÓÔ×Ï $\sr S$\dÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ
 101 ÏÂÏÚÎÁÞÁÅÔÓÑ $\preS\RExp_\Sigma$.
 102 \end{definition}
 103 \begin{table}[hbtp]
 104   \centering
 105 $$
 106 \begin{array}{lll}
 107 \text{ÔÅÒÍÙ\dËÒÁÔÎÏÓÔÉ}
 108 & k, l  \dotsc
 109 & k ::= \langle\text{ÏÂÏÚÎÁÞÅÎÉÅ ÜÌÅÍÅÎÔÏ×~$\sr S$}\rangle\\
 110 \text{ÔÅÒÍÙ}
 111 & s, t  \dotsc
 112 & s ::= \langle\text{ÂÁÚÏ×ÙÅ ÏÐÅÒÁÔÏÒÙ}\rangle
 113 \ |\ 0\ |\ 1\ |\ s+t\ |\ st\ |\ s^*\ |\ ks
 114 \end{array}
 115 $$
 116   \caption{ôÅÒÍÙ × ÏÐÒÅÄÅÌÅÎÉÉ $\sr S$\dÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ ÎÁÄ~$\Sigma$}
 117   \label{tab:S-regexp-bnf}
 118 \end{table}
 119 \begin{remark}
 120   $\RExp_\Sigma \subset \preS\RExp_\Sigma$.
 121 \end{remark}
 122
 123 ôÁËÖÅ, ËÁË É ÒÁÎØÛÅ, ÉÎÔÅÒÐÒÅÔÁÃÉÀ ÂÁÚÏ×ÙÈ ÓÉÍ×ÏÌÏ×~$I\colon
 124 \Sigma \to \ka K$, ÇÄÅ $\ka K$\T $\sr S$\dÁÌÇÅÂÒÁ ëÌÉÎÉ,
 125 ÍÙ ÏÄÎÏÚÎÁÞÎÏ ÐÒÏÄÏÌÖÁÅÍ ÄÏ ÇÏÍÏÍÏÒÆÉÚÍÁ ÎÁ ×Ó£
 126 $\preS\RExp_{\Sigma}$\T
 127 ÉÎÔÅÒÐÒÅÔÁÃÉÉ $\sr S$\dÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ.
 128
 129 ÷ ÏÐÒÅÄÅÌÅÎÉÅ Á×ÔÏÍÁÔÁ (ÍÁÔÒÉÞÎÏÅ; ÓÍ.~ïÐÒ.~\ref{def:???}) ÍÙ ÔÁËÖÅ
 130 ÄÏÂÁ×ÌÑÅÍ ËÒÁÔÎÏÓÔÉ (× ÞÁÓÔÎÏÓÔÉ, × ÐÒÏÓÔÙÈ ÓÕÍÍÁÈ ÍÏÇÕÔ ÐÏÑ×ÌÑÔØÓÑ
 131 ËÒÁÔÎÏÓÔÉ). ÷ ÉÔÏÇÅ, ÐÏÌÕÞÁÅÍ \tING{ÍÎÏÖÅÓÔ×Ï $\sr S$\dÁ×ÔÏÍÁÔÎÙÈ ×ÙÒÁÖÅÎÉÊ
 132   ÎÁÄ~$\Sigma$}\T $\preS\AExp_{\Sigma}$.
 133
 134
 135 \subsection{îÅËÏÔÏÒÙÅ ÍÏÄÅÌÉ É ÉÎÔÅÒÐÒÅÔÁÃÉÉ}
 136
 137 \subsubsection{$\sr S$\dÐÏÄÍÎÏÖÅÓÔ×Á ÎÅËÏÔÏÒÏÇÏ ÍÎÏÖÅÓÔ×Á}
 138 þÁÓÔÏ × ËÁÞÅÓÔ×Å ÜÌÅÍÅÎÔÁÒÎÏÊ ÏÓÎÏ×Ù ÄÌÑ ÎÁÛÉÈ ËÏÎÓÔÒÕËÃÉÊ × ÜÔÏÍ
 139 òÁÚÄÅÌÅ ÍÙ ÂÕÄÅÍ ÉÓÐÏÌØÚÏ×ÁÔØ \tNDNo{$\sr S$-ÐÏÄÍÎÏÖÅÓÔ×Á} (ÁÎÁÌÏÇ ×
 140 ÐÒÏÓÔÏÍ ÓÌÕÞÁÅ\T ÐÒÏÓÔÙÅ ÍÎÏÖÅÓÔ×Á, ÜÌÅÍÅÎÔÁÒÎÁÑ ÏÓÎÏ×Á ÐÏÓÔÒÏÅÎÉÑ
 141 ÂÏÌÅÅ ÓÌÏÖÎÙÈ ÏÂßÅËÔÏ×).
 142
 143 \begin{definition}
 144   ïÔÏÂÒÁÖÅÎÉÅ $C\colon U \to \sr S$
 145   ÎÁÚÙ×ÁÅÔÓÑ \tING{$\sr S$-ÐÏÄÍÎÏÖÅÓÔ×ÏÍ} ÍÎÏÖÅÓÔ×Á~$U$,
 146   ÉÌÉ \tING{ÐÏÄÍÎÏÖÅÓÔ×ÏÍ Ó ËÒÁÔÎÏÓÔÑÍÉ}.
 147
 148   \tING{ëÒÁÔÎÏÓÔØ ÜÌÅÍÅÎÔÁ}~$u \in U$ × $C$
 149   ÐÒÉÎÑÔÏ ÏÂÏÚÎÁÞÁÔØ $(C, u)$.\footnote{ðÒÉ×ÅÄ£ÎÎÏÅ ÏÂÏÚÎÁÞÅÎÉÅ
 150   ÏÔËÌÏÎÑÅÔÓÑ ÏÔ ÏÂÏÚÎÁÞÅÎÉÑ, ÉÓÐÏÌØÚÕÅÍÏÇÏ × \cite{E},
 151   \cite{H-incl}, \cite{HK}: $uC$. á ×ÏÏÂÝÅ, ×ÎÅ ÜÔÏÊ ÍÅÔÁÔÅÏÒÉÉ ÄÌÑ ÚÎÁÞÅÎÉÑ
 152   ÆÕÎËÃÉÉ ÐÒÉÎÑÔÏ ÐÉÓÁÔØ $C(u)$, \te ÐÒÉ×ÅÄ£ÎÎÏÅ ÏÂÏÚÎÁÞÅÎÉÅ: $(C,
 153   u) = C(u)$.}
 154 \end{definition}
 155 \begin{remark}
 156   ïÂÙÞÎÙÅ ÐÏÄÍÎÏÖÅÓÔ×Á ÍÎÏÖÅÓÔ×Á~$U$ ÍÏÖÎÏ ÐÏÎÉÍÁÔØ ËÁË $\sr
 157   S$\dÐÏÄÍÎÏÖÅÓÔ×Á, × ËÏÔÏÒÙÈ ÜÌÅÍÅÎÔÙ ÉÍÅÀÔ ËÒÁÔÎÏÓÔØ $1_{\sr S}$:
 158   \begin{align*}
 159     s \in C
 160     \text{ (× ÏÂÙÞÎÏÍ ÓÍÙÓÌÅ) } &\equivdef
 161     (C, s) \eqdef 1_{\sr S},\\
 162     s \notin C
 163     \text{ (× ÏÂÙÞÎÏÍ ÓÍÙÓÌÅ) } &\equivdef
 164     (C, s) \eqdef 0_{\sr S},\\
 165   \end{align*}
 166
 167
 168   ÷ ÓÏÇÌÁÓÉÉ Ó ÜÔÉÍ ÎÁÈÏÄÉÔÓÑ É ÓÏÈÒÁÎ£ÎÎÏÅ ÏÂÏÚÎÁÞÅÎÉÅ
 169   \tING{ÐÕÓÔÏÇÏ $\sr S$\dÐÏÄÍÎÏÖÅÓÔ×Á}\T $\emptyset$:
 170   $(\emptyset, u) = 0_{\sr S}$ ÄÌÑ ÌÀÂÏÇÏ $u \in U$.
 171 \end{remark}
 172
 173 \paragraph{óÔÒÕËÔÕÒÁ ÌÉÎÅÊÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á ÎÁ ÍÎÏÖÅÓÔ×Å $\sr S$-ÐÏÄÍÎÏÖÅÓÔ×.}
 174 ïÐÒÅÄÅÌÉÍ Ä×Å ÐÒÏÓÔÙÅ ÏÐÅÒÁÃÉÉ ÎÁÄ $\sr S$-ÐÏÄÍÎÏÖÅÓÔ×ÁÍÉ ÍÎÏÖÅÓÔ×Á $U$:
 175 \begin{description}
 176 \item[\tING{óÕÍÍÁ}:] $C_1 + C_2$: $(C_1 + C_2, u) \eqdef (C_1,u) + (C_2,u)$;
 177 \item[\tING{ÕÍÎÏÖÅÎÉÅ <<ÎÁ ÞÉÓÌÏ>>}:] $k C$, ÇÄÅ $k \in \sr S$:
 178 $(kC, u) \eqdef k (C, u)$.
 179 \end{description}
 180 ìÀÂÏÅ $\sr S$-ÐÏÄÍÎÏÖÅÓÔ×Ï ÍÏÖÎÏ ÐÒÅÄÓÔÁ×ÉÔØ × ×ÉÄÅ \tING{ÆÏÒÍÁÌØÎÏÇÏ
 181   ÒÑÄÁ}
 182 (ÆÏÒÍÁÌØÎÏ ÉÓÐÏÌØÚÕÑ ÜÔÉ Ä×Å ÏÐÅÒÁÃÉÉ):
 183 $$
 184 C \overset{\text{ÆÏÒÍ.}}{=} \sum_{u \in U} (C,u) u.
 185 $$
 186 %% é ÐÒÁ×ÄÁ, ÜÔÏ ÍÏÖÎÏ ÐÏÎÉÍÁÔØ ÔÁË:
 187 %% $$
 188 %% (C, u') = \left( \left(\sum_{u \in U} (L,u)u\right), u' \right)
 189 %% = \sum_{u \in U} (L, u) (u, u')
 190 %% = \sum_{u \neq u'} (L, u) 0 + (L, u') 1
 191 %% = 0 + (L, u') = (L, u')
 192 %% .
 193 %% $$
 194 %% (<<ÆÏÒÍÁÌØÎÏ>>, ÐÏÔÏÍÕ ÞÔÏ ÔÕÔ ÉÓÐÏÌØÚÕÀÔÓÑ ÓÕÍÍÁ ÂÅÓËÏÎÅÞÎÏÇÏ ÞÉÓÌÁ
 195 %% $K$-ÐÏÄÍÎÏÖÅÓÔ× É ÓÕÍÍÁ ÂÅÓËÏÎÅÞÎÏÇÏ ÞÉÓÌÁ ÜÌÅÍÅÎÔÏ× ÐÏÌÕËÏÌØÃÁ $K$,
 196 %% ËÏÔÏÒÙÅ ÎÅÏÐÒÅÄÅÌÅÎÙ.) íÏÖÎÏ ÂÙÌÏ ÂÙ ÐÒÏÓÔÏ ÏÐÒÅÄÅÌÉÔØ
 197 %% \tD{$K$-ÐÏÄÍÎÏÖÅÓÔ×Á} ËÁË ÔÁËÉÅ ÆÏÒÍÁÌØÎÙÅ ÒÑÄÙ: $L = \sum_{u \in U}
 198 %% r_u u$.
 199
 200 \begin{example}[ÁÎÁÌÏÇÉÑ]  ðÕÓÔØ $V$ ËÏÎÅÞÎÏÍÅÒÎÏÅ
 201 ×ÅËÔÏÒÎÏÅ\footnote{<<×ÅËÔÏÒÎÏÅ>> = <<ÌÉÎÅÊÎÏÅ>>.} ÐÒÏÓÔÒÁÎÓÔ×Ï
 202 ÎÁÄ $K$, $\dim V = n$, ÓÏ ÓËÁÌÑÒÎÙÍ ÐÒÏÉÚ×ÅÄÅÎÉÅÍ $(\place,
 203 \place)\colon V \times V \to K$. ðÕÓÔØ $\vec{f_1}, \dotsc, \vec{f_n}$~---
 204 ÏÒÔÏÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÂÁÚÉÓ~$V$. ôÏÇÄÁ ÌÀÂÏÊ $\vec{x} \in V$ ÐÒÅÄÓÔÁ×ÉÍ × ×ÉÄÅ:
 205 $$
 206 \vec{x} = \sum_{i=1}^{n} (\vec{x}, \vec{f_i}) \vec{f_i}.
 207 $$
 208 íÙ ÍÏÇÌÉ ÂÙ ÓÒÁÚÕ ÏÐÒÅÄÅÌÉÔØ ×ÅËÔÏÒÎÏÅ ÐÒÏÓÔÒÁÎÓÔ×Ï ËÁË ÍÎÏÖÅÓÔ×Ï
 209 ÜÌÅÍÅÎÔÏ×, ÆÏÒÍÁÌØÎÏ ÚÁÄÁÎÎÙÈ ËÁË $\vec{x} = \langle x_1, \dotsc, x_n
 210 \rangle$, ÇÄÅ $x_1, \dotsc, x_n \in K$ ÎÁÄÏ ÐÏÎÉÍÁÔØ ËÁË ËÏÏÒÄÉÎÁÔÙ
 211 ×ÅËÔÏÒÁ × ÂÁÚÉÓÅ~$\vec{f_1}, \dotsc, \vec{f_n}$, ÉÌÉ ËÁË ÆÏÒÍÁÌØÎÙÅ
 212 ÓÕÍÍÙ $K\sums{\vec{f_1}, \dotsc, \vec{f_n}}$:
 213 $$
 214 \vec{x} = \sum_{i=1}^{n} x_i \vec{f_i}.
 215 $$
 216 \end{example}
 217
 218 \begin{remark}\label{rem:infinite-sum}
 219 óÕÍÍÁ ÂÅÓËÏÎÅÞÎÏÇÏ ÞÉÓÌÁ $\sr S$\dÐÏÄÍÎÏÖÅÓÔ× ÍÎÏÖÅÓÔ×Á~$U$
 220 ÉÍÅÅÔ ÓÍÙÓÌ ÔÏÇÄÁ, ËÏÇÄÁ
 221 ËÁÖÄÙÊ ÜÌÅÍÅÎÔ $u \in U$ ×ÈÏÄÉÔ ÔÏÌØËÏ × ËÏÎÅÞÎÏÅ ÞÉÓÌÏ ÜÔÉÈ
 222 ÐÏÄÍÎÏÖÅÓÔ× Ó ÎÅÎÕÌÅ×ÏÊ ËÒÁÔÎÏÓÔØÀ.
 223 \end{remark}
 224
 225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 226 \subsubsection{æÏÒÍÁÌØÎÏÑÚÙËÏ×ÙÅ $\sr S$\dÁÌÇÅÂÒÙ}
 227 \label{sec:S-KA-langmodels}
 228
 229 ðÕÓÔØ $\Sigma$ ËÏÎÅÞÎÙÊ ÁÌÆÁ×ÉÔ.
 230 $(\Strs(\Sigma); \cdot, \eStr)$\T ÍÏÎÏÉÄ ËÏÎÅÞÎÙÈ ÓÔÒÏË.
 231
 232 âÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ
 233 ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ
 234 $\sr S$\dÐÏÄÍÎÏÖÅÓÔ×~$\Strs(\Sigma)$\T $\sr S\series{\Strs(\Sigma)}$.
 235
 236 \begin{definition}
 237   \tING{ðÒÏÉÚ×ÅÄÅÎÉÅ Ä×ÕÈ $\sr S$\dÐÏÄÍÎÏÖÅÓÔ× ÍÏÎÏÉÄÁ}
 238   $C, D \in \sr S\series{\Strs(\Sigma)}$:
 239   \begin{equation}
 240     \label{eq:S-set-concat}
 241     (C \cdot D,z) \eqdef \sum_{x y = z} (C,x)(D,y)
 242   \end{equation}
 243   ÄÌÑ ËÁÖÄÏÇÏ $z \in \Strs(\Sigma)$.
 244
 245   ÷ÏÏÂÝÅ ÔÁËÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÉÍÅÅÔ ÓÍÙÓÌ ÄÌÑ ×ÓÑËÏÇÏ
 246   \tD{ËÏÎÅÞÎÏÐÒÅÄÓÔÁ×ÉÍÏÇÏ ÍÏÎÏÉÄÁ}{def:finitely-pres-Mo} \cite{HK}
 247   (ÉÎÁÞÅ ÓÕÍÍÁ ÂÅÓËÏÎÅÞÎÁ).
 248 \end{definition}
 249
 250 \begin{proposition}
 251   óÔÒÕËÔÕÒÁ~$(\sr S\series{\Strs(\Sigma)};
 252   +, \cdot, \emptyset, \{ \eStr \} )$\T
 253   ÐÏÌÕËÏÌØÃÏ.
 254 \end{proposition}
 255
 256 \begin{definition}
 257   ðÕÓÔØ $C \in \sr S\series{\Strs(\Sigma)}$ É $(C, \eStr) = 0_{\sr
 258   S}$. ôÏÇÄÁ ÏÐÒÅÄÅÌÉÍ
 259   \begin{equation}
 260     \label{eq:S-set-star}
 261     C^*  \eqdef \sum_{n \in \bbN \cup \{ 0 \}} C^n,
 262   \end{equation}
 263   ÇÄÅ
 264   \begin{align*}
 265     C^0 &\eqdef \{ \eStr\}
 266     &
 267     C^{n+1} &\eqdef C \cdot C^n.
 268   \end{align*}
 269   âÅÓËÏÎÅÞÎÁÑ ÓÕÍÍÁ × ÏÐÒÅÄÅÌÅÎÉÉ ÉÍÅÅÔ ÓÍÙÓÌ, ÓÏÇÌÁÓÎÏ
 270   úÁÍÅÞÁÎÉÀ~\ref{rem:infinite-sum}, ÐÏÔÏÍÕ ÞÔÏ ÕÓÌÏ×ÉÅ $(C, \eStr) = 0_{\sr
 271   S}$ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ËÁÖÄÏÅ ÓÌÏ×Ï ÐÏÑ×ÌÑÅÔÓÑ × $C^n$ ÔÏÌØËÏ ËÏÎÅÞÎÏÅ
 272   ÞÉÓÌÏ ÒÁÚ.
 273
 274   \todo{[ÄÌÑ ËÁËÉÈ ÍÏÎÏÉÄÏ× ÉÍÅÅÔ ÓÍÙÓÌ? \cite{HK}]}
 275 \end{definition}
 276
 277 ôÏÌØËÏ ÞÔÏ ÏÐÒÅÄÅÌ£ÎÎÁÑ ÓÔÒÕËÔÕÒÁ~$(\sr S\series{\Strs(\Sigma)};
 278 +, \cdot, {}^*, \emptyset, \{ \eStr \}, \cdot )$\T
 279 $\sr S$\dÁÌÇÅÂÒÁ ÎÁÐÏÄÏÂÉÅ ëÌÉÎÉ.
 280
 281 \paragraph{ëÁÎÏÎÉÞÅÓËÁÑ ÉÎÔÅÒÐÒÅÔÁÃÉÑ}
 282
 283 \begin{definition}\label{def:interp-str}
 284   \tING{ëÁÎÏÎÉÞÅÓËÁÑ ÉÎÔÅÒÐÒÅÔÁÃÉÑ $\preS R_{\Sigma}$
 285     $\sr S$\dÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ ÎÁÄ~$\Sigma$} ×~$\sr S\series{\Strs(\Sigma)}$
 286   ÏÐÒÅÄÅÌÑÅÔÓÑ ÔÁËÉÍÉ ÚÎÁÞÅÎÉÑÍÉ ÎÁ ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÁÈ:
 287   $$
 288   \preS R_{\Sigma}(a) \eqdef \{ a \} \text{ ÄÌÑ } a \in \Sigma.
 289   $$
 290 \end{definition}
 291
 292 \begin{definition}\label{def:reg-by-basic}
 293   $\sr S$\dÐÏÄÍÎÏÖÅÓÔ×Ï ÓÔÒÏË~$C \in \sr S\series{\Strs(\Sigma)}$ ÎÁÚÙ×ÁÅÔÓÑ
 294   \tING{ÒÅÇÕÌÑÒÎÙÍ}, ÅÓÌÉ $C = \preS R_{\Sigma}(s)$ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ
 295   $\sr S$\dÒÅÇÕÌÑÒÎÏÇÏ ×ÙÒÁÖÅÎÉÑ $s \in \preS\RExp_{\Sigma}$.
 296
 297   \tING{óÅÍÅÊÓÔ×Ï ÒÅÇÕÌÑÒÎÙÈ $\sr S$\dÐÏÄÍÎÏÖÅÓÔ× ÓÔÒÏË ÎÁÄ~$\Sigma$}
 298   ÏÂÏÚÎÁÞÁÅÔÓÑ
 299   $\sr S^\reg\series{\Strs(\Sigma)} \eqdef \preS \Reg_{\Sigma}$.
 300   (<<$\preS\Reg_{\Sigma} \models \phi$>> ÚÎÁÞÉÔ
 301   <<$\preS\Reg_{\Sigma}, \preS R_\Sigma \models \phi$>>.
 302   \todo{[ÈÏÔÉÍ ÌÉ $\preS R_{\Sigma}$ ÐÏ ÕÍÏÌÞÁÎÉÀ?]})
 303 \end{definition}
 304 %
 305 \todo{[
 306 (íÏÖÎÏ ×ÓÔÒÅÔÉÔØ É ÄÒÕÇÏÅ ÐÏÈÏÖÅÅ ÜË×É×ÁÌÅÎÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÒÅÇÕÌÑÒÎÙÈ ÍÎÏÖÅÓÔ×
 307 ÓÔÒÏË, ÅÓÔÅÓÔ×ÅÎÎÏ ×ÏÚÎÉËÁÀÝÅÅ
 308 ÐÒÉ ÏÂÏÂÝÅÎÉÉ ËÏÎÓÔÒÕËÃÉÉ $\Reg_\Sigma$ ÎÁ ÐÒÏÉÚ×ÏÌØÎÙÅ ÍÏÎÏÉÄÙ\T
 309 ÓÍ.~úÁÍÅÞÁÎÉÅ~\label{???}.)]}
 310
 311
 312 \subsection{ó×ÑÚÉ $\sr S$\dÁÌÇÅÂÒ ÄÒÕÇ Ó ÄÒÕÇÏÍ}
 313 \label{sec:S-KA-interrelation}
 314
 315 íÙ ÎÅ ÉÓÓÌÅÄÏ×ÁÌÉ, ÎÏ ÐÏÄÏÚÒÅ×ÁÅÍ, ÞÔÏ × ÛÉÒÏËÏÍ ÎÁÂÏÒÅ ÓÌÕÞÁÅ× ÐÏÈÏÖÅ
 316 ÎÁ ÓÌÕÞÁÊ ÂÅÚ ËÒÁÔÎÏÓÔÅÊ.
 317
 318 \begin{question}
 319   \todo{[ÐÒÏ ÒÁ×-Ï EOf]}
 320 \end{question}
 321
 322 \subsection{ó×ÑÚÉ ðü × $\sr S$\dÁÌÇÅÂÒÁÈ É ÄÅÔ. Á×ÔÏÍÁÔÏ×}
 323 \label{sec:S-KA-det}
 324
 325
 326 \subsection{ôÅÏÒÅÍÁ ëÌÉÎÉ\EndrûÀÔÃÅÎÂÅÒÖÅ}
 327 \label{sec:multi-Kleene-th}
 328
 329 õÐÏÍÑÎÕÔÁ ×~\cite{DroZha01}\nocite{DroZha03}, \sm ÔÁËÖÅ
 330 \cite{Droste:1994:KTR,DroGas99}.
 331
 332 ôÅÏÒÅÍÁ ëÌÉÎÉ ÎÁÍ ÏÐÑÔØ ÐÏÚ×ÏÌÑÅÔ ÎÅ ÄÅÌÁÔØ ÒÁÚÎÉÃÙ × ÎÁÛÉÈ
 333 õÔ×ÅÒÖÄÅÎÉÑÈ ÍÅÖÄÕ ÌÉÎÅÊÎÏÊ
 334 ÚÁÐÉÓØÀ ÐÒÏÇÒÁÍÍ É ÇÒÁÆÏ×ÙÍ ÐÒÅÄÓÔÁ×ÌÅÎÉÅÍ × ÜÔÏÍ ÓÌÕÞÁÅ.
 335
 336 %%%%%%%%%
 337
 338 \subsection{ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ × $\sr S$\dÁÌÇÅÂÒÁÈ}
 339 \label{sec:S-Equa}
 340
 341 \todo{[ÓÉÎÔÁËÓÉÞÅÓËÏÅ Ó×ÅÄÅÎÉÅ -- ÞÔÏ Ñ ÉÍÅÌ × ×ÉÄÕ ÔÕÔ?]}
 342
 343 åÓÌÉ ÐÏÌÕËÏÌØÃÏ $\ka K = (K; +, \cdot, 0, 1)$ ×ËÌÁÄÙ×ÁÅÔÓÑ
 344 × ËÏÌØÃÏ $\sr R = (R; +, \cdot, 0, 1, -)$, ÔÏ
 345 $$
 346 \ka K, I \models s = t \iffdef I(s) = I(t)
 347 \iff I(s) - I(t) = 0.
 348 $$
 349
 350 \begin{proposition}
 351   åÓÌÉ ÐÏÌÕËÏÌØÃÏ $\sr S$ ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ, ÔÏ É
 352   ÐÏÌÕËÏÌØÃÏ $\sr S\series{\mo M}$ ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ.
 353 \end{proposition}
 354
 355 ðÏÌÕÞÁÅÍ ÔÁËÏÊ ÐÒÏÓÔÏÊ ËÒÉÔÅÒÉÊ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ (ÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÊ É
 356 Á×ÔÏÍÁÔÏ× Ó ËÒÁÔÎÏÓÔÑÍÉ):
 357 \begin{proposition}[\cite{E}]
 358   åÓÌÉ $\sr S$ ËÏÌØÃÏ, ÔÏ
 359   $$
 360   \sr S\series{\mo M} \models s = t
 361   \iff
 362   \sr S\series{\mo M} \models s + (-1_{\sr S} \cdot t) = 0.
 363   $$
 364
 365   ôÁËÖÅ ÉÚ Ä×ÕÈ Á×ÔÏÍÁÔÏ× $\au A$ É $\au B$ ÓÏÓÔÁ×ÉÍ ÏÄÉÎ
 366   $\au A \Hat{+} (\Hat{-} \au B)$ (\todo{[ËÁË]}) É
 367   $$
 368   \sr S\series{\mo M} \models \au A = \au B
 369   \iff
 370   \sr S\series{\mo M} \models \au A \Hat+ (\Hat- \au B) = 0.
 371   $$
 372 \end{proposition}
 373
 374
 375 \subsection{ôÅÏÒÅÍÁ üÊÌÅÎÂÅÒÇÁ. äÏËÁÚÁÔÅÌØÓÔ×Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DFA (ÐÅÒ×ÙÊ ÓÐÏÓÏÂ)}
 376 \label{sec:E}
 377
 378
 379 \begin{theorem}[Eilenberg](\cite[Thm. ??]{E}, \cite[Thm. ??]{HK})\footnote{÷~\cite{E} ÔÁËÁÑ ÔÅÏÒÅÍÁ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÁ ÄÌÑ \emph{ÐÏÌÅÊ} ×ÍÅÓÔÏ
 380 \emph{ËÏÌÅÃ Ó ÄÅÌÅÎÉÅÍ}, × \cite{HK} ÚÁÍÅÞÅÎÏ, ÞÔÏ ÏÎÁ ÌÅÇËÏ
 381 ÏÂÏÂÝÁÅÔÓÑ É ÎÁ ËÏÌØÃÁ Ó ÄÅÌÅÎÉÅÍ.}
 382   \label{th:E-many}
 383   $M$ \todo{[ÎÏÒÍÁÌÉÚÏ×ÁÎÏ]}.
 384   åÓÌÉ ÐÏÌÕËÏÌØÃÏ $\sr S$ ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ, ÔÏ
 385   \begin{equation}
 386     \label{eq:E-itapes}
 387     \preS \ITAPES_1
 388     \models IM^*F = 0
 389     \iff
 390     \left(
 391       \preS \ITAPES_1
 392       \models IM^iF = 0
 393       \text{ ÄÌÑ ×ÓÅÈ } i \in \{ 0, \dotsc, n \}
 394     \right),
 395   \end{equation}
 396   ÇÄÅ $n$\T ÞÉÓÌÏ ÓÏÓÔÏÑÎÉÊ Á×ÔÏÍÁÔÁ $\au A$.
 397
 398   ë ÔÏÍÕ ÖÅ, ËÁË ÌÅÇËÏ ÚÁÍÅÔÉÔØ,
 399   ÐÒÁ×ÁÑ ÞÁÓÔØ~\eqref{eq:E-itapes} ÜË×É×ÁÌÅÎÔÎÁ ËÏÎÅÞÎÏÍÕ ÞÉÓÌÕ
 400   ÕÓÌÏ×ÉÊ ×ÉÄÁ
 401   $$
 402   \ka K \models IM^iF = 0,
 403   $$
 404   ÇÄÅ $\ka K$\T ÎÅËÏÔÏÒÁÑ ÍÏÄÅÌØ ÉÚ $\preS \ITAPES_1$ (ÐÏ ÏÄÎÏÍÕ
 405   ÕÓÌÏ×ÉÀ ÎÁ
 406   ËÁÖÄÕÀ ËÏÎÅÞÎÕÀ ÓÔÒÏËÕ ÄÌÉÎÙ ÎÅ ÂÏÌØÛÅ $n$).
 407 \end{theorem}
 408
 409 \todo{[ÏÒÐ $\ITAPES_k]$}
 410
 411 üÔÏ ÓÌÅÄÓÔ×ÉÅ ÈÏÒÏÛÏ ÉÚ×ÅÓÔÎÏ (\todo{[ÐÏÄ ÎÁÚ×ÁÎÉÅÍ Ô íÕÒÁ]}):
 412 \begin{corollary}\label{cor:E-detDFA}
 413   $M$ \todo{[ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ (ÂÏÌÅÅ ÏÂÝÅÅ: ÏÄÎÏÚÎÁÞÎÙ)]}.
 414   $$
 415   \Reg_\Sigma
 416   \models \au A_2 = \au A_2
 417   \iff
 418   \left(
 419     \ITAPES_1
 420     \models I_1M_1^iF_1 = I_2M_2^iF_2
 421     \text{ ÄÌÑ ×ÓÅÈ } i \in \{ 0, \dotsc, n_1 + n_2 \}
 422   \right),
 423   $$
 424   ÇÄÅ $n_i$\T ÞÉÓÌÏ ÓÏÓÔÏÑÎÉÊ Á×ÔÏÍÁÔÁ $\au A_i$.
 425
 426   éÌÉ, ÕÞÉÔÙ×ÁÑ, ÞÔÏ $\Reg_\Sigma$ Ñ×ÌÑÅÔÓÑ Ó×ÏÂÏÄÎÏÊ ÍÏÄÅÌØÀ × \KA:
 427   $$
 428   \KA
 429   \models \au A_2 = \au A_2
 430   \iff
 431   \left(
 432     \ITAPES_1
 433     \models I_1M_1^iF_1 = I_2M_2^iF_2
 434     \text{ ÄÌÑ ×ÓÅÈ } i \in \{ 0, \dotsc, n_1 + n_2 \}
 435   \right).
 436   $$
 437 \end{corollary}
 438 \begin{proof}
 439   ðÏ ËÒÉÔÅÒÉÀ õÔ×ÅÒÖÄÅÎÉÑ~\ref{prop:unambig-multi} É ÐÏÔÏÍÕ, ÞÔÏ
 440   $\bbZ_2$\T ÐÏÌÅ.
 441 \end{proof}
 442
 443 \begin{question}
 444   îÁÓËÏÌØËÏ ÍÏÖÎÏ ÏÂÏÂÝÉÔØ ÔÒÅÂÏ×ÁÎÉÅ ÎÏÒÍÁÌÉÚÏ×ÁÎÎÏÓÔÉ Á×ÔÏÍÁÔÁ?
 445
 446   ïÔ×ÅÔ ÐÒÅÄÐÏÌÁÇÁÅÔ ÂÏÌÅÅ ÏÂÝÅÅ ÉÚÌÏÖÅÎÉÅ ÄÏËÁÚÁÔÅÌØÓÔ×Á, ÞÅÍ ÔÏ,
 447   ËÏÔÏÒÏÅ ÄÏÓÔÕÐÎÏ, ÓËÁÖÅÍ, ÐÏ~\cite[pages ??]{E}\todo{[?]}\T \sm
 448   òÁÚÄÅÌ~\ref{rem:sec:E-comparison}, × ÞÁÓÔÎÏÓÔÉ,
 449   ÷ÏÐÒÏÓ~\ref{q:E-many-reduction-conditions}.
 450 \end{question}
 451
 452 \subsection{ôÅÏÒÅÍÁ üÊÌÅÎÂÅÒÇÁ. äÏËÁÚÁÔÅÌØÓÔ×Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü DFA
 453   (×ÔÏÒÏÊ ÓÐÏÓÏÂ)}
 454 \label{sec:E-hard}
 455 ÷Ï ×ÔÏÒÏÍ ÓÐÏÓÏÂÅ ÐÒÉ×ÌÅËÁÀÔÓÑ ÎÅÔÒÉ×ÉÁÌØÎÙÅ ÁÌÇÅÂÒÁÉÞÅÓËÉÅ ÆÁËÔÙ Ï
 456 Ó×ÏÂÏÄÎÙÈ ÇÒÕÐÐÁÈ.
 457
 458 %\begin{definition}
 459 %\todo{
 460 íÙ ÐÏÌØÚÕÅÍÓÑ ÐÏÎÑÔÉÅÍ ÍÏÄÕÌÑ ÎÁÄ ËÏÌØÃÏÍ~$\ka R$ \cite{modules}
 461 (ÏÂÏÂÝÅÎÉÅ ÌÉÎÅÊÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á), ÉÈ ÒÁÚÍÅÒÎÏÓÔÉ.
 462 %\end{definition}
 463
 464 \begin{theorem}[Eilenberg]
 465   \label{th:E-one}
 466   ðÕÓÔØ $\ka K$\T ÐÏÌÕËÏÌØÃÏ  Ó ÏÐÅÒÁÃÉÅÊ $^*$, ÏÂÌÁÄÁÀÝÅÅ *\dÎÅÐÒÅÒÙ×ÎÏÓÔØÀ
 467   (ÓÍ. \todo{[ÞÔÏ ÓÀÄÁ ÄÏÂÁ×ÉÔØ???]}).
 468   åÓÌÉ ÍÏÄÕÌØ $\ka K^n$ ÉÍÅÅÔ ËÏÎÅÞÎÕÀ ÒÁÚÍÅÒÎÏÓÔØ~$k$, ÔÏ
 469   \begin{equation}
 470     \label{eq:E-one}
 471     \ka K
 472     \models IM^*F = 0
 473     \iff
 474     \left(
 475       \ka K
 476       \models IM^iF = 0
 477       \text{ ÄÌÑ ×ÓÅÈ } i \in \{ 0, \dotsc, k \}
 478     \right),
 479   \end{equation}
 480   ÇÄÅ $n$\T ÞÉÓÌÏ ÓÏÓÔÏÑÎÉÊ \todo{[Á×ÔÏÍÁÔÁ $\au A$.]}
 481 \end{theorem}
 482 \begin{proof}
 483 äÏËÁÚÙ×ÁÅÔÓÑ ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÐÒÏÓÔÙÈ Ó×ÏÊÓÔ× ÍÏÄÕÌÅÊ (ÌÉÎÅÊÎÙÈ ÐÒÏÓÔÒÁÎÓÔ×)\T
 484 ÔÅÍÉ ÖÅ ÒÁÓÓÕÖÄÅÎÉÑÍÉ, ÞÔÏ É <<ËÌÁÓÓÉÞÅÓËÁÑ>> ÔÅÏÒÅÍÁ
 485 üÊÌÅÎÂÅÒÇÁ (ÓÍ.~\cite[??]{E}).
 486 \end{proof}
 487
 488 ìÅÍÍÁ ÉÚ ËÌÁÓÓÉÞÅÓËÏÊ ìÉÎÅÊÎÏÊ ÁÌÇÅÂÒÙ:
 489 \begin{lemma}\label{lem:field-vector-dim}
 490   ìÉÎÅÊÎÏÅ ÐÒÏÓÔÒÁÎÓÔ×Ï ×ÅËÔÏÒÏ× ÒÁÚÍÅÒÁ~$n$
 491   ÎÁÄ ÐÏÌÅÍ~$\ka K$ ÉÍÅÅÔ ÒÁÚÍÅÒÎÏÓÔØ~$n$.
 492 \end{lemma}
 493 óÌÅÄÕÀÝÅÅ Å£ ÏÂÏÂÝÅÎÉÅ ÂÙÌÏ ÏÔÍÅÞÅÎÏ~\cite{HK} × ËÁÞÅÓÔ×Å
 494 ×ÓÐÏÍÏÇÁÔÅÌØÎÏÇÏ ÕÔ×ÅÒÖÄÅÎÉÑ:
 495 \begin{lemma}\label{lem:divring-vector-dim}
 496   íÏÄÕÌØ ×ÅËÔÏÒÏ× ÒÁÚÍÅÒÁ~$n$
 497   ÎÁÄ ËÏÌØÃÏÍ Ó ÄÅÌÅÎÉÅÍ~$\ka K$ ÉÍÅÅÔ ÒÁÚÍÅÒÎÏÓÔØ~$n$.
 498 \end{lemma}
 499
 500 \begin{corollary}[Eilenberg](\cite[??]{HK})
 501   \label{cor:E-one-divring}
 502   åÓÌÉ ÐÏÌÕËÏÌØÃÏ $\ka K$ Ó ÏÐÅÒÁÃÉÅÊ $^*$, ÏÂÌÁÄÁÀÝÅÅ *\dÎÅÐÒÅÒÙ×ÎÏÓÔØÀ
 503   (ÓÍ. \todo{[ÞÔÏ ÔÕÔ???]}), ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ, ÔÏ
 504   \begin{equation}
 505     \label{eq:E-one-divring}
 506     \ka K
 507     \models IM^*F = 0
 508     \iff
 509     \left(
 510       \ka K
 511       \models IM^iF = 0
 512       \text{ ÄÌÑ ×ÓÅÈ } i \in \{ 0, \dotsc, n \}
 513     \right),
 514   \end{equation}
 515   ÇÄÅ $n$\T ÞÉÓÌÏ ÓÏÓÔÏÑÎÉÊ \todo{Á×ÔÏÍÁÔÁ $\au A$}.
 516 \end{corollary}
 517 \begin{proof}
 518 óÌÅÄÓÔ×ÉÅ ôÅÏÒÅÍÙ~\ref{th:E-one} Ó ÕÞ£ÔÏÍ ìÅÍÍÙ~\ref{lem:divring-vector-dim}.
 519 \end{proof}
 520
 521 ðÒÏÂÌÅÍÁ ÄÅÌÅÎÉÑ ÄÌÑ ËÏÌÅÃ, Á ÉÍÅÎÎÏ ÐÏÌÕÞÅÎÉÅ ÕÓÌÏ×ÉÊ, ÐÒÉ ËÏÔÏÒÙÈ
 522 ËÏÌØÃÏ ×ÌÏÖÉÍÏ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ (= ÔÅÌÏ), ÔÒÕÄÎÁ, \sm, ÎÁÐÒÉÍÅÒ,
 523 \cite[VII.3, ÓÔÒ.~292]{cohn-ua-rus}.
 524 îÁÍ ×ÁÖÅÎ ÓÌÅÄÕÀÝÉÊ ÎÅÐÒÏÓÔÏÊ ÄÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÆÁËÔ, ÉÓÐÏÌØÚÏ×ÁÎÎÙÊ
 525 \cite{HK}:
 526 \begin{theorem}\cite[??]{HK}\label{th:Reg-divring}
 527   åÓÌÉ ÐÏÌÕËÏÌØÃÏ $\sr S$ ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ, ÔÏ
 528   ÐÏÌÕËÏÌØÃÏ $\preS \Reg_{\Sigma} = \sr S\series{\Sigma^*}$
 529   ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ.
 530 \end{theorem}
 531 \begin{proof}
 532   óÈÅÍÕ ÄÏËÁÚÁÔÅÌØÓÔ×Á \sm × \cite{HK}. ÷ ÞÁÓÔÎÏÓÔÉ, ×ÁÖÎÙÍ ÄÌÑ
 533   ÄÏËÁÚÁÔÅÌØÓÔ×Á ÆÁËÔÏÍ Ñ×ÌÑÅÔÓÑ ×ÏÚÍÏÖÎÏÓÔØ ×ÐÏÌÎÅ ÕÐÏÒÑÄÏÞÉÔØ
 534   Ó×ÏÂÏÄÎÕÀ ÇÒÕÐÐÕ, ÏÄÎÏ ÉÚ ÄÏËÁÚÁÔÅÌØÓÔ× ÜÔÏÇÏ ÆÁËÔÁ ÐÏ×ÔÏÒÅÎÏ
 535   ×~\cite{H-order}.
 536 \end{proof}
 537 ëÏÍÂÉÎÉÒÕÑ óÌÅÄÓÔ×ÉÅ~\ref{cor:E-one-divring} É ôÅÏÒÅÍÕ~\ref{th:Reg-divring}
 538 ÍÏÖÎÏ ÓÄÅÌÁÔØ ÔÅ ÖÅ ×Ù×ÏÄÙ, ÞÔÏ É ×
 539 óÌÅÄÓÔ×ÉÉ~\ref{cor:E-detDFA}.
 540 %% \begin{corollary*}
 541 %%   \todo{[copy that one]}
 542 %% \end{corollary*}
 543
 544 \begin{remark}
 545 îÅÓÌÏÖÎÏ ÐÏÎÑÔØ, ÞÔÏ
 546 ÅÓÌÉ × ÐÏÌÕËÏÌØÃÅ $\sr S$ ÅÓÔØ ÄÅÌÉÔÅÌÉ ÎÕÌÑ, ÔÏ $\sr S$ ÎÅ ÍÏÖÅÔ ÂÙÔØ
 547 ×ÌÏÖÅÎÏ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ.
 548 \end{remark}
 549 \begin{remark}
 550 ë ÐÒÉÍÅÒÕ, ÕÓÌÏ×ÉÅ ôÅÏÒÅÍÙ~\ref{th:E-one} ÎÅ ×ÙÐÏÌÎÅÎÏ ÄÌÑ ÍÏÄÅÌÅÊ\DÜÌÅÍÅÎÔÏ×
 551 $\preS \ITAPES_1$. ÷ÏÚØÍ£Í, ÎÁÐÒÉÍÅÒ, ÂÅÓËÏÎÅÞÎÕÀ ÌÅÎÔÕ, ÎÁ ËÏÔÏÒÏÊ
 552 ÎÁÐÉÓÁÎÏ ÓÌÏ×Ï $\omega$ ×ÉÄÁ:
 553 $$
 554 \omega = abbbb\dotsm \text{ (ÄÁÌØÛÅ ÔÏÌØËÏ $b$).}
 555 $$
 556 ÷ ÐÏÌÕËÏÌØÃÅ $\preS \relReg_{\kfITape(\omega)} \in \preS \ITAPES_1$
 557 ÅÓÔØ ÄÅÌÉÔÅÌÉ ÎÕÌÑ:
 558 $$
 559 \preS\relI{b} \preS\relI{a} = \emptyset.
 560 $$
 561 \end{remark}
 562
 563 \begin{question}
 564   ðÕÓÔØ $\ka K$\T ÐÏÌÕËÏÌØÃÏ.
 565   ëÁËÏ×Ù ÎÅÏÂÈÏÄÉÍÙÅ É ÄÏÓÔÁÔÏÞÎÙÅ ÕÓÌÏ×ÉÑ ÔÏÇÏ, ÞÔÏ
 566   ÍÏÄÕÌØ~$\ka K^n$ ÉÍÅÅÔ ËÏÎÅÞÎÕÀ ÒÁÚÍÅÒÎÏÓÔØ?
 567
 568   ìÅÍÍÁ~\ref{lem:divring-vector-dim} ÐÒÅÄÌÁÇÁÅÔ ÏÄÎÏ ÄÏÓÔÁÔÏÞÎÏÅ ÕÓÌÏ×ÉÅ.
 569 \end{question}
 570
 571 \begin{question}
 572   íÏÖÎÏ ÌÉ ÏÓÌÁÂÉÔØ ÕÓÌÏ×ÉÑ ôÅÏÒÅÍÙ~\ref{th:E-one}?
 573 \end{question}
 574
 575 \subsection{ôÅÏÒÅÍÁ üÊÌÅÎÂÅÒÇÁ. óÒÁ×ÎÅÎÉÅ Ä×ÕÈ ÓÐÏÓÏÂÏ×}
 576 \label{sec:E-comparison}
 577
 578 éÔÁË, ÍÙ ×ÉÄÉÍ Ä×Á ÓÐÏÓÏÂÁ ÐÏÌÕÞÉÔØ ÒÅÚÕÌØÔÁÔ Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü
 579 ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ËÏÎÅÞÎÙÈ Á×ÔÏÍÁÔÏ×, ÐÒÉÍÅÎÉ× ÔÅÏÒÅÍÕ üÊÌÅÎÂÅÒÇÁ.
 580
 581 éÓÔÏÒÉÞÅÓËÉ ÐÅÒ×ÏÊ ÂÙÌÁ ÐÏÌÕÞÅÎÁ ôÅÏÒÅÍÁ~\ref{th:E-many}, É Å£ ÄÏËÁÚÁÔÅÌØÓÔ×Ï
 582 ÐÒÏÝÅ, ÞÅÍ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ôÅÏÒÅÍÙ~\ref{th:Reg-division}, ÎÅÏÂÈÏÄÉÍÏÊ
 583 ÄÌÑ ÐÒÉÍÅÎÅÎÉÑ ôÅÏÒÅÍÙ~\ref{th:E-one} Ë ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÍ ËÏÎÅÞÎÙÍ
 584 Á×ÔÏÍÁÔÁÍ. ÷ \cite{HK} ×ÅÒÎÏÓÔØ ôÅÏÒÅÍÙ~\ref{th:E-one} ÄÅÍÏÎÓÔÒÉÒÕÅÔÓÑ
 585 ÐÒÏÓÔÙÍ, ÎÏ ÎÅ ÏÞÅÎØ ÅÓÔÅÓÔ×ÅÎÎÙÍ ÎÁ ÎÁÛ ×ÚÇÌÑÄ Ó×ÅÄÅÎÉÅÍ (ÐÅÒÅÈÏÄ Ë
 586 ÏÄÎÏÂÕË×ÅÎÎÙÍ Á×ÔÏÍÁÔÁÍ). üÔÏ ÓÏÚÄÁ£Ô ×ÐÅÞÁÔÌÅÎÉÅ Å£
 587 ×ÔÏÒÏÓÔÅÐÅÎÎÏÓÔÉ. ÷ÏÚÍÏÖÅÎ ÄÒÕÇÏÊ ×ÚÇÌÑÄ: ÎÁÉÂÏÌÅÅ ÏÂÝÅÊ ÓÞÉÔÁÅÔÓÑ
 588 ÔÅÏÒÅÍÁ ÎÁ×ÒÏÄÅ~\ref{th:E-one} (ÐÒÉÎÃÉÐÉÁÌØÎÏ, ÞÔÏ Å£ ÕÓÌÏ×ÉÅ\T
 589 ÕÓÌÏ×ÉÅ ÎÁ Ó×ÏÊÓÔ×Ï ÍÏÄÅÌÉ É ÎÅ ËÁÓÁÅÔÓÑ ÄÅÔÁÌÅÊ ÐÏÓÔÒÏÅÎÉÑ
 590 ÍÏÄÅÌÉ). äÏËÁÚÁÔÅÌØÓÔ×Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü Ó Å£ ÐÏÍÏÝØÀ ÍÏÖÎÏ ÐÒÅÄÓÔÁ×ÉÔØ
 591 ËÁË ÓÏÅÄÉÎÅÎÉÅ ÎÅÓËÏÌØËÉÈ ÁÒÇÕÍÅÎÔÏ×:
 592 \begin{enumerate}
 593 \item ðü ÒÁÚÒÅÛÉÍÁ: ÓÌÅÄÕÅÔ ÉÚ 2;
 594 \item ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÒÁ×ÎÏÓÉÌØÎÁ
 595   ×ÙÐÏÌÎÅÎÉÀ ÎÅËÏÔÏÒÏÇÏ ÐÒÏ×ÅÒÑÅÍÏÇÏ ÕÓÌÏ×ÉÑ ÎÁ ËÏÎÅÞÎÙÊ ÎÁÂÏÒÅ
 596   ËÏÎÓÔÒÕËÃÉÊ (×ÏÚÎÉËÁÀÝÉÈ × ÄÏËÁÚÁÔÅÌØÓÔ×Å ôÅÏÒÅÍÙ~\ref{th:E-one}):
 597   ÓÌÅÄÕÅÔ ÉÚ 3;
 598 \item ÐÏÌÕËÏÌØÃÏ, ×ÚÑÔÏÅ × ËÁÞÅÓÔ×Å ÍÏÄÅÌÉ, ×ÌÏÖÉÍÏ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ.
 599 \end{enumerate}
 600 ðÒÏÄÏÌÖÅÎÉÅ ÏÐÉÓÁÎÉÅ ÎÁÛÅÇÏ ×ÚÇÌÑÄÁ:
 601 ôÅÏÒÅÍÁ~\ref{th:E-many} ÐÏÌÕÞÁÅÔÓÑ ÓÉÌØÎÙÍ ÕÐÒÏÝÅÎÉÅÍ
 602 ×ÏÚÎÉËÁÀÝÉÈ ÐÒÉ ÐÒÉÍÅÎÅÎÉÉ ÏÂÝÅÊ ÔÅÏÒÅÍÙ ËÏÎÓÔÒÕËÃÉÊ, ËÏÔÏÒÏÅ ÏÓÎÏ×ÁÎÏ
 603 ÎÁ ÓÐÅÃÉÆÉÞÅÓËÉÈ Ó×ÏÊÓÔ×ÁÈ É ×ÚÁÉÍÏÏÔÎÏÛÅÎÉÑÈ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ ÍÏÄÅÌÅÊ.
 604 éÍÅÅÔÓÑ × ×ÉÄÕ ÎÅ ÕÐÒÏÝÅÎÉÅ ÁÒÇÕÍÅÎÔÁ 3 Ï ÔÏÍ, ÞÔÏ ÍÏÄÅÌØ\T ËÏÌØÃÏ Ó
 605 ÄÅÌÅÎÉÅÍ, Á ÕÐÒÏÝÅÎÉÅ ÁÒÇÕÍÅÎÔÁ 2 Ï ËÏÎÅÞÎÏÓÔÉ ÎÁÂÏÒÁ ËÏÎÓÔÒÕËÃÉÊ,
 606 ÄÏÓÔÁÔÏÞÎÙÈ ÄÌÑ ÒÁÓÓÍÏÔÒÅÎÉÑ ÄÌÑ ÐÒÏ×ÅÒËÉ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ. ÷
 607 ÒÅÚÕÌØÔÁÔÅ ÕÐÒÏÝÅÎÉÑ ÍÙ ÏÐÑÔØ ÐÒÉÈÏÄÉÍ Ë ÕÓÌÏ×ÉÀ Ï ÔÏÍ, ÞÔÏ ÎÅËÏÔÏÒÏÅ
 608 ÐÏÌÕËÏÌØÃÏ (ÕÖÅ ÄÒÕÇÏÅ) ×ËÌÁÄÙ×ÁÅÔÓÑ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ. ÷ ÓÌÕÞÁÅ Ó
 609 ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÍÉ ËÏÎÅÞÎÙÍÉ Á×ÔÏÍÁÔÁÍÉ ×ÏÚÍÏÖÎÏÅ ÕÐÒÏÝÅÎÉÅ
 610 ËÏÎÓÔÒÕËÃÉÊ ÏËÁÚÙ×ÁÅÔÓÑ ÏÞÅÎØ ÚÎÁÞÉÔÅÌØÎÏÅ.
 611
 612 ôÅÏÒÅÍÕ~\ref{th:comm-monot}
 613 Ï ÒÁÚÒÅÛÉÍÏÓÔÉ ðü ÄÌÑ ÐÒÏÇÒÁÍÍ Ó ËÏÍÍÕÔÁÔÉ×ÎÙÍÉ É ÍÏÎÏÔÏÎÎÙÍÉ
 614 ÏÐÅÒÁÔÏÒÁÍÉ ÔÏÖÅ ÍÏÖÎÏ ×ÉÄÅÔØ × ÜÔÏÍ Ó×ÅÔÅ. õÐÒÏÝÅÎÉÅ ËÏÎÓÔÒÕËÃÉÊ,
 615 ËÏÔÏÒÏÅ ×ÏÚÍÏÖÎÏ × ÔÏÍ ÓÌÕÞÁÅ, ÐÒÉ×ÏÄÉÔ Ë \tNDNo{ÓÅÞÅÎÉÑÍ} ×
 616 ÄÏËÁÚÁÔÅÌØÓÔ×Å ÜÔÏÊ ÔÅÏÒÅÍÙ (\cite{kurs4,ciaa-commut-monot}). äÌÑ
 617 ÄÏËÁÚÁÔÅÌØÓÔ×Á ÄÏÓÔÁÔÏÞÎÏÓÔÉ ÒÁÓÓÍÏÔÒÅÎÉÑ ÉÈ ËÏÎÅÞÎÏÇÏ ÞÉÓÌÁ
 618 ÉÓÐÏÌØÚÕÅÔÓÑ ÄÒÕÇÏÊ ÁÒÇÕÍÅÎÔ, ÎÅ Ó×ÑÚÁÎÎÙÊ Ó ËÏÌØÃÁÍÉ Ó
 619 ÄÅÌÅÎÉÅÍ. ëÁÖÅÔÓÑ, ÞÔÏ ÏÂÁ ÍÅÔÏÄÁ (üÊÌÅÎÂÅÒÇÁ É ÉÓÐÏÌØÚÕÅÍÏÇÏ ×
 620 ÄÏËÁÚÁÔÅÌØÓÔ×Å ôÅÏÒÅÍÙ~\ref{th:comm-monot}) ÍÏÖÎÏ ÏÐÉÓÁÔØ
 621 ÅÄÉÎÏÏÂÒÁÚÎÏ, ÓÄÅÌÁ× <<ÍÏÄÕÌØÎÙÍ>> ÐÏÓÌÅÄÎÉÊ ÁÒÇÕÍÅÎÔ.
 622 \begin{question}
 623   íÏÖÎÏ ÌÉ ÐÅÒÅÎÅÓÔÉ ÒÅÚÕÌØÔÁÔ ôÅÏÒÅÍÙ~\ref{th:comm-monot} ÎÁ ÓÌÕÞÁÊ Ó
 624   ËÒÁÔÎÏÓÔÑÍÉ? íÏÖÎÏ ÌÉ ÏÂßÅÄÉÎÉÔØ ÅÇÏ Ó ÔÅÏÒÅÍÏÊ üÊÌÅÎÂÅÒÇÁ?
 625   \todo{[ÄÌÑ ÜÔÏÇÏ ÎÁÄÏ ÐÏÎÑÔØ, ÞÔÏ ÔÁËÏÅ ËÒÁÔÎÏÓÔÉ ÄÌÑ KAT -- ÜÔÏ ÍÙ ÓÄÅÌÁÅÍ]}
 626 \end{question}
 627 \todo{[ÏÐÉÓÁÔØ ÄÏË-×Á × ÏÂÝÅÍ ÆÏÒÍÁÌÉÚÍÅ, ÉÌÉ ÈÏÔÑ ÂÙ ÄÁÔØ ÐÒÉÍÅÒ]}
 628 \begin{question}\label{q:E-many-reduction-conditions}
 629   ëÁËÉÍÉ Ó×ÏÊÓÔ×ÁÍÉ ÄÏÌÖÎÏ ÏÂÌÁÄÁÔØ ÕÐÒÏÝÅÎÉÅ, ÐÒÉ×ÏÄÑÝÅÅ Ë ÐÅÒ×ÏÍÕ
 630   ÓÐÏÓÏÂÕ? îÅÏÂÈÏÄÉÍÙÅ É ÄÏÓÔÁÔÏÞÎÙÅ ÕÓÌÏ×ÉÑ ÎÁ $\ka K$ ÄÌÑ ÔÏÇÏ,
 631   ÞÔÏÂÙ ÔÁËÏÅ ÕÐÒÏÝÅÎÉÅ ÂÙÌÏ ×ÏÚÍÏÖÎÏ É ÐÒÉ×ÏÄÉÌÏ Ë ÒÁÚÒÅÛÉÍÏÓÔÉ.
 632 \end{question}
 633
 634 %%% Local Variables:
 635 %%% mode: latex
 636 %%% TeX-master: "main"
 637 %%% End: