notations.tex

   1 % ``ÍÏÒÆÏÌÏÇÉÑ'' ÍÏÅÊ ÒÁÂÏÔÙ
   2
   3 %\subsection{ðÏ ÒÏÌÑÍ}
   4
   5 %% \todo{[$Q_\Sigma$\T ËÏÇÄÁ ÓÉÇÎÁÔÕÒÁ, ÄÌÑ ÉÎÔÅÒÐÒ. ×ÙÒÁÖÅÎÉÊ, a $Q(\Sigma)$\T ÐÏÓÔÒÏÅÎÏ ÎÁ ÏÓÎÏ×Å
   6 %%   (ÎÁÐÒ. $\Strs()$)]}
   7
   8 \todo{[ÎÅÐÏÌÎÙÊ ÓÐÉÓÏË]}
   9
  10 \newcommand*{\metav}{{\footnotesize \textbf{ÍÅÔÁÐÅÒÅÍÅÎÎÙÅ}}\xspace}
  11 \begin{description}
  12 \item[üÌÅÍÅÎÔÙ ÓÉÇÎÁÔÕÒ] \mbox{}
  13   \begin{itemize}
  14   \item ËÏÎÓÔÁÎÔÙ: \mbox{}
  15     \begin{itemize}
  16     \item \mbox{} [ÜÌÅÍÅÎÔÙ ÁÌÆÁ×ÉÔÏ×?  --ÄÌÑ ÚÁÐÉÓÉ ÐÒÏÇÒÁÍÍ]
  17       \begin{itemize}
  18       \item ÂÁÚÏ×ÙÅ ÏÐÅÒÁÔÏÒÙ: \metav $a$, $b$, \dots;
  19       \item ÂÁÚÏ×ÙÅ ÔÅÓÔÙ: \metav $p$, $q$, \dots;
  20       \end{itemize}
  21     \end{itemize}
  22   \end{itemize}
  23   [ÅÝ£?]
  24 \item[óÉÇÎÁÔÕÒÙ] \mbox{}
  25   \begin{itemize}
  26   \item \mbox{} [ÁÌÆÁ×ÉÔÙ? --ÄÌÑ ÚÁÐÉÓÉ ÐÒÏÇÒÁÍÍ]
  27     \begin{itemize}
  28     \item ËÏÎÅÞÎÙÊ ÁÌÆÁ×ÉÔ ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ×: \metav $\Sigma$;
  29     \item ËÏÎÅÞÎÙÊ[??] ÁÌÆÁ×ÉÔ ÂÁÚÏ×ÙÈ ÔÅÓÔÏ×: \metav $T$;
  30     \end{itemize}
  31   \end{itemize}
  32   [ÅÝ£?]
  33 \item[óÉÎÔÁËÓÉÞÅÓËÉÅ ÏÂßÅËÔÙ] \mbox{}
  34   \begin{itemize}
  35   \item ÓÏÓÔÁ×ÎÙÅ <<ÐÒÏÇÒÁÍÍÙ>> É ÉÈ ÞÁÓÔÉ:
  36     \begin{itemize}
  37     \item ÂÕÌÅ×ÓËÉÅ ÔÅÒÍÙ (× ÒÅÇÕÌÑÒÎÙÈ ×ÙÒÁÖÅÎÉÑÈ):
  38       \metav $\bt s$, $\bt t$, \dots;
  39     \item <<ÌÉÎÅÊÎÏ>> ÚÁÐÉÓÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ\T ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ (ÔÅÒÍÙ):
  40       0, 1 [ÎÅ ÓÔÏÉÔ ÐÉÓÁÔØ? ×ÅÄØ ÉÚ ÓÉÇÎÁÔÕÒÙ?];
  41       \metav $s$, $t$, \dots;
  42       \begin{itemize}
  43       \item ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÒÅÇÕÌÑÒÎÏÅ ×ÙÒÁÖÅÎÉÅ ÎÁÄ~$\Sigma$: $u_\Sigma$;
  44       \end{itemize}
  45     \item ÐÏÌÕËÏÌÅÞÎÙÅ ÔÅÒÍÙ: \metav $\srterm s$, $\srterm t$, \dots;
  46     \item ÓÉÎÔ.\ ÍÁÔÒÉÃÙ \todo{[ÒÁÚÍÅÒÁ]} $m \times n$:
  47       \metav $\smatr{s}{m}{n}$, $\smatr tmn$, \dots;
  48     \item ÍÁÔÒÉÞÎÙÅ ÔÅÒÍÙ \todo{[ÒÁÚÍÅÒÁ]} $m \times n$:
  49       \metav $\matrt{s}{m}{n}$, $\matrt tmn$, \dots;
  50     \item Á×ÔÏÍÁÔÙ\footnote{×ÓÌÅÄ ÚÁ ÛËÁÌÁÍÉ ëÒÉÐËÅ}:
  51       \metav $\autom A$, $\autom B$, \dots;
  52     \item ÓÈÅÍÙ: ;
  53     \end{itemize}
  54   \item ÉÎÄÉ×ÉÄÎÙÅ ÐÅÒÅÍÅÎÎÙÅ (ÐÏ ÜÌÅÍÅÎÔÁÍ ÁÌÇÅÂÒ ëÌÉÎÉ):  $x$, $y$, \dots;
  55   \item Ó×ÑÚËÉ × ÆÏÒÍÕÌÁÈ [ËÕÄÁ ×ÓÔÁ×ÉÔØ??]: $\implic$, $\equivc$;
  56   \item ÆÏÒÍÕÌÙ: $\phi$, $\psi$, \dots;
  57   \end{itemize}
  58   [ÅÝ£?]
  59 \item[íÎÏÖÅÓÔ×Á ÓÉÎÔÁËÓÉÞÅÓËÉÈ ÏÂßÅËÔÏ×] \mbox{}
  60   \begin{itemize}
  61   \item  ÍÎÏÖÅÓÔ×Á ÔÅÒÍÏ×: \metav \Terms, \dots;
  62   \item ÍÎÏÖÅÓÔ×Á ÐÒÏÇÒÁÍÍ:
  63     \begin{itemize}
  64     \item <<ÌÉÎÅÊÎÏ>> ÚÁÐÉÓÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ\T ÒÅÇÕÌÑÒÎÙÅ ×ÙÒÁÖÅÎÉÑ:
  65       \begin{itemize}
  66       \item ÎÁÄ $\Sigma$: $\RExp_{\Sigma}$;
  67       \item ÎÁÄ $\Sigma$, $T$: $\RExp_{\Sigma,T}$;
  68       \end{itemize}
  69     \item ÐÒÅÄÓÔÁ×ÌÅÎÉÑ ÐÒÏÇÒÁÍÍ × ×ÉÄÅ ÇÒÁÆÏ×:
  70       \begin{itemize}
  71       \item ËÏÎÅÞÎÙÅ Á×ÔÏÍÁÔÙ ÎÁÄ $\Sigma$:
  72         ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ\T $\NFA_{\Sigma}$, ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ\T $\DFA_{\Sigma}$;
  73       \item ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÅ ÓÈÅÍÙ  ÎÁÄ $\Sigma$, $T$:
  74         ÎÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ\T $\NPS_{\Sigma,T}$, ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ\T
  75         $\DPS_{\Sigma,T}$;
  76       \end{itemize}
  77     \end{itemize}
  78   \item ÍÎÏÖÅÓÔ×Á ÆÏÒÍÕÌ (= ÔÅÏÒÉÉ): \metav $\Phi$, \dots,
  79     \begin{itemize}
  80     \item ÍÎÏÖÅÓÔ×Á ÒÁ×ÅÎÓÔ× ÔÅÒÍÏ×: \metav $E$, \dots;
  81     \item ÜË×ÁÃÉÏÎÁÌØÎÁÑ ÔÅÏÒÉÑ ËÌÁÓÓÁ~$\class C$: $\EquaOf\class C$;
  82     \item (ÕÎÉ×ÅÒÓÁÌØÎÁÑ) Horn-ÔÅÏÒÉÑ ËÌÁÓÓÁ~$\class C$: $\HornOf\class C$;
  83     \end{itemize}
  84   \end{itemize}
  85 \item[ëÌÁÓÓÙ ÔÅÏÒÉÊ] \mbox{}
  86   \begin{itemize}
  87   \item \Equa, \Commut, \Monot, \Shifts,
  88   \item \Horn, $\Horn(\thclass c)$,
  89   \end{itemize}
  90   \metav $\thclass c$
  91 \item[üÌÅÍÅÎÔÙ ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÓÔÒÕËÔÕÒ] \mbox{}
  92   \begin{itemize}
  93   \item ÎÁÔÕÒÁÌØÎÙÅ ÞÉÓÌÁ: 0, 1, \dots, \metav $k$, $n$, $m$, \dots;
  94   \item ÓÔÒÏËÉ: ÐÕÓÔÁÑ ÓÔÒÏËÁ $\eStr$; \metav $x$, $y$, $z$, \dots,
  95   $\sigma$, \dots;
  96   \item ÏÔÎÏÛÅÎÉÑ: ÔÏÖÄÅÓÔ×ÅÎÎÏÅ ÏÔÎÏÛÅÎÉÅ $\id_U$ ÎÁ~$U$; \metav S,
  97     T, \dots
  98   \end{itemize}
  99 \item[íÏÄÅÌÉ, ÁÌÇÅÂÒÁÉÞÅÓËÉÅ ÓÔÒÕËÔÕÒÙ] \mbox{}
 100   \begin{itemize}
 101   \item ÍÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ: $\bbN$ (ÓÏ ÓÔÁÎÄÁÒÔÎÙÍÉ
 102     ÏÐÅÒÁÃÉÑÍÉ);
 103   \item ÍÎÏÖÅÓÔ×Ï ÃÅÌÙÈ ÞÉÓÅÌ: $\bbZ$ (ÓÏ ÓÔÁÎÄÁÒÔÎÙÍÉ
 104     ÏÐÅÒÁÃÉÑÍÉ);
 105 %%   \item ÍÎÏÖÅÓÔ×Ï ÄÅÊÓÔ×ÉÔÅÌØÎÙÈ ÞÉÓÅÌ: $\bbR$ (ÓÏ ÓÔÁÎÄÁÒÔÎÙÍÉ
 106 %%     ÏÐÅÒÁÃÉÑÍÉ);
 107   \item ÍÏÎÏÉÄÙ: \metav $\mo M$, \dots;
 108     \begin{itemize}
 109     \item ÍÏÎÏÉÄ ÓÔÒÏË ÎÁÄ $\Sigma$ (= Ó×ÏÂÏÄÎÙÊ ÍÏÎÏÉÄ ÎÁÄ~$\Sigma$):
 110       $\Strs(\Sigma)$ (Á ÔÁËÖÅ $\Sigma^*$);
 111     \end{itemize}
 112   \item ÁÌÇÅÂÒÙ ëÌÉÎÉ: \metav $\ka K$, \dots;
 113     \begin{itemize}
 114     \item ÓÅÍÅÊÓÔ×Ï ÒÅÇÕÌÑÒÎÙÈ ÍÎÏÖÅÓÔ× ÓÔÒÏË ÎÁÄ $\Sigma$:
 115       $\Reg_{\Sigma}$;
 116     \item ÒÅÌÑÃÉÏÎÎÁÑ ÁÌÇÅÂÒÁ ÎÁ~$U$: $\Rels(U)$ [??].
 117     \end{itemize}
 118   \item ÂÕÌÅ×Ù ÁÌÇÅÂÒÙ: \metav $\ba B$, \dots;
 119   \item ÁÌÇÅÂÒÙ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ: \metav $\ka T$, \dots;
 120 %%     \begin{itemize}
 121 %% %%     \item ÓÅÍÅÊÓÔ×Ï ÒÅÇÕÌÑÒÎÙÈ ÍÎÏÖÅÓÔ× ÓÔÒÏË ÎÁÄ $\Sigma$:
 122 %% %%       $\Reg_{\Sigma}$;
 123 %% %%     \item ÒÅÌÑÃÉÏÎÎÁÑ ÁÌÇÅÂÒÁ ÎÁ~$U$: $\Rels(U)$ [??].
 124 %%     \end{itemize}
 125   \end{itemize}
 126 \item[ïÔÏÂÒÁÖÅÎÉÑ × ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÓÔÒÕËÔÕÒÁÈ] \mbox{}
 127   \begin{itemize}
 128   \item ÇÏÍÏÍÏÒÆÉÚÍÙ ÁÌÇÅÂÒ ëÌÉÎÉ: \mbox{}
 129     \begin{itemize}
 130     \item ÉÎÔÅÒÐÒÅÔÁÃÉÉ: \metav $I\colon \RExp_{?,?} \to \ka K$,
 131     \dots;
 132     \begin{itemize}
 133     \item ËÁÎÏÎÉÞÅÓËÁÑ ÉÎÔÅÒÐÒÅÔÁÃÉÑ: $R_{\Sigma}\colon \RExp_{\Sigma} \to
 134       \Reg_{\Sigma}$;
 135     \item [??]: $\Ext\colon 2^{\Trs(\kf F)} \to \Rels(Q_{\kf F})$;
 136     \end{itemize}
 137     \end{itemize}
 138   \end{itemize}
 139 \item[ëÌÁÓÓÙ ÁÌÇÅÂÒÁÉÞÅÓËÉÈ ÓÔÒÕËÔÕÒ (ÍÏÄÅÌÅÊ),
 140   ËÁÔÅÇÏÒÉÉ]\footnote{ðÅÒÅÞÉÓÌÅÎÎÙÅ ÚÄÅÓØ ÉÍÅÎÁ ËÁÔÅÇÏÒÉÊ (ÍÅÔÁËÏÎÓÔÁÎÔÙ)
 141   ÍÙ × ÔÅËÓÔÅ ÉÓÐÏÌØÚÕÅÍ ÅÝ£ É ËÁË ËÒÁÔËÏÅ ÏÂÏÚÎÁÞÅÎÉÅ ÔÉÐÁ ÁÌÇÅÂÒ,
 142   ÎÁÐÒÉÍÅÒ, ÔÁË: <<ÌÀÂÁÑ \KA{}>> ÚÎÁÞÉÔ  <<ÌÀÂÁÑ ÁÌÇÅÂÒÁ ëÌÉÎÉ>>.}
 143   \mbox{}
 144   \begin{itemize}
 145   \item ÍÏÎÏÉÄÙ\footnote{ÅÓÌÉ ÒÅÞØ Ï ËÁÔÅÇÏÒÉÉ\T ÔÏ ÓÌÅÄÕÅÔ ÞÉÔÁÔØ \emph{ÍÏÎÏÉÄÙ É ÇÏÍÏÍÏÒÆÉÚÍÙ
 146   ÍÏÎÏÉÄÏ×}; ÁÎÁÌÏÇÉÞÎÏ É × ÄÒÕÇÉÈ ÓÌÕÞÁÑÈ}: $\Mon$;
 147   \item ÐÏÌÕËÏÌØÃÁ: $\Sr$;
 148   \item ÉÄÅÍÐÏÔÅÎÔÎÙÅ ÐÏÌÕËÏÌØÃÁ: $\ISr$;
 149   \item ÁÌÇÅÂÒÙ ëÌÉÎÉ: $\KA$;
 150   \item *\d ÎÅÐÒÅÒÙ×ÎÙÅ ÁÌÇÅÂÒÙ ëÌÉÎÉ: $\KAc$;
 151   \item ÒÅÌÑÃÉÏÎÎÙÅ ÁÌÇÅÂÒÙ ëÌÉÎÉ: $\RKA$;
 152   \item ÁÌÇÅÂÒÙ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ: $\KAT$;
 153   \item *\d ÎÅÐÒÅÒÙ×ÎÙÅ ÁÌÇÅÂÒÙ ëÌÉÎÉ Ó ÔÅÓÔÁÍÉ: $\KATc$;
 154   \end{itemize}
 155   \metav $\class C$, \dots;
 156 \item[æÕÎËÔÏÒÙ] \mbox{}
 157   \begin{itemize}
 158   \item $\REG\colon \text{ÉÚ $\Mon$ × $\KAc$}$ \cite{KA-complexity};
 159   \end{itemize}
 160 \item[ïÂßÅËÔÙ, ÌÅÖÁÝÉÅ × ÏÓÎÏ×Å ÄÒÕÇÉÈ ËÏÎÓÔÒÕËÃÉÊ] \mbox{}
 161   \begin{itemize}
 162   \item ËÏÎÅÞÎÙÅ ÁÌÆÁ×ÉÔÙ (ÎÁÐÒÉÍÅÒ, ÂÕË× ÄÌÑ ÐÏÓÔÒÏÅÎÉÑ ÓÔÒÏË): \metav $\Sigma$;
 163   \item ÍÎÏÖÅÓÔ×Á: ÐÕÓÔÏÅ $\emptyset$; \metav $X$, $Y$, $Z$, \dots;
 164   \item ÍÎÏÖÅÓÔ×Ï ÐÏÄÍÎÏÖÅÓÔ× ÍÎÏÖÅÓÔ×Á~$U$: $2^U$;
 165   \item ÍÎÏÖÅÓÔ×Ï ÏÔÎÏÛÅÎÉÊ ÎÁ~$U$: $2^{U \times U} \eqdef \Rels(U)$;
 166   \item ÛËÁÌÙ ëÒÉÐËÅ: \metav $\kframe F$, $\kframe E$, \dots~--- ÄÌÑ
 167   ÐÏÓÔÒÏÅÎÉÑ ÒÅÌÑÃÉÏÎÎÙÈ É ÔÒÁÓÓÏ×ÙÈ ÍÏÄÅÌÅÊ;
 168   \end{itemize}
 169 \item[ðÒÏÞÉÅ] \mbox{}
 170   \begin{itemize}
 171   \item $\equivdef$, $\eqdef$
 172   \end{itemize}
 173 \end{description}
 174
 175 %% \subsection{óÔÒÏÅÎÉÅ}
 176
 177 %% ûËÁÌÙ ëÒÉÐËÅ: $\fr F = (Q_{\fr F}, m_{\fr F})$.
 178
 179 %% á×ÔÏÍÁÔÙ: $\autom A = (Q_{\au A}, I_{\au A}, F_{\au A}, m_{\au A})$.
 180
 181 %% $\REG \Sigma^* \eqdef \Reg_{\Sigma}$
 182
 183 %% \subsection{ðÒÏÉÓÈÏÖÄÅÎÉÅ}
 184
 185 %%% Local Variables:
 186 %%% mode: latex
 187 %%% TeX-master: "main"
 188 %%% End: