hypo-withTests-det.tex

   1
   2 \subsection{óÉÎÔÁËÓÉÓ}
   3 \label{sec:uschemes}
   4
   5 \begin{definition}
   6   \tING{õÎÉÆÉÃÉÒÏ×ÁÎÎÏÊ ÓÈÅÍÏÊ\todo{?} 1-ÇÏ ÒÏÄÁ} ÎÁÄ~$\Sigma, T$
   7   ÎÁÚÙ×ÁÅÔÓÑ ÓÈÅÍÁ
   8   $\au A = (Q, \Delta, I, F)$, ÔÁËÁÑ, ÞÔÏ
   9   Å£ ÜÌÅÍÅÎÔÙ $\Delta$ É $Q$
  10   ÒÁÚÂÉ×ÁÀÔÓÑ ÎÁ Ä×Á  ÔÉÐÁ:
  11   \begin{align}
  12     \label{eq:usch-ops-tests}
  13     Q &= Q_\ops \cup Q_\tests
  14     &&\text{(\tING{ÕÚÌÙ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÉ} É \tING{\dÒÁÓÐÏÚÎÁ×ÁÔÅÌÉ})}\\
  15     \Delta &= \Delta_\ops \cup \Delta_\tests,
  16     &&\text{(\tING{ÐÅÒÅÈÏÄÙ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÉ} É \tING{\dÒÁÓÐÏÚÎÁ×ÁÔÅÌÉ})}
  17   \end{align}
  18   ÔÁËÉÅ, ÞÔÏ
  19   \begin{align}
  20     \Delta_\ops &\subseteq Q_\ops \times \Sigma \times Q_\tests,\\
  21     \Delta_\tests &\subseteq Q_\tests \times \Atoms_T \times Q_\ops,
  22   \end{align}
  23   $I \subseteq Q_\tests$, $F \subseteq Q_\tests$ \todo{[subsets or
  24     what?]}
  25   É
  26   ÉÚ ËÁÖÄÏÇÏ ÕÚÌÁ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑ ×ÙÈÏÄÉÔ ÒÏ×ÎÏ ÏÄÉÎ ÐÅÒÅÈÏÄ (\todo{$\pi(u)$}), Á
  27   ÉÚ ËÁÖÄÏÇÏ ÕÚÌÁ\dÒÁÓÐÏÚÎÁ×ÁÔÅÌÑ ×ÙÈÏÄÑÔ ÐÅÒÅÈÏÄÙ ÐÏÍÅÞÅÎÎÙÅ ×ÓÅÍÉ
  28   ÁÔÏÍÁÍÉ $\Atoms_T$, ÐÒÉÞ£Í ËÁÖÄÙÍ\T ÒÏ×ÎÏ ÏÄÉÎ ÒÁÚ. ôÅÍ ÓÁÍÙÍ ÍÏÖÎÏ
  29   ÏÐÒÅÄÅÌÉÔØ ÏÄÎÏÚÎÁÞÎÕÀ ×ÓÀÄÕ ÏÐÒÅÄÅÌ£ÎÎÕÀ ÆÕÎËÃÉÀ:
  30   \begin{equation}
  31     \label{eq:usch-delta}
  32     \delta_{\au A}\colon Q_\tests \times \Atoms_T \to Q_\ops.
  33   \end{equation}
  34 \end{definition}
  35 (õÎÉÆÉÃÉÒÏ×ÁÎÎÁÑ ÓÈÅÍÁ 1-ÇÏ ÒÏÄÁ
  36 ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ Ä×ÕÄÏÌØÎÙÊ ÎÁÐÒÁ×ÌÅÎÎÙÊ ÇÒÁÆ.) ïÐÒÅÄÅÌÅÎÉÅ
  37 ÐÏ×ÔÏÒÑÅÔ ÉÄÅÀ ÏÐÒ-Ñ ÉÚ \cite{??}.
  38
  39 \begin{definition}
  40   \tING{õÎÉÆÉÃÉÒÏ×ÁÎÎÏÊ ÓÈÅÍÏÊ\todo{?} 2-ÇÏ ÒÏÄÁ} ÎÁÄ~$\Sigma, T$
  41   ÎÁÚÙ×ÁÅÔÓÑ ÓÈÅÍÁ
  42   $(Q, \Delta, I, F)$, ÔÁËÁÑ, ÞÔÏ
  43   ×ÓÅ Å£ ÐÅÒÅÈÏÄÙ ÉÍÅÀÔ ÏÓÏÂÙÊ ×ÉÄ:
  44   \begin{align}
  45     \label{eq:usch-2}
  46     \Delta \subseteq Q \times (\Atoms_T \cdot \Sigma^*) \times Q
  47   \end{align}
  48   É
  49   ÉÚ ËÁÖÄÏÇÏ ÕÚÌÁ ×ÙÈÏÄÑÔ ÐÅÒÅÈÏÄÙ ÐÏÍÅÞÅÎÎÙÅ ×ÓÅÍÉ
  50   ÁÔÏÍÁÍÉ $\Atoms_T$, ÐÒÉÞ£Í ËÁÖÄÙÍ\T ÒÏ×ÎÏ ÏÄÉÎ ÒÁÚ. ôÅÍ ÓÁÍÙÍ ÍÏÖÎÏ
  51   ÏÐÒÅÄÅÌÉÔØ ÏÄÎÏÚÎÁÞÎÕÀ ×ÓÀÄÕ ÏÐÒÅÄÅÌ£ÎÎÕÀ ÆÕÎËÃÉÀ:
  52   \begin{equation}
  53     \label{eq:usch-delta}
  54     \delta_{\au A}\colon (Q \times \Atoms_T)
  55     \to
  56     (\Sigma^* \times Q),
  57   \end{equation}
  58   ÏÐÒÅÄÅÌÑÀÝÕÀ \tING{ËÏÎÅÞÎÙÊ ÕÚÅÌ É ÄÅÊÓÔ×ÉÅ ËÁÖÄÏÇÏ ÐÅÒÅÈÏÄÁ}.
  59 \end{definition}
  60
  61 \begin{proposition}
  62   \todo{[ÄÅÔ. ÓÈÅÍÕ ÍÏÖÎÏ ÕÎÉÆÉÃÉÒÏ×ÁÔØ]}
  63 \end{proposition}
  64
  65 ïÐÒ-Ñ ÎÁÛÅÊ ÓÅÍ-ËÉ
  66
  67
  68 \subsection{îÅËÏÔÏÒÙÅ ÒÁÚÒÅÛÉÍÙÅ ÓÌÕÞÁÉ}
  69 \label{sec:simple-decidable}
  70
  71 comm?
  72
  73 monot?
  74
  75 other?
  76
  77
  78 \subsection{þÁÓÔÉÞÎÁÑ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØ É ÍÏÎÏÔÏÎÎÏÓÔØ ÏÐÅÒÁÔÏÒÏ×}
  79 \label{sec:pcommut-monot}
  80
  81 \begin{align}
  82   \label{eq:commut-monot-E}
  83   E_{\comm\monot}(\Sigma,T)  &\eqdef \Ecomm \cup \Emonot,
  84   \text{ÔÁËÉÅ, ÞÔÏ }
  85   \IndepBy{\Ecomm} = \Sigma \times \Sigma,
  86   \ShiftBy{\Emonot}_0 = \emptyset,
  87   \ShiftBy{\Emonot}_1 = \Sigma \times T,\\
  88   \label{eq:commut-monot-E}
  89   E_{\pcomm\monot}(\Sigma,T)  &\eqdef \Epcomm \cup \Emonot,
  90   \text{ÔÁËÉÅ, ÞÔÏ }
  91   \IndepBy{\Epcomm} \subseteq \Sigma \times \Sigma,
  92   \ShiftBy{\Emonot}_0 = \emptyset,
  93   \ShiftBy{\Emonot}_1 = \Sigma \times T.
  94 \end{align}
  95
  96 \begin{align}
  97   \label{eq:commut-monot}
  98   \CommutMonot  &\eqdef \{ E_{\comm\monot}(\Sigma,T) \mid
  99   \Sigma, T \text{ ÌÀÂÙÅ}\}\\
 100   \label{eq:commut-monot}
 101   \PCommutMonot  &\eqdef \{ E_{\pcomm\monot}(\Sigma,T) \mid
 102   \Sigma, T \text{ ÌÀÂÙÅ}\}
 103 \end{align}
 104
 105 \begin{theorem}\cite{kurs4,ciaa-commut-monot,podl-first,podl-prev,podl-last}
 106   $\EOf \SIMPLET(E_{\comm\monot}(\Sigma,T))_{\Sigma,T}$
 107   (\te ÐÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÓÈÅÍ × ÐÒÏÓÔÙÈ ÍÏÄÅÌÑÈ ÐÒÉ ÄÏÐÕÝÅÎÉÑÈ
 108   ÔÁËÏÇÏ ×ÉÄÁ)
 109   ÒÁÚÒÅÛÉÍÁ
 110   ÓÏ ÓÌÏÖÎÏÓÔØÀ $O(l^{(\size{\Sigma}+1)(\size{T}+1)+2}\log l)$,
 111   ÇÄÅ $l$\T Â\'ÏÌØÛÉÊ ÉÚ ÒÁÚÍÅÒÏ× ÓÒÁ×ÎÉ×ÁÅÍÙÈ ÓÈÅÍ.
 112 \end{theorem}
 113 \begin{proof}
 114 óÍ. \cite{kurs4}.
 115 \todo{[ÐÅÒÅÐÉÓÁÔØ ÎÁ ÎÏ×ÙÊ ÌÁÄ]}
 116 \end{proof}
 117
 118 \begin{theorem}
 119 \todo{[ÒÁÚÒ, ÓÌÏÖÎÏÓÔØ]}
 120 \end{theorem}
 121 áÎÏÎÓÉÒÏ×ÁÎÁ × \cite{dm6-pcommut-monot}.
 122 \begin{proof}
 123 \todo{[p. comm. monot algo?]}
 124 \end{proof}
 125
 126
 127
 128 \subsection{éÓÓÌÅÄÏ×ÁÎÉÅ ÐÒÉÍÅÎÉÍÏÓÔÉ ÔÅÏÒÅÍÙ üÊÌÅÎÂÅÒÇÁ}
 129 \label{sec:E-for-comm-monot}
 130
 131 íÏÄÅÌÉÒ dmta, ÄÅÌÉÔÅÌÉ ÎÕÌÑ, Ó×ÑÚØ Ó Ô. HK
 132
 133 åÓÔØ Ñ×ÎÏÅ ÏÞÅÎØ ÐÒÏÓÔÏÅ ÐÒÅÐÑÔÓÔ×ÉÅ Ë ÐÒÉÍÅÎÅÎÉÀ ÓÐÏÓÏÂÁ HK
 134 (Eilenb Ë Ó×ÏÂÏÄÎÏÊ ÍÏÄÅÌÉ) ÄÏËÁÚÁÔÅÌØÓÔ×Á ÒÁÚÒÅÛÉÍÏÓÔÉ: ËÌÀÞÅ×ÏÅ
 135 ÕÔ×-Å ÄÌÑ ÎÅÇÏ -- ÄÏÓÔÁÔÏÞÎÏÅ ÕÓÌÏ×ÉÅ ÒÁÚÒÅÛÉÍÏÓÔÉ -- ËÏÌØÃÏ
 136 ÍÎÏÖÅÓÔ× Ó ËÒÁÔÎÏÓÔÑÍÉ, ÓÏÏÔ×. Ó×ÏÂÏÄÎÏÊ ÍÏÄÅÌÉ, ×ËÌÁÄÙ×ÁÅÔÓÑ ×
 137 ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ (\todo{[ÔÅÌÏ?]}. îÏ
 138 Õ ÎÁÓ × $\Cons_{\Sigma,T,E}$, $E \in \Commut \oplus \Shifts$, Ñ×ÎÏ
 139 ÅÓÔØ ÄÅÌÉÔÅÌÉ ÎÕÌÑ, ÎÁÐÒÉÍÅÒ:
 140 \begin{align}
 141   \label{eq:bool-zero-divisor}
 142   \Cons_{\Sigma,T,E} &\models p \cdot \n{p} = 0,\\
 143   \label{eq:shifts-zero-divisor}
 144   \Cons_{\Sigma,T,E} &\models (p a) \cdot (\n{p}) = 0
 145   \text{ ÅÓÌÉ $(pa\n{p} =0) \in E$,}
 146 \end{align}
 147 ÞÔÏ ÄÅÌÁÅÔ, ÎÁ ÐÅÒ×ÙÊ ×ÚÇÌÑÄ,
 148 ÎÅ×ÏÚÍÏÖÎÙÍ ÓÏÚÄÁÎÉÅ ËÏÌØÃÁ Ó ÄÅÌÅÎÉÅÍ ÎÁ ÏÓÎÏ×Å ÜÔÏÊ
 149 ÁÌÇÅÂÒÙ, ÓÏÈÒÁÎÑÀÝÅÇÏ ÓÅÍÁÎÔÉÞÅÓËÉÅ Ó×ÏÊÓÔ×Á. (ïÔÓÕÔÓÔ×ÉÅ ÄÅÌÉÔÅÌÅÊ
 150 ÎÕÌÑ ÎÅÏÂÈÏÄÉÍÏÅ, ÎÏ ÎÅ ÄÏÓÔÁÔÏÞÎÏÅ ÕÓÌÏ×ÉÑ ×ÌÏÖÉÍÏÓÔÉ × ËÏÌØÃÏ Ó ÄÅÌÅÎÉÅÍ.)
 151
 152 \todo{[ÚÁÞÅÍ ÜÔÏ ÎÁÍ?]}
 153
 154 îÏ ÔÏÔ ÖÅ ÓÌÕÞÁÊ ÍÎÏÇÏÌÅÎÔÏÞÎÙÈ Á×ÔÏÍÁÔÏ× ÐÒÅÄÏÓÔÁ×ÌÑÅÔ ÎÁÍ ×ÁÖÎÙÊ
 155 ÐÒÉÍÅÒ, ÐÏËÁÚÙ×ÁÀÝÉÊ, ÞÔÏ ÜÔÏ ×Ó£-ÔÁËÉ ÍÏÖÅÔ ÂÙÔØ ×ÏÚÍÏÖÎÏ.
 156
 157 \begin{example}[k\dÈÌÅÎÔÏÞÎÙÅ Á×ÔÏÍÁÔÙ]
 158   \label{ex:nmta-KA-KAT}
 159   îÁ $k$ ÌÅÎÔÁÈ Ä×ÕÈÂÕË×ÅÎÎÙÊ ÁÌÆÁ×ÉÔ.
 160
 161   \subparagraph{÷ $\RExp_{\Sigma}$.}
 162
 163   $\Sigma = {\Sigma_1 \cup \dotsb \cup \Sigma_k}$
 164   $\Sigma_i = \{ a_i, b_i \}$. (÷ÓÅ ÂÕË×Ù ÒÁÚÌÉÞÎÙ.)
 165
 166   \subparagraph{÷ $\RExp_{\Sigma',T'}$.}
 167   $\Sigma' = {\Sigma_1' \cup \dotsb \cup \Sigma_k'}$
 168   $\Sigma_i' = \{ c_i \}$ (<<ÛÁÇÉ ÐÏ ÌÅÎÔÁÍ>>),
 169   $T' = T_1' \cup \dotsb \cup T_k'$
 170   $T_i' = \{ p_i \}$ (ËÏÄÉÒÕÀÔ ÚÎÁÞÅÎÉÑ ÚÁÐÉÓÁÎÎÙÅ ÎÁ ÌÅÎÔÁÈ).
 171
 172   $\Expl_{\Sigma_1,\dotsc,\Sigma_n} \colon
 173   \RExp_{\Sigma}
 174   \to
 175   \RExp_{\Sigma',T'}$
 176
 177   \begin{align}
 178     \label{eq:Expl}
 179     \Expl(a_i) &= \n{p_i} c_i
 180     &
 181     \Expl(b_i) &= p_i c_i
 182   \end{align}
 183
 184   $\Expl$ ÐÅÒÅ×ÏÄÉÔ ÐÒÏÇÒÁÍÍÙ ÂÅÚ ÔÅÓÔÏ× (ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ,
 185   Á×ÔÏÍÁÔÙ) × ÐÒÏÇÒÁÍÍÙ Ó ÔÅÓÔÁÍÉ. ÷ÏÔ ËÁË ÓÏÏÔÎÏÓÉÔÓÑ ÉÈ
 186   ÐÏÄÒÁÚÕÍÅ×ÁÅÍÁÑ ÓÅÍÁÎÔÉËÁ.
 187
 188   \subparagraph{÷ $\HornOf\RKA$.} \todo{[REL, cont?]}
 189   íÎÏÖÅÓÔ×Ï ÐÏÓÙÌÏË $E$\T ÔÁËÉÅ ÕÓÌÏ×ÉÑ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ (×ÙÒÁÖÅÎÎÙÅ ×
 190   ÔÅÒÍÉÎÁÈ ÏÔÎÏÛÅÎÉÑ ÎÅÚÁ×ÉÓÉÍÏÓÔÉ):
 191   \begin{equation}
 192     \label{eq:multitape-commut}
 193     a \IndepBy{E} b \iff a \in \Sigma_i, b \in \Sigma_j, i \neq j.
 194   \end{equation}
 195
 196   ðÏ×ÅÒÑÅÍ
 197   $$
 198   \RKA \models E \implic s = t.
 199   $$
 200   \todo{[éÌÉ ÐÏÄËÌÁÓÓ?]}
 201   òÁÚÒÅÛÉÍÏÓÔØ ÐÒÏÂÌÅÍÙ ÜË×-ÔÉ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ $k$\dÈÌÅÎÔÏÞÎÙÈ
 202   Ä×ÕÈÂÕË×ÅÎÎÙÈ
 203   Á×ÔÏÍÁÔÏ×\T
 204   ÒÁÚÒÅÛÉÍÏÓÔØ $\HOf_{\{ E \}} \RKA$.
 205
 206   \subparagraph{÷ $\HornOf\RKAT$.} \todo{[REL, cont?]}
 207   íÎÏÖÅÓÔ×Ï ÐÏÓÙÌÏË $E' = \Ecomm \cup \Esh$\T ÔÁËÏÅ, ÐÏ ÓÕÔÉ ÅÇÏ ÔÏÖÅ
 208   ÍÏÖÎÏ ×ÙÒÁÚÉÔØ ÏÔÎÏÛÅÎÉÅÍ ÎÅÚÁ×ÉÓÉÍÏÓÔÉ:
 209   \begin{gather}
 210     \label{eq:multitape-steps-commut}
 211     \text{äÌÑ $c, d \in \Sigma'$: }
 212     c \IndepBy{\Ecomm} d \iff c \in \Sigma_i', d \in \Sigma_j', i \neq j,\\
 213     \label{eq:multitape-values-commut}
 214     \text{äÌÑ $c\in \Sigma', p \in T'$: }
 215     p \Indep' c \iff p \in T_i', c \in \Sigma_j', i \neq j.
 216   \end{gather}
 217   ñ×ÎÏ ÕÓÌÏ×ÉÑ, ×ÙÒÁÖÁÅÍÙÅ $\Indep'$ ÚÁÐÉÛÕÔÓÑ ÔÁË:
 218   íÎÏÖÅÓÔ×Ï ÐÏÓÙÌÏË $E'$\T ÕÓÌÏ×ÉÑ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ É ÓÄ×ÉÇÏ×:
 219   \begin{equation}
 220     \Esh = \{
 221     (p c \n{p} = 0),
 222     (\n{p} c p = 0)
 223     \mid p \Indep' c
 224     \}.
 225   \end{equation}
 226   ðÕÓÔØ $s' = \Expl(s), t' = \Expl(t)$.
 227   ðÏ×ÅÒÑÅÍ
 228   $$
 229   \RKAT \models E' \implic s' = t'.
 230   $$
 231   \todo{[éÌÉ ÄÒ. ÐÏÄËÌÁÓÓ?]}
 232   òÁÚÒÅÛÉÍÏÓÔØ ÐÒÏÂÌÅÍÙ ÜË×-ÔÉ ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ 2\dÈÌÅÎÔÏÞÎÙÈ
 233   Á×ÔÏÍÁÔÏ×\T
 234   ÒÁÚÒÅÛÉÍÏÓÔØ $\HOf_{\{ E' \}} \RKAT$.
 235
 236 \end{example}
 237
 238 úÁÍÅÔÉÍ ×ÁÖÎÕÀ ÄÌÑ ÎÁÓ ×ÅÝØ:
 239 \begin{proposition}
 240 × ÐÏÄÁÌÇÅÂÒÅ $\Cons_{\Sigma',T',E'}$,
 241 ÐÏÒÏÖÄ£ÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÅÊ ÏÂÒÁÚÁ $\RExp_{\Sigma}$ ÐÒÉ ÏÐÉÓÁÎÎÏÍ
 242 ÏÔÏÂÒÁÖÅÎÉÉ\dÐÅÒÅ×ÏÄÅ $\Expl$, ÎÅÔ ÄÅÌÉÔÅÌÅÊ ÎÕÌÑ.
 243 \end{proposition}
 244 ôÁË ÞÔÏ ÎÁ ÏÓÎÏ×Å ÔÁËÏÊ ÐÏÄÁÌÇÅÂÒÙ ÒÁÚÕÍÎÏ ÐÒÉÍÅÎÑÔØ ÔÅÏÒÅÍÕ
 245 Eilenb. (ðÒÁ×ÄÁ, ÞÔÏÂÙ ÐÅÒÅÈÏÄ ÂÙÌ ÒÁÚÕÍÎÙÍ, ÎÕÖÎÏ ÅÝ£ ÕÂÅÄÉÔØÓÑ ×
 246 ÔÏÍ, ÞÔÏ ÐÒÉ ÐÅÒÅ×ÏÄÅ ÉÚ ÏÄÎÏÚÎÁÞÎÙÈ ÐÏÌÕÞÁÀÔÓÑ ÏÄÎÏÚÎÁÞÎÙÅ ÐÒÏÇÒÁÍÍÙ
 247 (ÏÄÎÏÚÎÁÞÎÁÑ ÐÏÄÁÌÇÅÂÒÁ).)
 248 \begin{proof}
 249 éÄÅÑ × ÔÏÍ, ÞÔÏ
 250 ÚÁ ×ÓÑËÉÍ $p_i$ ×
 251 ×ÙÒÁÖÅÎÉÉ ÎÅÐÏÓÒÅÄÓÔ×ÅÎÎÏ ÓÌÅÄÕÅÔ $c_i$, ÔÁË ÞÔÏ
 252 ÕÓÌÏ×ÉÑ~\eqref{eq:bool-zero-divisor}, \eqref{eq:shifts-zero-divisor}
 253 ÎÅ ÏÂÎÕÌÑÔ ÐÒÏÉÚ×ÅÄÅÎÉÑ Ä×ÕÈ ÜÌÅÍÅÎÔÏ× ÉÚ ÜÔÏÊ ÐÏÄÁÌÇÅÂÒÙ.
 254
 255 \todo{[ÄÏË-×Ï]}
 256 \end{proof}
 257 \begin{proposition}
 258   \todo{[åÓÌÉ $s$ ÏÄÎÏÚÎÁÞÎÏ ÏÔÎÏÓ $\Cons_{\Sigma,E_{\mword{mt}}}$, ÔÏ
 259     $\Expl(s)$ ÏÄÎÏÚÎÁÞÎÏ ÏÔÎÏÓ $\Cons_{\Sigma',T',E'}$]}.
 260 \end{proposition}
 261
 262 ðÏÐÒÏÂÕÅÍ ÕÓÔÁÎÏ×ÉÔØ É ÓÏÏÔ×-Å, ÏÂÒÁÔÎÏÅ $\Expl$. üÔÏ ÂÕÄÅÔ ÒÅÛÅÎÉÅÍ
 263 Ä×ÕÈ ÚÁÄÁÞ: ÄÅÍÏÎÓÔÒÁÃÉÅÊ ÔÏÇÏ, ÞÔÏ ÏÂÅ <<ÁÂÓÔÒÁËÔÎÙÅ ÍÏÄÅÌÉ
 264 ÐÒÏÇÒÁÍÍ>> ÜË×É×ÁÌÅÎÔÎÙ (ÏÄÉÎÁËÏ×Ï ×ÙÒÁÚÉÔÅÌØÎÙ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ
 265 ÄÅÔ. ÍÎÏÇÏÌÅÎÔÏÞÎÙÍ Á×ÔÏÍÁÔÁÍ), É ÐÏÌÕÞÅÎÉÅÍ
 266 ÓÐÏÓÏÂÁ Ó×ÅÄÅÎÉÑ ÏÂÝÅÇÏ ÓÌÕÞÁÑ ÒÁ×ÅÎÓÔ×Á × ... Ë ÒÁ×ÅÎÓÔ×Õ × ÐÏÄÁÌÇÅÂÒÅ ÂÅÚ
 267 ÄÅÌÉÔÅÌÅÊ ÎÕÌÑ, ÞÔÏ ÏÔËÒÏÅÔ ÐÕÔØ ÄÌÑ ÐÒÉÍÅÎÅÎÉÑ Ô. Eilenb., ÔÁË, ËÁË
 268 ÜÔÏ ÄÅÌÁÌÉ HK.
 269
 270 \paragraph{õÓÌÏ×ÉÑ $E \in \MultitapeT_2$.}
 271 \todo{[ÏÂÏÚÎÁÞ. Ó×. ÐÒÏÉÚ×.]}
 272
 273 ðÏ ÓÕÔÉ ÎÁÍ ÎÁÄÏ ÉÚÂÁ×ÉÔØÓÑ ÏÔ ÎÅËÏÔÏÒÏÊ ÉÚÂÙÔÏÞÎÏÓÔÉ × ÐÒÅÄÏÓÔÁ×ÌÅÎÎÏÊ
 274 ÐÒÏÇÒÁÍÍÅ (ÎÅ ÔÅÓÔÉÒÏ×ÁÔØ ÍÎÏÇÏ ÒÁÚ ÏÄÎÏ É ÔÏ ÖÅ ÚÎÁÞÅÎÉÅ ÂÁÚÏ×ÏÇÏ ÔÅÓÔÁ).
 275
 276 âÕÄÅÍ ÒÁÂÏÔÁÔØ Ó ÐÒÅÄÓÔÁ×ÌÅÎÉÅÍ ÐÒÏÇÒÁÍÍ × ×ÉÄÅ ÓÉÓÔÅÍ ÐÅÒÅÈÏÄÏ×.
 277
 278 ïÇÒÁÎÉÞÉÍÓÑ ÒÁÓÓÍÏÔÒÅÎÉÅÍ ÕÎÉÆÉÃÉÒÏ×ÁÎÎÙÈ ÓÈÅÍ.
 279
 280 ÷ÏÚØÍ£Í ÕÎÉÆÉÃÉÒÏ×ÁÎÎÕÀ ÓÈÅÍÕ $\au A = (Q, \Delta, I, F)$.
 281
 282 ðÏÓÔÒÏÉÍ ÎÏ×ÕÀ $\Hat{\au A} = (Q', \Delta', I', F')$:
 283
 284 $Q' = Q_\ops \times \Atoms_{T'}$
 285
 286 \todo{[ÏÐÒ $\alpha[p]$]}
 287
 288 äÌÑ ËÁÖÄÏÇÏ ÕÚÌÁ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑ $v \in Q_\ops$
 289 ÓÔÁÒÏÊ ÓÈÅÍÙ ÄÌÑ ËÁÖÄÏÇÏ $\alpha \in \Atoms_T$
 290 ÄÏÂÁ×ÉÍ × ÎÏ×ÕÀ Ä×Á ÐÅÒÅÈÏÄÁ:
 291 \begin{align}
 292   \label{eq:transform-transitions}
 293   &\left(
 294   (v, \alpha)
 295   \transition{c_i \cdot p_i}
 296   ( \delta(u, \alpha[p_i]), \alpha[p_i])
 297   \right),\\
 298   &\left(
 299   (v, \alpha)
 300   \transition{c_i \cdot \n{p_i}}
 301   ( \delta(u, \alpha[\n{p_i}]), \alpha[\n{p_i}])
 302   \right),
 303 \end{align}
 304 ÇÄÅ $u$\T ËÏÎÅÃ ÐÅÒÅÈÏÄÁ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑ ÉÚ $v$ ($u = \delta(v)$),
 305 $c_i$\T ÂÁÚÏ×ÙÊ ÏÐÅÒÁÔÏÒ, ËÏÔÏÒÙÍ ÐÏÍÅÞÅÎ ÜÔÏÔ ÐÅÒÅÈÏÄ
 306 ($\pi(v) = c_i$). úÄÅÓØ ÏÓÏÂÁÑ ÒÏÌØ Õ $p_i$\T
 307 ÅÄÉÎÓÔ×ÅÎÎÏÇÏ ÂÁÚÏ×ÏÇÏ ÔÅÓÔÁ, ÚÁ×ÉÓÉÍÏÇÏ ÏÔ $c_i$ ÓÏÇÌÁÓÎÏ $E$:
 308 \begin{equation}
 309   \label{eq:transform-for-Dep}
 310   p_i \Dep c_i).
 311 \end{equation}
 312 \todo{[ÏÐÒÅÄ $\Dep$]}
 313
 314 \todo{[ÚÁ× ÏÔ ÔÏÇÏ, ÞÔÏ ÔÁËÏÅ I:]}
 315
 316 ðÏÌÏÖÉÍ $I' = $, $F' = $ ??
 317
 318 \begin{proposition}
 319   \todo{ÓÏÈÒ-Å ÉÎÔÅÒÐÒ, }
 320 óÏÈÒÁÎÅÎÉÅ ÏÄÎÏÚÎ.
 321 \end{proposition}
 322
 323 èÏÔØ ÍÙ ÐÏÌÕÞÉÌÉ É ÎÅ ÓÏ×ÓÅÍ ÔÁËÏÊ ×ÉÄ, ËÁË ÈÏÔÅÌÉ (ÈÏÔÅÌÉ, ÞÔÏÂÙ
 324 ÐÏÓÌÅ ×ÓÑËÏÇÏ $p_i^\nu$ ÂÙÌ $c_i$, Á ÐÏÌÕÞÉÌÉ ÎÁÏÂÏÒÏÔ), ÜÔÏ ÎÁ ÍÎÅ
 325 ÐÏÍÅÛÁÅÔ: ÅÓÌÉ ÐÏÓÍÏÔÒÅÔØ ÎÁ ÓÈÅÍÕ <<ÓÚÁÄÉ ÎÁÐÅÒ£Ä>>, ÐÏÌÕÞÉÔÓÑ ÓÈÅÍÁ
 326 ÔÏÇÏ ×ÉÄÁ, ËÏÔÏÒÏÇÏ ÎÁÍ ÈÏÔÅÌÏÓØ. (÷ ÔÅÒÍÉÎÁÈ ÍÁÔÒÉÃ: ÕÍÎÏÖÁÔØ ÍÏÖÎÏ ×
 327 ÒÁÚÎÏÍ ÐÏÒÑÄËÅ.) öÅÌÁÅÍÏÅ Ó×ÏÊÓÔ×Ï ×ÙÐÏÌÎÅÎÏ:
 328 \begin{proposition}
 329   \todo{[ÒÁÂÏÔÁÅÍ × ÐÏÄÁÌÇÅÂÒÅ, ÇÄÅ ÎÅÔ ÄÅÌ-ÅÊ ÎÕÌÑ]}
 330 \end{proposition}
 331
 332 \begin{corollary}
 333   ðü ÄÌÑ ÔÁËÉÈ ÓÈÅÍ ÒÁÚÒÅÛÉÍÁ. \todo{[!!]}
 334 \end{corollary}
 335 \begin{proof}
 336   íÏÖÎÏ ÕÓÔÁÎÏ×ÉÔØ ÓÏÏÔ×ÅÔÓÔ×ÉÅ
 337   \begin{align}
 338     \label{eq:tests-to-dmta}
 339     c_i p_i &\mapsto a_i'
 340     &
 341     c_i \n{p_i} &\mapsto b_i'
 342   \end{align}
 343   É Ó×ÅÓÔÉ ÐÒÏÂÌÅÍÕ Ë ðü dmta.
 344 \end{proof}
 345 \begin{remark}
 346   ÷ÏÏÂÝÅ-ÔÏ ÎÁÍ ÈÏÔÅÌÏÓØ ÂÙ ÂÏÌÅÅ ÏÂÝÅÇÏ ËÒÉÔÅÒÉÑ, ÂÅÚ ÚÁÍÅÎÙ
 347   ×ÙÒÁÖÅÎÉÊ Ó ÔÅÓÔÁÍÉ ÎÁ ×ÙÒÁÖÅÎÉÑ ÂÅÚ, Á ×ÙÒÁÖÅÎÎÙÊ ÎÅÐÏÓÒÅÄÓÔ×ÅÎÎÏ ×
 348   ×ÉÄÅ ÕÓÌÏ×ÉÊ ÎÁ \KAT, ÄÏÓÔÁÔÏÞÎÙÈ ÄÌÑ ÒÁÚÒÅÛÉÍÏÓÔÉ.
 349
 350   \todo{[ÉÚÌÏÖÉÔØ ËÁË ×Ù×ÏÄ ÎÕÖÎÙÈ ÕÓÌÏ×ÉÊ]}
 351 \end{remark}
 352
 353 \paragraph{õÓÌÏ×ÉÑ $E \in \Commut \oplus \Shifts$.}
 354
 355 ÷ÏÚØÍ£Í ÕÎÉÆÉÃÉÒÏ×ÁÎÎÕÀ ÓÈÅÍÕ $\au A = (Q, \Delta, I, F)$.
 356
 357 ðÏÓÔÒÏÉÍ ÎÏ×ÕÀ $\Hat{\au A} = (Q', \Delta', I', F')$:
 358
 359 $Q' = Q_\ops \times \Atoms_{T'}$
 360
 361 \todo{[ÏÐÒ $\alpha[\beta]$]}
 362
 363 äÌÑ ËÁÖÄÏÇÏ ÕÚÌÁ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑ $v \in Q_\ops$
 364 ÓÔÁÒÏÊ ÓÈÅÍÙ ÄÌÑ ËÁÖÄÏÇÏ $\alpha \in \Atoms_T$
 365 ÂÕÄÅÍ ÄÅÊÓÔ×Ï×ÁÔØ ÔÁË.
 366 ðÕÓÔØ $\pi(v) = a$, $\alpha$ ÉÍÅÅÔ ×ÉÄ:
 367 \begin{equation}
 368   \label{eq:alpha}
 369   q_1^{\nu_1} \dotsm q_m^{\nu_m}.
 370 \end{equation}
 371 ðÏÓÔÒÏÉÍ ÓÐÉÓÏË $T'$ ÂÁÚÏ×ÙÈ ÔÅÓÔÏ×:
 372 \begin{equation}
 373   \label{eq:T'}
 374   T' = \{ q_i \mid q_i \notin \ShiftOf_{\nu_i}(a),\; i = 1, \dotsc, m \}.
 375 \end{equation}
 376 é ÄÏÂÁ×ÉÍ × ÎÏ×ÕÀ ÓÈÅÍÕ $2^{\size{T'}}$ ÐÅÒÅÈÏÄÏ×\T ÐÏ ÏÄÎÏÍÕ ÎÁ
 377 ËÁÖÄÙÊ ÜÌÅÍÅÎÔ $\beta \in \Atoms_{T'}$:
 378 \begin{align}
 379   \label{eq:transform-transitions}
 380   &\left(
 381   (v, \alpha)
 382   \transition{a \cdot \beta}
 383   ( \delta(u, \alpha[\beta]), \alpha[\beta])
 384   \right),
 385 \end{align}
 386 ÇÄÅ $u$\T ËÏÎÅÃ ÐÅÒÅÈÏÄÁ\dÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑ ÉÚ $v$ ($u = \delta(v)$).
 387
 388 \todo{[ÚÁ× ÏÔ ÔÏÇÏ, ÞÔÏ ÔÁËÏÅ I:]}
 389
 390 ðÏÌÏÖÉÍ $I' = $, $F' = $ ??
 391
 392 üÔÏ ÏÂÏÂÝÅÎÉÅ ÒÁÓÓÍÏÔÒÅÎÎÏÊ ÄÏ ÜÔÏÇÏ ËÏÎÓÔÒÕËÃÉÉ ÄÌÑ ÞÁÓÔÎÏÇÏ ÓÌÕÞÁÑ
 393 $E = \Emt$ (ÜÔÁ ÄÁ£Ô ÔÅ ÖÅ ÒÅÚÕÌØÔÁÔÙ × ÞÁÓÔÎÏÍ ÓÌÕÞÁÅ):
 394 × ÓÌÕÞÁÅ $\Emt$ $T' = \{ p_i \}$ ÄÌÑ $a = c_i$, \tk $p_i$
 395 ÓÏÇÌÁÓÎÏ~$\Emt$\T ÅÄÉÎÓÔ×ÅÎÎÙÊ ÂÁÚÏ×ÙÊ ÔÅÓÔ, ÔÁËÏÊ, ÞÔÏ $q \notin
 396 \ShiftOf_0(c_i)$, ÒÁ×ÎÏ ËÁË É ÅÄÉÎÓÔ×ÅÎÎÙÊ ÂÁÚÏ×ÙÊ ÔÅÓÔ, ÔÁËÏÊ, ÞÔÏ $q \notin
 397 \ShiftOf_1(c_i)$ (ÎÁ ÜÔÏ ÕÖÅ ÂÙÌÏ ÏÂÒÁÝÅÎÏ ×ÎÉÍÁÎÉÅ ÕÓÌÏ×ÉÅÍ
 398 ÚÁ×ÉÓÉÍÏÓÔÉ~\eqref{eq:transform-for-Dep}).
 399
 400 \begin{proposition}
 401   \todo{ÓÏÈÒ-Å ÉÎÔÅÒÐÒ, }
 402 óÏÈÒÁÎÅÎÉÅ ÏÄÎÏÚÎ.
 403 \end{proposition}
 404
 405 áÎÁÌÏÇ ÕÔ×ÅÒÖÄÅÎÉÑ ÏÂ ÏÔÓÕÔÓÔ×ÉÉ ÄÅÌÉÔÅÌÅÊ ÎÕÌÑ:
 406 \begin{proposition}
 407   \todo{[ÏÔÎÏÓÉÔÅÌØÎÏÅ ÏÔÓÕÔÓÔ×ÉÅ ÄÅÌ-ÅÊ ÎÕÌÑ]}
 408 \end{proposition}
 409 \begin{proof}
 410   \todo{[???]}
 411 \end{proof}
 412
 413 \begin{question}
 414   íÏÖÎÏ ÌÉ ÎÁÄÅÑÔØÓÑ ÎÁ ÒÁÚÕÍÎÏÅ ÐÒÉÍÅÎÅÎÉÅ Ô Eilenb × ÜÔÏÍ ÓÌÕÞÁÅ?
 415   \todo{[ÜÔÏ??]}
 416 \end{question}
 417
 418 \paragraph{óÒÁ×ÎÅÎÉÅ Ó ÜÌÉÍÉÎÁÃÉÅÊ.}
 419 \todo{...}
 420
 421
 422 íÙ ÐÒÏÄÅÌÁÌÉ ÜÔÏ ÄÌÑ ÓÈÅÍ, É ÕÓÌÏ×ÉÅ ÄÌÑ ÓÈÅÍ -- Á ÍÏÖÎÏ ÌÉ ÅÇÏ
 423 ÐÅÒÅÎÅÓÔÉ ÎÁ RExp (ÐÏÄÁÌÇÅÂÒÁ, ÐÏÒÏÖÄ. ÓÈÅÍÏÊ, ÔÁ ÖÅ ÂÕÄÅÔ?)
 424
 425 ïÂÏÂÝÅÎÉÅ ÜÔÏÇÏ ÕÓÌÏ×ÉÑ (ÄÅÌ-ÌÉ ÎÕÌÑ)
 426
 427 ÷ÏÚÍÏÖÎÏ, ÜÔÏ ÎÁÍ£Ë ÎÁ ÔÏ, ÞÔÏ ÔÁËÏÊ <<ËÒÁÔËÉÊ>> ×ÉÄ (ÂÅÚ ÉÚÂÙÔÏÞÎÏÓÔÉ)
 428 ÂÏÌÅÅ ÐÏÄÈÏÄÑÝÉÊ ÄÌÑ ÒÅÛÅÎÉÑ ÐÒÏÂÌÅÍÙ ÜË×-ÔÉ ÐÏÄÏÂÎÙÈ
 429 ÄÅÔÅÒÍ. ÐÒÏÇÒÁÍÍ, ÞÅÍ <<ÒÁÓÐÒÏÓÔÒÁÎ£ÎÎÙÊ>> (Ó ÉÚÂÙÔÏÞÎÏÓÔØÀ),
 430 ÐÒÉ×ÅÄÅÎÉÅ Ë ËÏÔÏÒÏÍÕ ÞÁÓÔÏ ÂÙÌÏ ÐÅÒ×ÙÍ ÛÁÇÏÍ ÁÌÇÏÒÉÔÍÁ ÐÒÏ×ÅÒËÉ
 431 Ü×Ë-ÔÉ × \cite{???} (ÕÎÉÆÉËÁÃÉÑ).
 432
 433
 434 %%% Local Variables:
 435 %%% mode: latex
 436 %%% TeX-master: "main"
 437 %%% End: