% file transducers.tex
% originally appeared in late 1980s - early 1990s
% preparation for publication (by Yu. Pritykin) started 25.05.2007
% last update by K. Gorbunov 08.05.2008

\documentclass[12pt]{article}

\usepackage{amsmath, amssymb}
\usepackage{fullpage}
\usepackage{amsthm}

\newtheorem{theorem}{Теорема}%[section]
\newtheorem{lemma}{Лемма}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\theoremstyle{definition}
\newtheorem{remark}{Замечание}
\newtheorem{question}{Вопрос}
\newtheorem{definition}{Определение}
\renewcommand{\proofname}{Доказательство}
\renewcommand{\abstractname}{Аннотация}
\renewcommand{\refname}{Литература}


\newcommand{\вх}{\mathop{\it вх}\nolimits}
\newcommand{\вых}{\mathop{\it вых}\nolimits}
\newcommand{\poly}{\mathop{\rm poly}\nolimits}
\newcommand{\A}{{\frak A}}
\newcommand{\B}{{\frak B}}

%\input amssym.def

\title{Алгоритмические аспекты декомпозиции и эквивалентности
конечнозначных преобразователей}

\author{К.~Ю.~Горбунов\thanks{Институт проблем передачи информации
им. А.~А.~Харкевича РАН; e-mail: gorbunov@iitp.ru}, Ан.~А.~Мучник}

\begin{document}

\maketitle

\section{Введение}

В настоящей работе исследуются алгоритмические вопросы декомпозиции
конечнозначного преобразователя в объединение однозначных и
вложенности произвольного преобразователя в конечнозначный. Эти
вопросы изучались А.~Вебером в работах \cite{Web-diss87},
\cite{Web-man87}, \cite{Web-man89}, \cite{Web-man96}. Он доказал
полиномиальную разрешимость вопроса о конечнозначности преобразователя,
возможность декомпозиции конечнозначного преобразователя 
в объединение однозначных, предложил алгоритм проверки вложенности
произвольного преобразователя в конечнозначный. Мы предлагаем
более простые конструкции, частично улучшающие оценки А.~Вебера.
Полученные в результате декомпозиции однозначные преобразователи
у нас имеют размер одна экспонента от $\poly(n)$, где $n$~---
размер данного конечнозначного преобразователя; проверка вложенности
произвольного преобразователя в конечнозначный производится на зоне
одна экспонента (у А.~Вебера соответствующие оценки равны двум
экспонентам). С другой стороны в конструкции А.~Вебера из 
\cite{Web-man96} число однозначных преобразователей равно 
значности данного конечнозначного преобразователя, что не следует
из нашей конструкции. Таким образом, в каждой конструкции
есть свои преимущества. Отметим также работу \cite{Sakar-Souza},
авторы которой другим способом (независимо от авторов настоящей
работы) сократили размер однозначных преобразователей до
одной экспоненты.

Напомним, что конечным недетерминированным  преобразователем $\A$
называется пятерка $\langle A,Q,Q_{0},F,\delta\rangle$, где $A$~---
конечный  алфавит, $Q$~--- конечное множество состояний,
$Q_{0}\subseteq Q$~--- множество начальных  состояний, $F \subseteq
Q$~--- множество заключительных состояний, $\delta$~--- множество
переходов. Каждый переход~--- это  четверка $\langle
q_{1},a,v,q_{2}\rangle$. Здесь $q_{1}$~--- состояние до перехода,
$q_{2}$~---  состояние  после перехода, $a\in A\bigcup\{\Lambda\}$
($\Lambda$~--- пустое слово)~--- вход перехода, $v\in A^{*}$~---
выход перехода. Будем  представлять $\A$  ориентированным  графом,
вершины которого являются состояниями, а ребра~--- переходами.
Каждое ребро  помечено входом и выходом соответствующего  перехода.
Путями в этом  графе будем называть ориентированные пути. Слово,
полученное конкатенацией входов вдоль некоторого пути $l$, назовем
входом пути $l$ (обозначение: $\вх(l)$), а конкатенацией выходов~---
выходом  пути $l$ (обозначение: $\вых(l)$). Путь, начинающийся в
начальном состоянии и заканчивающийся в заключительном, будем
называть   допускающим. Графиком $\Gamma(\A)$ преобразователя $\A$
назовем множество пар $\langle u,v\rangle$ таких, что $u = \вх(l)$,
$v = \вых(l)$ для некоторого допускающего пути $l$.  Будем говорить,
что преобразователь $\A_{1}$ вложен в преобразователь $\A_{2}$, если
$\Gamma(\A_{1})\subseteq \Gamma(\A_{2})$. Преобразователи $\A_{1}$ и
$\A_{2}$ назовем эквивалентными,  если
$\Gamma(\A_{1})=\Gamma(\A_{2})$. Размером $\A$ (обозначение: $|\A|$)
будем  называть  сумму  числа  его состояний, переходов  и длин  их
выходов. Очевидно, что по преобразователю $\A$ можно за
полиномиальное от $|\A|$  время построить эквивалентный ему
преобразователь, в котором через  любое состояние проходит хотя бы
один допускающий путь. Поэтому будем считать,  что все
рассматриваемые далее преобразователи обладают этим  свойством.
Основным для дальнейшего изложения будет следующее определение.

\begin{definition}
Преобразователь $\A$ называется \emph{конечнозначным}, если
существует константа $c$ такая, что для любого слова $u$ существует
не более $c$ различных слов $v$ таких, что $\langle u,v\rangle\in
\Gamma(\A)$. Минимальное такое $c$ называется значностью $\A$. Если
значность равна  1,  то $\A$  называется однозначным.
\end{definition}

Назовем преобразователь $\A$ редуцированным,  если  у  него  ровно
одно начальное и ровно одно конечное состояние,  и  все  переходы  с
пустым входом идут  из  начального  состояния  в  конечное.  А.~Вебер
доказал в \cite{Web-diss87} следующее утверждение.

\begin{lemma} \label{construct-reduced}% лемма 1
По преобразователю $\A$  можно  за  полиномиальное время либо
построить  эквивалентный  ему  редуцированный преобразователь, либо
констатировать бесконечнозначность~$\A$.
\end{lemma}
\begin{proof}
Добавив не более  двух  состояний  и  не  более $2|\A|$ переходов,
очевидным образом добьёмся, чтобы  в $\A$  было ровно одно начальное
состояние, из которого  переходы  только выходят,  и ровно одно
заключительное,  куда  переходы  только входят.  Далее, зададим на
состояниях $\A$ частичный  порядок~$R$: $q_1Rq_2$, если существует
путь из $q_{1}$ в $q_{2}$ с пустым входом. Предположим,  что $q_{1}$
и $q_{2}$ эквивалентны относительно этого порядка. Легко видеть, что
если  $\A$ конечнозначный, то любой путь из $q_{1}$ в $q_{2}$ с
пустым  входом должен иметь пустой выход. Очевидно, что проверка
последнего условия  для всех пар $\langle q_{1},q_{2}\rangle$
выполняется  за полиномиальное  время. Пусть это условие выполнено.
Каждый класс эквивалентных состояний естественным образом склеим  в
одно состояние.  Получим преобразователь $\A'$, который, очевидно,
эквивалентен $\A$. Пусть в $\A'$ есть не начальное и не
заключительное состояние $q$ такое, что существует переход  с пустым
входом, который входит в $q$  или выходит  из $q$. Для каждой пары
переходов $\langle q_{1},a_{1},v_{1},q\rangle$,$\langle
q,a_{2},v_{2},q_{2}\rangle$ такой,  что $a_{1} = \Lambda$  или
$a_{2} = \Lambda$, добавим переход $\langle
q_{1},a_{1}a_{2},v_{1}v_{2},q_{2}\rangle$. После этого, удалим все
переходы с пустым входом, входящие в $q$ и выходящие из $q$. Так как
в $\A'$  нет переходов вида $\langle q,\Lambda,v,q\rangle$, то
описанная процедура не изменяет  график преобразователя. Кроме того,
если до нее у некоторого  состояния $q'$ не было инцидентных ему
переходов с пустым входом, то и после нее их не будет. Поэтому, не
более чем за $|\A'|$ таких  операций мы получим требуемый
редуцированный преобразователь. Лемма~\ref{construct-reduced}
доказана.
\end{proof}


\section{Декомпозиция конечнозначных преобразователей}

Скажем, что  конечнозначный  преобразователь $\A$ \emph{разлагается в
декомпозицию} однозначных   преобразователей
${\A_{1},\A_{2},\ldots,\A_{k}}$,   если
${\Gamma(\A)=\bigcup\limits_{i=1}^{k}\Gamma(\A_{i})}$.  А.~Вебер
доказал  в \cite{Web-man87},  что  любой  конечнозначный
преобразователь  $\A$ размера $n$   можно   эффективно   разложить в
декомпозицию не более $\exp(\poly(n))$ однозначных преобразователей
за время $\exp(\exp(\poly(n)))$.  При  этом  размер каждого
однозначного преобразователя  не  более $\exp(\exp(\poly(n)))$.   Мы
предлагаем в следующей теореме более простой путь декомпозиции с
лучшей оценкой на время и размер компонент.

\begin{theorem} \label{transducer-decomposition} % теорема 1
Существует алгоритм, который по любому конечнозначному
преобразователю $\A$ размера $n$ находит его декомпозицию из не
более чем $k \leqslant \exp(\poly(n))$ однозначных преобразователей
$\A_1,\ldots,\A_k$ за время  не  более $\exp(\poly(n))$. Размер
каждого $\A_i$ не более $\exp(\poly(n))$.
\end{theorem}
\begin{proof}
Из утверждения леммы~\ref{construct-reduced} следует, что достаточно
рассмотреть случай, когда в $\A$ нет переходов с пустым входом. Если
$l$~--- путь в $\A$ со входом $u$ и $u'\subseteq u$ (т.~е. $u'$~---
начало $u$), то через $l(u')$ будем  обозначать начало  пути $l$
такое,  что $\вх(l(u'))=u'$.  Если $u=v_{1}v_{2}v_{3}$,  то  через
$l(v_{2})$ будем  обозначать   путь такой,   что конкатенация
$l(v_{1})l(v_{2})$ есть $l(v_{1}v_{2})$. Если $l_{1}$  и $l_{2}$
--- два  пути такие,  что $\вх(l_{1})=\вх(l_{2})=u$  и $u'\subseteq
u$, то  будем  обозначать через $d(l_{1},l_{2},u')$   число,
равное $|\вых(l_{1}(u'))|-|\вых(l_{2}(u'))|$. Сформулируем  критерий
конечнозначности  для  преобразователя   без переходов с пустым
входом.

\begin{theorem} \label{finite-value-characteristic} % теорема 2
Преобразователь $\A$ размера $n$  без  пустых  входов конечнозначен
тогда  и  только  тогда,  когда  для  любых  двух  его состояний
$s_{1}$, $s_{2}$ (не обязательно различных) и любых  трех путей
$p_{1}$, $p_{2}$, $p_{3}$ с одним и тем же входом $u$, таких что
$p_{1}$ начинается в $s_{1}$ и кончается в $s_{1}$, $p_{2}$
начинается в $s_{1}$, кончается в $s_{2}$, $p_{3}$ начинается  в
$s_{2}$ и кончается в $s_{2}$, выполняются следующие два условия:\\
(1) Если  $\вых(p_{1})\not=\Lambda$, то $\вых(p_{2})$    является
началом бесконечного слова $(\вых(p_{1}))^{\infty}$.\\
(2) Для любого $u'\subseteq u$ выполняется: $|d(p_{1},p_{2},u')|
\leqslant n^4$.
\end{theorem}

Сходный критерий сформулировал и доказал в \cite{Web-diss87}
А.~Вебер. Докажем необходимость сформулированного критерия.

Предположим, что условие (1) не выполняется. Пусть ${k>c}$, где
$c$~--- значность~$\A$. Рассмотрим множество
${\{p^{i-1}_{1}p_{2}p^{k-i}_{3}\mid i=1,\ldots,k\}}$ путей из
$s_{1}$ в $s_{2}$. Легко видеть, что все эти пути имеют один и тот
же вход $u^{k}$. Выбор $k$ гарантирует существование такого $j>0$, что
$(\вых(p_1))^j\вых(p_2) = \вых(p_2)(\вых(p_3))^j$. Отсюда
$(\вых(p_1))^{2j}\вых(p_2) =$\\ $(\вых(p_1))^j\вых(p_2)(\вых(p_3))^j
= \вых(p_2)(\вых(p_3))^j(\вых(p_3))^j = \вых(p_2)(\вых(p_3))^{2j}$,
и аналогично $(\вых(p_1))^{tj}\вых(p_2) = \вых(p_2)(\вых(p_3))^{tj}$
для любого $t$, откуда ясно, что $\вых(p_2)$~--- начало
$(\вых(p_1))^\infty$.

Докажем (2). Предположим, $|d(p_{1},p_{2},u')| > n^4$ для какого-то
$u' \subseteq u$. Пусть $\Lambda = u_0, u_1, u_2, \dots$~--- все
начала слова $u$. Заметим, что $|d(p_1, p_2, u_i) - d(p_1, p_2,
u_{i+1})| \leqslant n$ для любого $i$, при этом $d(p_1, p_2, u_0) =
0$, следовательно, среди $u_i$ найдётся хотя бы $n^3 + 1$ начал
$u_{i_k}$ с различными $d(p_1, p_2, u_{i_k})$. Каждому $u_{i_k}$
соответствует тройка состояний, в  которых кончаются пути
$p_{1}(u_{i_k})$, $p_{2}(u_{i_k})$, $p_{3}(u_{i_k})$. Возьмем  такие
$u_{i'}$  и $u_{i''}$ (${u_{i'}\subset u_{i''}}$), которым
соответствует одна и та же тройка. Таким  образом, $u =
v_{1}v_{2}v_{3}$,  где $v_{1} = u_{i'}$, $v_{1}v_{2} = u_{i''}$. По
построению $|\вых(p_{1}(v_{2}))| \ne |\вых(p_{2}(v_{2}))|$, так как
$d(p_1, p_2, v_1) = |\вых(p_1(v_1))| - |\вых(p_2(v_1))| \ne
|\вых(p_1(v_1))| + |\вых(p_1(v_2))| - |\вых(p_2(v_1))| - |\вых(p_2(v_2))| =
d(p_1, p_2, v_1v_2)$. Если ${|\вых(p_{1})|\not= |\вых(p_{3})|}$, то
длины выходов путей ${p^{i-1}_{1}p_{2}p^{k-i}_{3}}$,  очевидно,
попарно различны, что противоречит выбору $k$. Если
${|\вых(p_{1}(v_{1}))|+|\вых(p_{1}(v_{3}))|\not=
|\вых(p_{3}(v_{1}))|+|\вых(p_{3}(v_{3}))|}$, то такое же рассуждение
верно для путей ${[p_{1}(v_{1})p_{1}(v_{3})]^{i - 1}
p_{2}(v_{1})p_{2}(v_{3})[p_{3}(v_{1})p_{3}(v_{3})]^{k - i}}$. Иначе,
рассмотрим различные пути из $s_{1}$  в $s_{2}$  со  входом
${v_{1}v_{2}v_{3}v_{1}v_{2}v_{2}v_{3}\ldots v_{1}v_{2}^{k}v_{3}}$,
проходящие по $p_{1}$, $p_{2}$, $p_{3}$. Легко видеть, что длина
выхода  этих  путей монотонно зависит от того, какой блок
${v_{1}v_{2}^{i}v_{3}}$ приходится на путь $p_{2}$, что противоречит
выбору $k$.  Необходимость  критерия  доказана.

\medskip

При доказательстве теоремы~\ref{transducer-decomposition} будем
предполагать вместо конечнозначности $\A$  выполненность  данного
критерия.   Поскольку из   возможности декомпозиции преобразователя
следует его конечнозначность, то  будет доказана достаточность
критерия.

Продолжим доказательство теоремы~\ref{transducer-decomposition}.
Пусть $q_{1}$ и $q_{2}$~--- состояния $\A$. Скажем, что
$q_{1}\geqslant q_{2}$, если существует путь из $q_{1}$ в $q_{2}$.
Это отношение частичного  порядка  разбивает множество  состояний
$Q$  на   классы эквивалентных  состояний. Переход $\langle
q_{1},a,v,q_{2}\rangle$ будем   называть \emph{переходом в
состояниях}, если $q_{1}$ не эквивалентно $q_{2}$. Пусть $Q_{1}$ и
$Q_{2}$~--- подмножества $Q$. Скажем, что $Q_{2}$ достигается из
$Q_{1}$ на  слове $w$,  если существует множество $L$ путей из
$Q_{1}$ в $Q_{2}$ со входом $w$ такое,  что  для любого $q_{1}\in
Q_{1}$ существует путь из $L$, начинающийся в $q_{1}$, а для  любого
$q_{2}\in Q_{2}$ существует путь из $L$, кончающийся в $q_{2}$.
Скажем,  что $Q_{1}\geqslant Q_{2}$, если существует слово, на
котором $Q_{2}$ достигается  из $Q_{1}$. Очевидно, что введенное
отношение является отношением  частичного порядка  на
подмножествах~$Q$, разбивающим их на классы эквивалентных
подмножеств, и это отношение продолжает уже введённое на состояниях:
$q_{1}\geqslant q_{2}$ тогда и только тогда, когда $\{q_{1}\}
\geqslant \{q_{2}\}$. Легко видеть также, что по двум подмножествам
$Q_{1}$ и $Q_{2}$ можно за время $\exp(\poly(n))$ выяснить, 
выполняется ли $Q_{1}\geqslant Q_{2}$ (действительно, если
$Q_{2}$ достигается из $Q_{1}$ на некотором слове, то оно достигается 
из $Q_{1}$ и на слове длины не большей $n^{n}$).
Пусть есть слово $u$, и $u'\subseteq u$.
Множеством двусторонней достижимости $M_{u}(u')$ назовем множество
таких состояний $q$, для которых существует допускающий путь $l$
такой, что $\вх(l)=u$ и путь $l(u')$ кончается в $q$. Легко видеть,
что если $u_{1}\subseteq u_{2}\subseteq u$,  то
$M_{u}(u_{1})\geqslant M_{u}(u_{2})$. Пусть на допускающем пути $l$
есть переход $p$  и $l_{1}$  ---  начало $l$, кончающееся
непосредственно до $p$, а $l_{2}$ --- начало $l$, кончающееся  сразу
после $p$. Будем называть $p$ \emph{переходом во множествах}  на
$l$, если $M_{u}(u_{1})$ не эквивалентно $M_{u}(u_{2})$, где $u_{1}
= \вх(l_{1})$, $u_{2} = \вх(l_{2})$. Докажем две леммы.

\begin{lemma} \label{equivalent-states} % лемма 2
Пусть в $\A$ два состояния $q_{1}$ и $q_{2}$  эквивалентны. Тогда
для любых двух путей $l_{1}$ и $l_{2}$ из $q_{1}$ в $q_{2}$ таких,
что $\вх(l_{1}) = \вх(l_{2})$, выполняется: $\вых(l_{1}) =
\вых(l_{2})$. Для любого начала $u'$  слова $u = \вх(l_{1})$
выполняется: $|d(l_{1},l_{2},u')| \leqslant n^4$.
\end{lemma}
\begin{proof}
Обозначим: $w_{1} = \вых(l_{1})$, $w_{2} = \вых(l_{2})$.  В   силу
эквивалентности $q_{1}$  и $q_{2}$  существует  путь $l$  из $q_{2}$
в $q_1$.  Если $|w_1| = |w_2|$, применим условие (1), где $s_1 = s_2
= q_1$, $p_1 = l_1l$, $p_2 = p_3 = l_2l$. Получим, что $\вых(l_1l) =
\вых(l_{2}l)$,  откуда  следует $w_1 = w_2$. Пусть $|w_1| \ne
|w_2|$.  Будем считать, что ${|w_{1}|>0}$. Получаем противоречие  с
условием~(2), положив в нем $s_1 = s_2 = q_1$, $p_{1} =
(l_{1}l)^{k}$, $p_2 = p_3 = (l_2l)^k$  для $k > n^4$. Последнее
утверждение леммы следует из условия~(2).
Лемма~\ref{equivalent-states} доказана.
\end{proof}


Скажем, что два слова согласованы, если одно  из  них  является
началом другого.

\begin{lemma} \label{two-equivalent-sets} % лемма 3
Пусть $M_1$, $M_2$~--- произвольные эквивалентные относительно
отношения $\geqslant$ множества состояний, $q_1 \in M_1$, $q_2 \in
M_2$, $l'$~--- путь из $q_1$ в $q_2$ такой, что 
$M_2$ достигается из $M_1$ на слове $v = \вх(l')$ и  
$|\вых(l')| > n^4$. Тогда для любых двух путей $l_{1}$, $l_{2}$ из $q_{1}$ в
$q_{2}$ со входом $v = \вх(l')$ слова $\вых(l_{1})$ и $\вых(l_{2})$
согласованы, и для любого $v' \subseteq v$ выполняется:
$|d(l_1,l_2,v')| \leqslant 2n^4$.
\end{lemma}
\begin{proof}
Будем считать, что $q_{1}$ не эквивалентно $q_{2}$, иначе
утверждение леммы сразу следует  из леммы~\ref{equivalent-states}.
Из эквивалентности $M_{1}$ и $M_{2}$ следует, что $M_{1}$
достигается из $M_{2}$ на некотором слове $v_{1}$. Тогда $M_{1}$
достигается  из самого  себя  на слове $vv_{1}$. Поэтому существует
бесконечная последовательность состояний из $M_{1}$:
$q_{0},q_{-1},q_{-2}\ldots$ такая, что для любого $i\leqslant 0$
существует путь $\gamma_{i}$ из $q_{i}$ в $q_{i+1}$ со входом
$vv_{1}$. Зафиксируем  состояние $b_{1}=q_{i}=q_{j}$ для некоторых
$i<j\leqslant 1$. Получим замкнутый путь  из $b_{1}$  в $b_{1}$,
который обозначим  через $p$. Кроме того, существует бесконечная
последовательность состояний из $M_1$: $q_{3},q_{4},\ldots$ такая,
что  существует путь $\gamma_{2}$ из $q_{2}$ в $q_{3}$ со входом
$v_{1}$, и для любого $i\geqslant 3$ есть путь $\gamma_{i}$ из
$q_{i}$ в $q_{i+1}$ со входом $vv_{1}$.  Здесь $q_{i} \ne q_{j}$ для
всех $i\leqslant 1$, $j\geqslant 2$ в  силу неэквивалентности
$q_{1}$  и $q_{2}$. Зафиксировав $b_{2}=q_{i}=q_{j}$  для  некоторых
$3\leqslant i<j$, получим замкнутый путь из $b_{2}$ в $b_{2}$,
который  обозначим через $p'$. Путь из $b_{1}$ в $b_{2}$, состоящий
из трех отрезков~--- из $b_{1}$ в $q_{1}$ по путям $\gamma_{i}$
($i\leqslant 0$), из $q_{1}$ в $q_{2}$ по $l'$ и из $q_{2}$ в
$b_{2}$ по путям $\gamma_{i}$ ($i\geqslant 2$)~--- обозначим через
$\gamma$. Очевидно, $|\вх(p)| = kn_1$, $|\вх(\gamma)|=kn_{2}$,
$|\вх(p')|=kn_{3}$,  где $k=|vv_{1}|$, а $n_{1}$, $n_{2}$,
$n_{3}$~--- натуральные числа. Возьмем на $p$ состояние $s$ такое,
что путь, начинающийся в $s$, идущий все время по  циклу $p$  и
имеющий длину $k(n_{1}n_{2}n_{3} - n_{2})$, оканчивается  в $b_{1}$,
обозначим этот путь через $\gamma'$. Рассмотрим три пути: путь
$p_{1}$ из $s$ в $s$,  совершающий $n_{2}n_{3}$ оборотов по циклу
$p$, путь $p_{2}$ из $s$ в $b_{2}$, равный $\gamma'\gamma$ и путь
$p_{3}$ из $b_{2}$ в $b_{2}$, совершающий $n_{1}n_{2}$ оборотов по
циклу $p'$. Очевидно, что $\вх(p_{1}) = \вх(p_{2}) = \вх(p_{3})$.
Так как $|\вых(p_{2})|\geqslant |\вых(l')| > n^4$,   то   по
условию~(2) $|\вых(p_{1})| > 0$. Путь $p_{2}$ можно провести по
$l_{1}$ или $l_{2}$  вместо $l'$. По условию~(1) выходы любого из
этих  трех возможных  вариантов пути $p_{2}$ являются началами слова
$(\вых(p_{1}))^{\infty}$. Отсюда, в частности, следует, что слова
$\вых(l_{1})$ и $\вых(l_{2})$ согласованы.  Из условия~(2) легко
видеть,   что $|d(l_{1},l_{2},v')|\leqslant 2n^4$.
Лемма~\ref{two-equivalent-sets} доказана.
\end{proof}

\begin{corollary} \label{two-prefixes}
Пусть $l$~--- допускающий путь в $\A$, $u_{1}$, $u_{2}$~---  два
начала слова $u = \вх(l)$, $u_{1} \subseteq u_{2}$, $M_{u}(u_{1})$
эквивалентно $M_{u}(u_{2})$. Обозначим через $l'$ отрезок пути $l$,
дополняющий $l(u_{1})$ до $l(u_{2})$,  а  через $q_{1}$  и
$q_{2}$~--- соответственно   начальное   и   конечное состояния
$l'$. Пусть ${|\вых(l')| > n^4}$. Тогда для любых двух путей
$l_{1}$, $l_{2}$ из $q_{1}$ в $q_{2}$ со  входом $v = \вх(l')$ слова
$\вых(l_{1})$ и $\вых(l_{2})$  согласованы,  и  для  любого
${v'\subseteq v}$ выполняется: $|d(l_{1},l_{2},v')| \leqslant 2n^4$.
\end{corollary}


Пусть $l$~--- допускающий путь в $\A$.  Каждому  началу $l'$  пути
$l$ соответствует пара $(q,M)$, где $q$ --- состояние, в котором
оканчивается $l'$, а $M = M_{u}(u')$,  где $u = \вх(l)$, $u' =
\вх(l')$. Будем  отмечать  пары, соответствующие   некоторым началам
пути $l$.   Отметим    пары, соответствующие пустому началу и всему
пути. Для каждого перехода  в состояниях на $l$, который не является
переходом во множествах  на $l$, возьмем ближайшие  слева  и справа
на $l$   (мы   представляем $l$ направленным слева направо) переходы
во множествах (если они  есть). Для  каждого  из  этих двух
переходов   отметим   по   две   пары, соответствующие  началам пути
$l$,  кончающимся  непосредственно  до перехода и сразу после него.
Для  каждого  перехода  в  состояниях, который является  и переходом
во  множествах  на $l$,  отметим  две указанные пары,
соответствующие этому переходу.  Обозначим  через $D$
последовательность всех отмеченных  пар,  расположенных  в порядке
возрастания соответствующих им начал. Легко видеть,  что для любых
двух соседних в $D$  пар  $(q_{1},M_{1})$, $(q_{2},M_{2})$ возможны
следующие  три случая:

1) $q_{1}$ эквивалентно $q_{2}$;

2) начала $l$, соответствующие этим парам,  различаются  на  один
переход пути $l$, который является  переходом и в состояниях, и во
множествах;

3) $M_{1}$ эквивалентно $M_{2}$, $q_{1}$ не эквивалентно $q_{2}$.

Если имеет место $i$-й  случай,  будем  говорить,  что  отрезок
$[(q_{1},M_{1}),\,(q_{2},M_{2})]$ имеет $i$-й  тип.  В  случае~2
припишем  этому отрезку  слово,  являющееся   выходом
соответствующего   перехода. В случае~3 пусть $l'$~---  участок  пути $l$ между  положениями $(q_{1},M_{1})$
и $(q_{2},M_{2})$, $v = \вх(l')$, $w = \вых(l')$. Припишем
данному отрезку число $k$, равное разности  между $|w|$  и
минимальной  длиной выхода среди выходов всех  путей  из $q_{1}$  в
$q_{2}$  со  входом $v$. Из утверждения следствия~\ref{two-prefixes}
следует, что $k \leqslant 2n^4$.

Последовательность $D$   с   приписанной   отрезкам   указанной
информацией будем называть диаграммой  пути $l$  и  обозначать  через
$D(l)$. Информация включает также номер  типа  каждого  отрезка.

\begin{lemma} \label{two-accepting-paths} % лемма 4
Пусть $l_1$ и $l_2$~--- допускающие  пути  в $\A$ такие, что
$\вх(l_{1}) = \вх(l_{2})$ и $D(l_{1})$ совпадает с $D(l_{2})$. Тогда
$\вых(l_{1}) = \вых(l_{2})$.
\end{lemma}
\begin{proof}
Очевидно,  что  любая  не   крайняя   пара   из диаграммы
соответствует положению пути непосредственно до или  после перехода
во множествах, причем из диаграммы  видно,  какой  из  этих случаев
имеет место. Любое множество двусторонней достижимости $M$,  о
котором   известно, что оно соответствует положению пути
непосредственно слева (справа) от перехода во множествах, однозначно
определяет начало $u'$ слова $u=\вх(l_{1})$ такое, что
$M=M_{u}(u')$. Поэтому пары из диаграммы однозначно разбивают  вход
$u$  на соответствующие участки, и достаточно доказать равенство
выходов $l_{1}$ и $l_{2}$  на  каждом участке  входа.  Если  отрезок
диаграммы  имеет  первый   тип,   то совпадение выходов  на
соответствующем  участке  входа  следует  из
леммы~\ref{equivalent-states}. При отрезке второго типа выход 
указан непосредственно в диаграмме. На
отрезке третьего типа выходы $l_{1}$  и $l_{2}$
согласованы  по  лемме~\ref{two-equivalent-sets}, поэтому одинаковая
разность  с  одним  и  тем  же  числом обеспечивает  их совпадение.
Лемма~\ref{two-accepting-paths} доказана.
\end{proof}

Так как все диаграммы  имеют  полиномиальную  длину (длина диаграммы
$\leqslant 4\cdot$[количество переходов в состояниях]$\leqslant 4n$)
и каждый член диаграммы (как и информация, приписанная отрезку) 
может принимать не более $\exp(\poly(n))$ значений, то всего возможных диаграмм не более $\exp(\poly(n))$.
Поэтому, для доказательства теоремы~\ref{transducer-decomposition}
достаточно для каждой возможной диаграммы $D$ построить за
экспоненциальное время преобразователь $\A(D)$, график которого
состоит  из  тех  и только тех  элементов $\Gamma(\A)$,  которые
реализуются  путями  с диаграммой $D$. По
лемме~\ref{two-accepting-paths} преобразователь $\A(D)$ будет
однозначным.

Множеством  левосторонней  достижимости  для  слова $u$  назовем
множество таких состояний $q$,  что  существует  путь  из  начального
состояния в $q$ со входом $u$. Если  дана  диаграмма $D$,  то
множеством локальной двусторонней  достижимости  на  отрезке
$[(q_{1},M_{1}),\,(q_{2},M_{2})]$ диаграммы $D$ для входа $u$ и его
начала $u'$  назовем  множество  таких состояний $q$, что существует
путь $l$ из $q_{1}$ в $q_{2}$ такой, что  $\вх(l)=u$  и путь $l(u')$
кончается  в $q$.  Множеством  локальной   левосторонней достижимости
на этом отрезке для входа $u$  назовем  множество  таких состояний
$q$, что существует путь из $q_{1}$ в $q$ со входом $u$. Будем
считать, что в первой  паре  $(q,M)$  диаграммы $D$  множество $M$
является подмножеством множества начальных состояний, а в  последней
паре --- подмножеством множества заключительных  состояний,
поскольку иначе, очевидно, не существует пути с диаграммой $D$.

Опишем $\A(D)$. Состояниями $\A(D)$ будут  следующие  совокупности:
$\langle Q_{1},Q_{2},q,L\rangle$.  Здесь  в $Q_{1}$   будет
вычисляться множество  левосторонней  достижимости  для  прочтенного
начала входа, в $Q_{2}$~--- множество двусторонней достижимости  для
всего входа и текущего начала входа, в $q \in Q_{2}$~---  текущее
состояние угадываемого пути  с  читаемым входом  и  диаграммой $D$.
Очевидно, что множество $Q_{2}$  однозначно определяет текущий
отрезок $[(q_{1},M_{1}),\,(q_{2},M_{2})]$ диаграммы $D$ первого или
третьего типа такой, что $M_{1}\geqslant Q_{2}\geqslant M_{2}$, если
он существует. $L$ непусто тогда и только тогда, когда этот отрезок
существует и имеет  третий тип. В этом случае 
$L$~--- совокупность $\langle
Q'_{1},Q'_{2},P\rangle$. Здесь в $Q'_{1}$  будет  вычисляться
множество локальной левосторонней достижимости на  текущем  отрезке,
в $Q'_{2}$~--- множество локальной двусторонней достижимости, $q\in
Q'_{2}\subseteq Q'_{1}$.
$P$~--- это множество пар $\langle q',m\rangle$ по одной для каждого
состояния $q' \in Q'_2$, где $0\leqslant m\leqslant 2n^4$, и еще
одна текущая пара с $q'$, равным  текущему состоянию $q$. Обозначим
через $u_{t}$ отрезок входа, прочтенный к текущему моменту в $\A(D)$
на участке, где $M_{1}\geqslant Q_{2}\geqslant M_{2}$. В текущей
паре $\langle q,m\rangle$ в $m$ будет вычисляться разность между
длиной выхода угадываемого в $\A$  пути на отрезке входа $u_{t}$ и
минимальной длиной выхода среди  выходов  всех путей со входом
$u_{t}$ из $q_{1}$ во множество $Q'_{2}$.  Чтобы  следить  за этой
минимальной длиной, в каждой  не  текущей  паре $\langle
q',m\rangle$  в $m$ будет вычисляться разность между минимальной
длиной выхода  среди выходов всех путей из $q_{1}$ в $q'$ со входом
$u_{t}$ и минимальной длиной выхода среди выходов всех путей со
входом $u_{t}$ из $q_{1}$ во множество~$Q'_{2}$.  Начальными
состояниями $\A(D)$ являются такие, в которых $Q_{1}$~--- множество
начальных состояний, $Q_{2}$ и $q$~--- те, что указаны в начале $D$;
если первый  отрезок диаграммы имеет третий тип, то $L$ непусто, 
$Q'_{1} = Q'_{2} =
\{q\}$ и во  всех  парах $m = 0$.  Текущая  пара: $\langle
q,0\rangle$. Заключительными состояниями $\A(D)$ являются такие, где
$Q_{2}$ и $q$~--- те, которые указаны  в  конце $D$,  и множество
$Q_{1}\setminus Q_{2}$ не  содержит заключительных состояний: если
последний  отрезок диаграммы  имеет третий  тип, то $L$  непусто,
$Q'_{2} = \{q\}$ и в
текущей паре $m$ равно числу, указанному в $D$.

Опишем переходы $\A(D)$. Скажем, что состояние $q''$  из  $\A$
является последователем состояния $q'$ по букве $a$, если есть
переход из $q'$ в $q''$ со входом $a$. Переход из состояния $s_{1}$
в  состояние $s_{2}$  со  входной буквой $a$ и выходным словом $v$
существует тогда и только тогда,  когда выполнены все следующие
условия.

1)~$Q_{1}(s_{2})$ (так обозначаем компоненту $Q_{1}$ в  состоянии
$s_{2}$)  есть множество всех  последователей  состояний  из
$Q_{1}(s_{1})$  по $a$.  Таким образом, компонента $Q_{1}$
вычисляется детерминированно.

2)~Существует переход в $\A$ из $q(s_{1})$  в $q(s_{2})$  со  входом
$a$  и выходом $v$.

3)~Для каждого состояния $q'$ из $Q_{2}(s_{1})$  хотя  бы  один  из
его последователей по $a$ принадлежит $Q_{2}(s_{2})$. Для каждого
состояния $q'$  из $Q_{1}(s_{1})\setminus Q_{2}(s_{1})$ все его
последователи по $a$ не принадлежат $Q_{2}(s_{2})$.

4)~В $D$ существует отрезок
$R\colon\,[(q_{1},M_{1}),\,(q_{2},M_{2})]$ либо типа 1 или 3 такой,
что $M_{1}\geqslant Q_{2}(s_{1})\geqslant M_{2}$, $M_{1}\geqslant
Q_{2}(s_{2})\geqslant M_{2}$,  (очевидно,  такой  отрезок может быть
лишь один), либо типа 2 такой, что $M_{1}=Q_{2}(s_{1})$, $M_{2} =
Q_{2}(s_{2})$, $q_{1}=q(s_{1})$, $q_{2}=q(s_{2})$, $v$  равно
выходу,  указанному при $R$.  В  этом последнем случае, если
предыдущий  отрезок $D$ (до  $(q_{1},M_{1})$)  имеет третий тип, то
должно выполняться: $Q'_{2}(s_{1})=\{q_{1}\}$, $m$ в  текущей  паре
в $s_{1}$ равно указанному  в $D$.  Аналогично,
если последующий отрезок $D$ (от $(q_{2},M_{2})$)  имеет  третий
тип,  то должны  выполняться очевидные начальные условия. В случае,
если $R$ третьего  типа,  то должны выполняться перечисленные в
следующем абзаце условия.

Множество $Q'_{1}(s_{2})$ состоит из всех последователей состояний
из $Q'_{1}(s_{1})$ по $a$. Для каждого состояния $q'$ из
$Q'_{2}(s_{1})$ хотя бы  один  из  его  последователей  по $a$
принадлежит $Q'_{2}(s_{2})$. Для каждого состояния $q'$  из
$Q'_{1}(s_{1})\setminus Q'_{2}(s_{1})$  все его последователи по $a$ не
принадлежат $Q'_{2}(s_{2})$.
$P(s_{2})$ получается по следующим правилам. Сначала  сопоставим
каждому $q'\in Q'_{2}(s_{2})$ минимальное число среди всех сумм $m +
|w|$  таких,  что  для некоторого $q''$ $\langle q'',m\rangle\in
P(s_{1})$ и существует переход из $q''$ в $q'$ со входом $a$ и
выходом $w$. Среди всех сопоставленных чисел  возьмем  минимальное
число $k$. Если $k \ne 0$, уменьшим  все  эти  числа  на $k$.  При
этом  все получившиеся  числа  не  превышают  $2n^4$.  Эти  числа в
парах   с соответствующими им состояниями  войдут  в $P(s_{2})$. В
текущей  паре $m(s_{2}) = m(s_{1}) + |v| - k\leqslant 2n^4$.

Очевидно, что если в $\A$ есть допускающий путь $l$ с диаграммой $D$,
то в $\A(D)$ существует допускающий путь $l'$  такой,  что
$\вх(l)=\вх(l')$, $\вых(l)=\вых(l')$. Пусть, наоборот, в $\A(D)$ есть
допускающий  путь $l'$. Покажем,  что  соответствующий  ему угаданный
путь $l$  в  $\A$  имеет диаграмму $D$.  Компонента $Q_{1}$
вычисляется  верно,   так   как   она детерминированна. Покажем, что
$Q_{2}$ тоже вычисляется верно. Пусть  это не так. Пусть $Q_{2}$ в
некоторый момент имеет лишнее состояние.  Тогда в силу того, что
элементы $Q_{2}$ имеют хотя бы одного последователя в $Q_{2}$ на
каждом  шагу,  в  конце $Q_{2}$  будет  содержать незаключительное
состояние, что противоречит тому, что путь $l'$ допускающий. Пусть
$Q_{2}$ не содержит некоторого состояния, которое на  самом  деле
входит  в множество  двусторонней  достижимости. Так  как  все
последователи состояний  из $Q_{1}\setminus Q_{2}$  не принадлежат
$Q_{2}$,  то  в  конце   некоторое заключительное состояние будет
принадлежать $Q_{1}\setminus Q_{2}$,  что невозможно. Аналогично
доказывается правильность вычисления $Q'_{1}$ и $Q'_{2}$  на
отрезках. Переходы $\A(D)$ устроены так, что находясь на  каком-либо
отрезке $D$ первого или третьего типа, можно уйти с него  только  по
переходу, соответствующему следующему отрезку второго  типа,  и  лишь
тогда, когда информация о  первом  отрезке соответствует $D$.
Правильность вычисления этой  информации очевидна.  Построение
$\A(D)$,  очевидно, производится за экспоненциальное время.
Теорема~\ref{transducer-decomposition} и  достаточность критерия
конечнозначности доказаны.
\end{proof}

Можно  построить  $\A(D)$  так,   чтобы   он   обладал   следующим
дополнительным свойством: для любого слова $u$  существует  не  более
одного допускающего пути со входом $u$.  Для  этого  нужно  с  самого
начала перенумеровать все переходы $\A$. В определении  состояний
$\A(D)$ следует добавить для отрезков первого типа~--- компоненты,
вычисляющие множества локальной односторонней и двусторонней
достижимости,  для отрезков третьего типа ---
множество ``тупиковых'' пар вида $\langle
q,m\rangle$.  Здесь $q$  ---  состояние $\A$,  в  котором  по
предположению оканчивается начало некоторого возможного  пути,
последовательность переходов которого  лексикографически  меньше, чем
у  угадываемого пути. В числе $m$ вычисляется  та  же
характеристика  возможного пути, которая раньше вычислялась только
для  угадываемого  пути.  В устройстве  переходов  $\A(D)$
добавляется  правило  о  том,  что  все переходы из текущего
состояния, которые меньше угаданного, либо ведут в локально
двусторонне недостижимое состояние (на отрезках  типа  1, 3), либо не
соответствуют указанному  в $D$  переходу  (тип~2),  либо (отрезок
типа~3) ведут в состояние, которое входит в  ``тупиковую''  пару. 
Если в $\A(D)$ есть переход из $s_{1}$  в $s_{2}$  со  входом
$a$  и выходом $v$, не выводящий за пределы отрезка третьего типа, 
то для каждого состояния $q''$,  являющегося
последователем по $a$ состояния $q'$, входящего в ``тупиковую''  пару
$\langle q',m\rangle\in P(s_{1})$, должно
выполняться хотя бы одно из следующих условий.

1)~$q''\notin Q'_{2}(s_{2})$.

2)~В $P(s_{2})$  существует  ``тупиковая''  пара $\langle
q'',m_{1}\rangle$, где $m_{1}$ вычислено по $m$,
$v$ так же, как  вычислялось для угадываемого пути.

Если же рассматриваемый переход выводит за пределы отрезка, то
в любой ``тупиковой''  паре из $P(s_{1})$ число $m$ должно
быть не равно числу, указанному в $D$.

Легко видеть, что описанный преобразователь для  каждого  входа
допускает лишь тот путь с диаграммой $D$, последовательность
переходов которого  наименьшая  в  лексикографическом  смысле.
Укажем   одно следствие наших построений.

\begin{theorem} \label{values-on-one-word} % теорема 3
Для любого слова $u$ в $\A$ существует множество $M(u)$  из
$\exp(\poly(n))$ допускающих путей со входом $u$  такое,  что  для
любого допускающего пути $l$ со входом $u$ существует путь $l'\in
M(u)$  такой,  что $\вых(l')=\вых(l)$, и для любого $u'\subseteq u$
выполняется: $|d(l,l',u')|\leqslant 2n^4$.
\end{theorem}

В  частности,   как   доказал   А.~Вебер в \cite{Web-diss87},
значность конечнозначного   преобразователя   размера $n$    не
превосходит $\exp(\poly(n))$.

Для доказательства теоремы~\ref{values-on-one-word} возьмем в
качестве $M(u)$ по  одному пути с каждой  возможной  диаграммой.
Утверждение  теоремы~\ref{values-on-one-word} легко следует из
лемм~\ref{equivalent-states}, \ref{two-accepting-paths} и
следствия~\ref{two-prefixes}.

Нижняя   оценка   значности   конечнозначного   преобразователя
экспоненциальна. Легко  показать,  что  даже  число  различных  длин
выходов на  одном  входе  может  быть  экспоненциальным.  Для  этого
рассмотрим преобразователь $\B$, имеющий $m+1$ пару  состояний:
$(q_{1},q'_{1})$, $(q_{2},q'_{2}),\ldots,(q_{m+1},q'_{m+1})$.
Начальные состояния $q_{1},\,q'_{1}$, заключительные
$q_{m+1},\,q'_{m+1}$.  Переходы  следующие:
$$
\langle q_{i},u_{i},\Lambda,q_{i+1}\rangle,\ \langle
q_{i},u_{i},\Lambda,q'_{i+1}\rangle,\ \langle
q'_{i},u_{i},\Lambda,q_{i+1}\rangle,
$$
$$
\langle q'_{i},u_{i},\Lambda,q'_{i+1}\rangle,\ \langle
q_{i},u_{i},c,q_{i}\rangle,\ \langle
q'_{i},u_{i},\Lambda,q'_{i}\rangle,
$$
где $u_{i}=a$ при нечетном $i$ и $u_{i}=b$ при четном, $a$, $b$, $c$
--- буквы. Очевидно,  что  $\B$ конечнозначный. Пусть $f(k)=2^{m-k}$.
Тогда  для  входа $a^{f(0)}a\,b^{f(1)}b\, a^{f(2)}a\,b^{f(3)}b\ldots
a^{2}a\,bb$ (считаем $m$ четным)  преобразователь $\B$  может,
очевидно, выдать любой выход $c^{k}$, где число $k$ записывается в
двоичной системе числом из не более $m$ цифр. Так как таких чисел
всего $2^{m}$,  то нижняя экспоненциальная оценка доказана.

В  общем  случае  дополнение  до   множества,   распознаваемого
недетерминированным  автоматом  размера $m$,  распознается
автоматом размера $\exp(\poly(m))$. Однако, в данном случае имеет
место

\begin{theorem} \label{diagram-automaton} % теорема 4
Для  любой  диаграммы $D$  существует  автомат  $\A'(D)$ размера
$\exp(\poly(n))$, который распознает множество таких  входов $u$, что
не существует допускающего пути в $\A(D)$ со входом $u$. Для  каждого
$u$ в $\A'(D)$ существует не более одного допускающего пути со входом
$u$.
\end{theorem}
\begin{proof}
Состояния $\A'(D)$ включают множества $Q_{1}$, $Q_{2}$,  в которых
вычисляются   множества   односторонней   и   двусторонней
достижимости. Кроме того, они содержат множества $Q'_{1}$ и $Q'_{2}$
локальной односторонней и двусторонней достижимости, а для  отрезков
третьего типа еще множество пар $\langle q,m\rangle$. 
Здесь $q$  --- состояние из $Q'_{2}$,
в котором оканчивается возможный путь, т.~е. путь  с прочитанной
частью входа, который может оказаться началом некоторого пути с
диаграммой $D$, $m$ --- та  же  характеристика  этого  пути на
отрезке, как  и  в  $\A(D)$.  Множество  пар  полное,  т.~е.
если существует  возможный  путь  с   некоторыми   характеристиками,
то существует и соответствующая им пара. Множества $Q_{1}$,
$Q_{2}$, $Q'_{1}$, $Q'_{2}$  вычисляются так же, как в $\A(D)$. Если
при очередном переходе новое $Q_{2}$ остается на том же отрезке $D$,
что и старое, то новые $Q'_{1}$, $Q'_{2}$ вычисляются так  же, как в
$\A(D)$, а новое  множество  пар  вычисляется  по  старому
естественным образом с сохранением свойства полноты. Если  очередной
переход во множествах соответствует отрезку второго  типа,  а  перед
этим был отрезок первого или третьего типа, то переход на  следующий
отрезок $D$ осуществляется лишь в  том  случае,  если $Q'_{2}$
состоит  из конечного состояния отрезка, а для третьего типа среди
пар  есть хотя бы одна, которая соответствует  информации $D$
для  пройденного отрезка. Если же $Q'_{2}$ пусто или нет
соответствующей пары, а также в случае,  когда  очередной переход
во  множествах противоречит $D$, совершается переход в состояние
$\langle Q_{1},Q_{2},{\rm ``сбой''}\rangle$, и дальше продолжают
вычисляться только $Q_{1}$  и $Q_{2}$,   слово   ``сбой''
сохраняется (отметим, что $Q_{1}$ может стать и пустым).   
В заключительных состояниях $\A'(D)$ все состояния из
$Q_{2}$ заключительные, а из $Q_{1}\setminus Q_{2}$ ---
незаключительные. Среди  состояний  $\A'(D)$,  в  которых
выполняется это свойство, незаключительными являются лишь такие, где
нет сбоя, $Q_{2}$ равно последнему множеству из $D$,
$Q'_{2} = \{q\}$, где $q$ --- последнее состояние из $D$,
а если последний отрезок имеет третий тип, то существует
соответствующая диаграмме пара $\langle q,m\rangle$.

Легко видеть, что если в $\A$ нет допускающего пути со входом $u$  и
диаграммой $D$, то $\A'(D)$ допускает $u$. Пусть наоборот, в
$\A'(D)$ есть допускающий путь со входом $u$. Так же, как в
доказательстве теоремы~\ref{transducer-decomposition}, показывается,
что $Q_{1}$, $Q_{2}$, $Q'_{1}$, $Q'_{2}$ вычисляются  верно.  Из
устройства переходов и полноты множества наборов следует, что
учитываются все возможные начала  путей, претендующих  на диаграмму
$D$, и верно определяется их отсутствие. Поэтому в $\A$ нет
допускающего  пути со входом $u$ и диаграммой $D$. Из того, что
входная буква и фиксированный вариант угадывания $Q_{2}$ и $Q'_{2}$
однозначно определяют переход  из любого состояния $\A'(D)$, следует
единственность допускающего пути со  входом $u$.
Теорема~\ref{diagram-automaton} доказана. Отметим, что   подобную
теорему для двухэкспоненциальной оценки доказал в \cite{Web-man87}
А.~Вебер.
\end{proof}

А.~Вебер доказал в \cite{Web-diss87} следующую теорему.

\begin{theorem} \label{finite-value-poly-algorithm}% теорема 5
Существует  полиномиальный  алгоритм,   который   по произвольному
преобразователю решает, конечнозначный он или нет.
\end{theorem}
\begin{proof}
Этот результат  следует  из  леммы~\ref{construct-reduced}, критерия
конечнозначности (теорема~\ref{finite-value-characteristic}) и того,
что   по произвольному преобразователю $\A$ без пустых входов можно
за полиномиальное время решить, удовлетворяет ли он критерию.
Покажем, как  это сделать. Перебираем пары состояний $\langle
s_{1},s_{2}\rangle$. Для каждой пары сначала проверим, выполняется
ли   условие~(2).   Для этого, построим   следующий
недетерминированный  автомат $A_{1}$. Его состояния  ---
упорядоченные четверки $\langle q_{1},q_{2},q_{3},m\rangle$, где
$q_{1},\,q_{2},\,q_{3}$ --- состояния $\A$, а $m$ --- либо  целое
число такое, что $|m|\leqslant n^4$, либо символ $*$. 
Переход из состояния
$\langle q_{1},q_{2},q_{3},m\rangle$ в состояние $\langle
q'_{1},q'_{2},q'_{3},m'\rangle$ со входом $a$ существует тогда и
только тогда, когда, во-первых, для каждого $i = 1,2,3$ существует
переход в $\A$  из $q_{i}$  в $q'_{i}$  со входом $a$ (обозначим его
выход через $v_{i}$) и, во-вторых, если $m$ --- число и
$|m+|v_{1}|-|v_{2}||\leqslant n^4$, то $m'=m+|v_{1}|-|v_{2}|$, иначе
$m'=*$.  Начальное  состояние $A_{1}$: $\langle
s_{1},s_{1},s_{2},0\rangle$,   заключительное: $\langle
s_{1},s_{2},s_{2},*\rangle$. В $m$ вычисляется разность между
длинами выходов $p_{1}$  и $p_{2}$, а $*$ указывает, что ее модуль
превысил $n^4$.

Очевидно, что из существования допускающего пути в $A_{1}$  следует
существование указанных в критерии путей $p_{1}$, $p_{2}$, $p_{3}$
таких,  что  на некотором начале $u'$ их общего входа
$|d(p_{1},p_{2},u')| > n^4$.  Обратно,  из существования  таких
путей вытекает,   очевидно,   существование допускающего пути в
$A_{1}$. Таким образом, выполненность условия~(2) для $s_{1}$,
$s_{2}$ эквивалентна  отсутствию  в $A_{1}$  допускающего  пути,
что, очевидно, проверяется за полиномиальное время.

Теперь  проверим  для $s_{1}$, $s_{2}$   выполненность условия~(1),
предполагая, что условие~(2) для них выполнено. Сначала заметим, что
условие~(1) эквивалентно следующему условию~$(1)'$: слова
$\вых(p_{1})$  и $\вых(p_{2})$ согласованы. Действительно, если (1)
нарушается  для  путей $p_{1}$, $p_{2}$, $p_{3}$, то для путей
$p'_{1}=p_{1}^{k}$, $p'_{2}=p_{2}p_{3}^{k-1}$, $p'_{3}=p_{3}^{k}$,
где $k$  достаточно велико, нарушается условие~$(1)'$. Построим
следующий автомат $A_{2}$.  Его состояния делятся на три множества:
$Q_{1}$, $Q_{2}$, $Q_{3}$.  В $Q_{1}$  это пятерки $\langle
q_{1},q_{2},q_{3},m,a\rangle$, здесь $q_{1}$, $q_{2}$, $q_{3}$ так
же,  как  в $A_{1}$, соответствуют последним состояниям угадываемых
путей $p_{1}$, $p_{2}$, $p_{3}$, в $m$ вычисляется разность длин
выходов $p_{1}$ и $p_{2}$. При  этом требуется,  чтобы $|m|\leqslant
n^4$, и если  это  неравенство нарушается,   переход   отсутствует.
В $a$ естественным образом вычисляется последняя буква того  пути
из $p_{1}$, $p_{2}$, выход которого в данный момент строго длиннее
(если $|m|>0$),  а если $m=0$,  то $a=\Lambda$.  Начальное
состояние: $\langle s_{1},s_{1},s_{2},0,\Lambda\rangle$,
заключительных состояний в $Q_{1}$ нет.

Находясь в произвольном состоянии $\langle
q_{1},q_{2},q_{3},m,a\rangle\in Q_{1}$ ($m\not= 0$), $A_{2}$ может
``предположить'', что именно  в  указанной  букве $a$  произойдет
рассогласованность $\вых(p_{1})$ и $\вых(p_{2})$ (назовем ее сбоем),
и  перейти (с  пустым  входом  и  выходом)  в  состояние  из
$Q_{2}$, имеющее  вид $\langle q_{1},q_{2},q_{3},a,k\rangle$,  где
$k$ сначала равно $m$.  Здесь  в $q_{1}$, $q_{2}$, $q_{3}$
вычисляется обычная информация, $a$~--- буква  предполагаемого сбоя,
$k$ указывает, на сколько букв надо  нарастить  ``короткий'' выход,
чтобы проверить, действительно  ли  в  указанном  месте произойдет
сбой. Переходы между состояниями в $Q_{2}$ очевидным образом
уменьшают $|k|$  по мере  нарастания  ``короткого''  выхода, знак
$k$  определяет  путь с ``коротким'' выходом. Когда на ``коротком''
выходе появляется буква,  в которой   по предположению   должен быть
сбой, проверяется, действительно ли эта буква не  равна $a$. Если
это так, $A_{2}$  может перейти в состояние из $Q_{3}$, которое
имеет вид $\langle q_{1},q_{2},q_{3}\rangle$.  Если, находясь  в
состоянии $\langle q_{1},q_{2},q_{3},0,\Lambda\rangle\in Q_{1}$,
$A_{2}$ обнаруживает при очередном переходе несогласованность
выходов $p_{1}$ и $p_{2}$, то  он  тоже может перейти  в $\langle
q'_{1},q'_{2},q'_{3}\rangle\in Q_{3}$. Нахождение  в  состоянии  из
$Q_{3}$ означает, что сбой произошел, и теперь осталось  достроить
пути $p_{1}$, $p_{2}$, $p_{3}$ до конца. Переходы в $Q_{3}$
определяются  естественным  образом, заключительное состояние:
$\langle s_{1},s_{2},s_{2}\rangle$. Очевидно,  что  условие~$(1)'$
выполнено для $s_{1}$, $s_{2}$ тогда и  только  тогда,  когда  не
существует допускающего пути в $A_{2}$. Полиномиальность времени
проверки  критерия конечнозначности и
теорема~\ref{finite-value-characteristic} доказаны.
\end{proof}


\section{Вложенность преобразователей}

Перейдем  к   вопросам,   связанным   с   вложенностью   одного
преобразователя в другой.  В~\cite{CulKarh86} доказана  разрешимость
выяснения вопроса о вложенности произвольного преобразователя в
конечнозначный без оценки на время алгоритма. А.~Вебер
в~\cite{Web-man87}  доказал разрешимость этого вопроса за время
$\exp(\exp(\poly(n)))$, где $n$~---  сумма размеров
преобразователей. Размер  зоны (т.е. используемой памяти)  
у  этого алгоритма  тоже двойная
экспонента. Мы докажем теорему, усиливающую этот результат, построив
алгоритм с экспоненциальной зоной.

\begin{theorem} \label{transducers-inclusion-algorithm} % теорема 6
Существует детерминированный алгоритм, работающий на зоне
$\exp(\poly(n))$, который по  произвольному  преобразователю $\A_{1}$
и конечнозначному преобразователю $\A_{2}$ решает вопрос о
вложенности $\A_{1}$  в $\A_{2}$.
\end{theorem}
\begin{proof}
В силу леммы~\ref{construct-reduced} можно считать, что $\A_{1}$  и
$\A_{2}$  не имеют пустых входов. Следующая лемма  утверждает,  что
если $\A_{1}$  не вложен в $\A_{2}$, то это проявляется на выходах
экспоненциальной длины.

\begin{lemma}  \label{transducer-not-included} % лемма 5
Если преобразователь $\A_{1}$  не  вложен  в конечнозначный
преобразователь $\A_{2}$, то существует пара $\langle u,v\rangle$
такая, что ${\langle u,v\rangle\in \Gamma(\A_{1})}$, ${\langle
u,v\rangle\notin \Gamma(\A_{2})}$ и ${|v|\leqslant \exp(p_{1}(n))}$,
где $p_{1}(n)$ --- некоторый полином.
\end{lemma}
\begin{proof}
Рассмотрим допускающий путь $l_{1}$ в $\A_{1}$  с выходом
минимальной длины такой,  что $\langle u,v_{1}\rangle\in
\Gamma(\A_{1})$, $\langle u,v_{1}\rangle\notin \Gamma(\A_{2})$, где
$u=\вх(l_{1})$, $v_{1}=\вых(l_{1})$. Предположим, что
$|v_{1}|>\exp(p_{1}(n))$, где степень $p_{1}(n)$   достаточно
велика. Будем   далее подразумевать под словосочетаниями типа
``достаточно много'' $\exp(\poly(n))$,  где степень полинома
настолько  велика, чтобы можно   было   выполнить все описываемые
действия. Если $|v_{1}| = |v_{2}|$, но $v_{1} \ne v_{2}$,  то
назовем левым (соответственно, правым) сбоем между $v_{1}$ и $v_{2}$ 
первую  слева (соответственно, справа) пару неравных букв слов 
$v_{1}$ и $v_{2}$, равноотстоящих от начала (соответственно, конца).  
По теореме~\ref{values-on-one-word} количество
различных $v_{2}$, таких что $\langle u, v_{2}\rangle\in
\Gamma(\A_{2})$~---  фиксированная экспонента, поэтому и букв на
$v_{1}$, в которых имеет  место  левый или правый сбой между $v_{1}$
и каким-нибудь из таких $v_{2}$, тоже мало. Возьмем в слове $v_{1}$
достаточно большое подслово $r$, в которое не попадает  ни один сбой
и которое  лежит от  ближайшего сбоя  на расстоянии,  в достаточно
большое число раз превышающем $|r|$.

Будем называть начала входа $u$ точками. Иногда под точкой  будем
понимать также то место на пути, где  заканчивается  соответствующее
начало входа. Выделим достаточно много точек, так чтобы  выполнялись
следующие три условия:

1. Слова $\вых(l_{1}(u'))$ для всех выделенных точек $u'$ заканчиваются
внутри $r$ и различны.

2. Во всех выделенных точках $l_{1}$ проходит через  одно  и  то  же
состояние.

3. Во  всех  выделенных  точках   множества   левосторонней   и
правосторонней  достижимости  в  $\A_{2}$   одни   и   те   же   (множеством
правосторонней  достижимости  в  точке $u'$  мы  называем   множество
состояний, из которых существует путь в заключительное состояние  со
входом $u''$, где $u'u''=u)$.

Будем следующим образом сужать по  шагам  множество  выделенных
точек и одновременно строить в  $\A_{2}$ множество отмеченных состояний. На
очередном  шаге  для  каждого  неотмеченного  состояния $q$   из    $\A_{2}$
проверяем, существует ли допускающий путь в $\A_{2}$ со входом $u$,  который
находится в $q$ в не менее чем $m/\exp(n)$ выделенных  точках,  где $m$  ---
количество выделенных точек на данный момент.  Если  существует,  то
отмечаем $q$, ставим ему в соответствие один  из  описанных  путей,  а
множество выделенных точек уменьшаем в $\exp(n)$ раз,  так  чтобы  этот
путь во всех выделенных точках проходил через $q$. Путь,  поставленный
в соответствие отмеченному состоянию $q$,  будем  обозначать $l(q)$  и
называть отмеченным. Когда на очередном шаге  ни  одно  неотмеченное
состояние не будет отмечено, процесс останавливается. Так как  шагов
не более $n$, в конце процесса количество выделеннных точек достаточно
велико. Каждый путь $l(q)$  во  всех  выделенных  точках  находится  в
состоянии $q$.

Разделим все выделенные точки  на  три  примерно  равные  части
идущих подряд точек, а между левой и средней частью зафиксируем одну
из выделенных точек $u_{b}$, которую  будем  называть  граничной.
Каждой выделенной точке $u'$ из средней части сопоставим множество,
состоящее из всех таких наборов $\langle q,q_{1},q_{2},d\rangle$,
что в $\A_{2}$ существует путь $l$ из $q_{1}$ в $q_{2}$ со входом
$u''$, где $u'=u_{b}u''$, $q$ --- отмеченное состояние и  разность
между $|\вых(l)|$ и длиной выхода $l(q)$ на отрезке  входа $u''$
равна $d$, причем $|d|\leqslant 2n^4$. Число описанных множеств
--- фиксированная экспонента, поэтому  существует  много
выделенных средних   точек,   которым соответствует одно и то же
множество. В средней части будем  считать выделенными только эти
точки.

Так как во всех выделенных точках путь $l_{1}$  находится  в  одном
состоянии,  мы  можем  выбросить  любое  множество  отрезков   между
выделенными точками и получить укороченный допускающий путь $l'_{1}$
в $\A_{1}$. В силу выбора $l_{1}$, существует допускающий путь
$l'_{2}$ в  $\A_{2}$  такой,  что $\вх(l'_{2})=\вх(l'_{1})$,
$\вых(l'_{2})=\вых(l'_{1})$. Пусть выбросы отрезков произведены в
средней  трети.  Будем  понимать  под  выделенными  точками  пути  с
выбросами точки, получившиеся из точек  первоначального  пути  после
выбросов из них. Покажем, что $l'_{2}$ хотя бы в одной из выделенных
точек первой и последней трети проходит через отмеченные состояния.
Будем обозначать через $q(t)$ состояние, в котором находится $l'_{2}$
в точке $t$. Рассмотрим  на  $\вх(l'_{2})$  точку $t$,
соответствующую  самому   правому выброшенному отрезку.  В  силу
совпадения  множеств  правосторонней достижимости во всех выделенных
точках, существует путь  из $q(t)$  в заключительное состояние, вход
которого равен $u'u''$, где $u'$  ---  вход самого правого
выброшенного отрезка, а $u''$ --- вход $l'_{2}$ от $t$  до  конца.
Соединив старое начало с новым  концом,  получим  новый  допускающий
путь, на входе которого одним выброшенным отрезком меньше. Таким  же
образом вставим остальные выброшенные отрезки и получим  допускающий
путь со входом $u$. В первой трети выделенных точек он проходит
через некоторое состояние $q_{1}$, которое  встречается  на  примерно
$1/(3n)$  от количества всех выделенных точек. Если бы $q_{1}$ не было
отмеченным, это бы  противоречило  завершенности  построения
отмеченных  состояний. Аналогично  показывается,  что   на
последней   трети   существует выделенная точка, в которой $l'_{2}$
находится в отмеченном состоянии $q_{2}$.

Так как пути $l(q_{1})$ и $l(q_{2})$ во всех выделенных  точках
проходят через $q_{1}$ и $q_{2}$, то из этих путей можно  сделать
выбросы  на  тех  же отрезках входа, что  и  для $l_{1}$.  Будем
обозначать  пути  с  такими выбросами через $l'(q_{1})$ и
$l'(q_{2})$. Из условия~(2) (при $s_{1}=q_{1}$, $s_{2}=q_{2}$,
$p_{1}$, $p_{2}$, $p_{3}$ --- участки путей $l'(q_{1})$, $l'_{2}$,
$l'(q_{2})$ соответственно) следует, что разность длин выходов пути
$l'_{2}$ на отрезке от $u_{b}$ до любой  средней точки $u'$ и пути
$l'(q_{1})$ на том же участке входа,  не  превосходит  по модулю
$2n^4$.   Учитывая   это,   рассмотрим    следующий    процесс
``восстановления'' $l'_{2}$ до пути с  первоначальным  входом.
Пусть самый левый выброшенный отрезок расположен между точками
$t_{1}$  и $t_{2}$  и  его вход есть $u_{1}$. Обозначим через $l'$
участок пути $l'_{2}$ от $u_{b}$  до $t_{1}$.  По построению
(совпадение множеств наборов в средних точках) существует путь $l''$
из $q(u_{b})$ в $q(t_{1})$  такой,  что  $\вх(l'')=\вх(l')u_{1}$,  а
разность $|\вых(l'')|-|\вых(l')|$ равна длине выхода пути $l(q_{1})$
на отрезке  входа $u_{1}$. Вход  нового  допускающего  пути,
получающегося  заменой  в $l'_{2}$ участка $l'$ на $l''$, содержит
на один выброшенный отрезок меньше. Можно сказать, что мы вставили
отрезок на входе и при этом выход удлинился на длину выхода пути
$l(q_{1})$  на  вставленном  отрезке  входа.  После этого, таким же
образом вставляем второй слева отрезок и так  далее. В конце получим
``восстановленный'' путь со входом $u$.

Будем  обозначать  для  выброса $\alpha$   через $l'_{2}(\alpha)$
некоторый допускающий путь  с  выбросом $\alpha$  в  $\A_{2}$; через
$l_{2}(\alpha)$  ---  некоторый ``восстановленный'' путь  со  входом
$u$,  построенный  описанным  выше процессом; $q_{1}(\alpha)$ ---
некоторое  отмеченное  состояние,  через  которое проходит в  первой
трети  выделенных  точек  путь $l'_{2}(\alpha)$; $t_{1}(\alpha)$  ---
некоторая выделенная точка первой трети в которой $l_{2}(\alpha)$
находится  в $q_{1}(\alpha)$; $q_{2}(\alpha)$ и $t_{2}(\alpha)$ ---
то же самое для  последней  трети; $l'_{\alpha}(q_{1})$  --- путь
$l(q_{1})$ с выбросом $\alpha$; $|\alpha|$ --- сумма длин выходов
выбрасываемых  из $l_{1}$ отрезков.

Любой отрезок между двумя средними  выделенными  точками  имеет
относительно каждого отмеченного состояния $q$  один  из  трех типов:
длина выхода $l(q)$ на этом отрезке может  быть  больше  длины выхода
пути $l_{1}$ на нем (положительный тип), меньше (отрицательный тип)
или равна  (нулевой  тип).  Таким  образом,   каждому   такому
отрезку сопоставляется  набор   пар $\langle q,{\rm тип}\rangle$.
Всего   таких   наборов   --- фиксированная экспонента. Выберем
достаточно много  непересекающихся отрезков,  которым соответствует
один и тот же набор. Упорядочим  их и рассмотрим последовательность
$S$ выбросов, в которой $m$-й  выброс состоит из первых $m$ отрезков
в нашем упорядочении. Каждому выбросу $\alpha$ из $S$ поставим   в
соответствие   пару $\langle q,v\rangle$,   где $q=q_{1}(\alpha)$,
$v=\вых(l_{2}(\alpha))$. По теореме~\ref{values-on-one-word}
количество таких  пар~--- фиксированная экспонента. Пусть
$\alpha_{1}$ и $\alpha_{2}$, --- два различных выброса из $S$,
которым соответствует одна и та же пара $\langle q,v\rangle$. Если бы
тип  всех  отрезков относительно $q$ был ненулевым, то, очевидно,
разности  между длинами выходов ``восстановленных'' путей и $|v_{1}|$
были бы различны для $\alpha_{1}$ и $\alpha_{2}$, значит эти выходы
тоже были бы различны. Полученное  противоречие показывает, что тип
всех отрезков относительно $q$  нулевой,  что  с учетом конструкции
вставки дает для  всех $\alpha\in S$:
$|\вых(l_{2}(\alpha))|=|v_{1}|$.

Скажем, что выброс $\alpha$ является выбросом нулевого типа, если тип
всех отрезков из $\alpha$ относительно $q_{1}(\alpha)$ нулевой. Таким
образом,  на  любом участке средней части с достаточно  большим
количеством  выделенных точек  существует   достаточно   много
выбросов   нулевого   типа: $\alpha_{1}$,
$\alpha_{2},\ldots,\alpha_{k}$,  где  все $|\alpha_{i}|$  различны.
Поэтому, можно взять достаточно много выбросов на средней трети так,
чтобы выполнялись следующие условия:

1. Выбросы упорядочены, т.е.\ каждый  отрезок  одного  из  любых
двух выбросов лежит  строго  левее  каждого  отрезка  другого  и  не
пересекается с ним.

2. Все выбросы являются выбросами нулевого типа.

3. Для любых двух выбросов $\alpha_{1}$, $\alpha_{2}$: $|\alpha_{1}|
\ne |\alpha_{2}|$.

4. Для всех выбросов $\alpha$ $q_{1}(\alpha)$ одно и то же (обозначим
его $q_{1})$.

5. Для всех $\alpha$ разности между длиной выхода $l'_{2}(\alpha)$
на отрезке  от $t_{1}(\alpha)$ до $u_{b}$ и длиной выхода
$l'_{\alpha}(q_{1})$ на том же отрезке  одинаковы (из условия (2) 
теоремы~\ref{finite-value-characteristic} следует,
что эта разность по модулю не превосходит $n^4$).

6. У всех $l_{2}(\alpha)$ (а значит и $l'_{2}(\alpha))$ одинаковый
выход  от  начала до $u_{b}$.

7. Все $\вых(l_{2}(\alpha))$ одинаковы (обозначим этот выход $v_{2}$).

Из условия~2 вытекает, что выход пути $l(q_{1})$ не  пуст  на  любом
отрезке, входящем в выбросы.  Тогда,  из  условий~(1) и~(2)
теоремы~\ref{finite-value-characteristic} и того, что
разность выходов путей $l'_{2}(\alpha)$ и $l'_{\alpha}(q_{1})$ на
отрезке от $t_{1}(\alpha)$  до $t_{2}(\alpha)$ не меняется после
вставки, следует, что для всех $\alpha$ (кроме, возможно, $n^4$
самых левых и самых правых)  $\вых(l_{2}(\alpha))$  фактически  получается  из
$\вых(l'_{2}(\alpha))$ вставкой выходов пути $l(q_{1})$ на отрезках
из $\alpha$ (действительно, если $w$ и $w_1$~--- выходы путей
$l'_{\alpha}(q_{1})$ и $l(q_{1})$ на отрезке от $t_{1}(\alpha)$
до $t_{2}(\alpha)$, то выход $l'_{2}(\alpha)$ на этом отрезке
является началом слова $w^{\infty}$, оканчивающимся в 
$n^{4}$-окрестности конца первого $w$, а выход $l_{2}(\alpha)$
на том же отрезке является оканчивающимся в аналогичной окрестности
началом слова $w_{1}^{\infty}$, где $w_{1}$ получается из $w$ 
вставками, произведенными вне $n^{4}$-окрестностей начала и конца). 
Далее, из условия~5  следует, что для всех $\alpha$ (кроме,
возможно, $n^4$ самых левых) выходы  всех $l'_{2}(\alpha)$ после
точки $u_{b}$ повторяют выходы путей $l'_{\alpha}(q_{1})$  с  одного
и  того  же места на общем начале выходов $l'_{\alpha}(q_{1})$.
Учитывая условие~6, заключаем, что если выброс $\alpha_{1}$ строго
левее чем $\alpha_{2}$, то и вставка на  выходе  для $\alpha_{1}$
происходит строго левее (считая по длине всего  выхода)  вставки для
$\alpha_{2}$. Назовем это свойство  монотонностью.  Напомним,  что
$v_{1}\not= v_{2}$, $|v_{1}|=|v_{2}|$ (в силу условия~2) и для
любого выброса если из $v_{1}$  и $v_{2}$ выбросить  соответствующие
отрезки,  они  станут  равными.  В  силу монотонности, существует
много таких выбросов, для  которых  участок выбросов из $v_{2}$ не
содержит ни левого ни правого сбоя между $v_{1}$ и $v_{2}$.
Рассмотрим эти выбросы. Легко видеть, что для того, чтобы  после них
сбои исчезли, необходимо, чтобы выбросы из $v_{1}$ и $v_{2}$ лежали
по  разные стороны от обоих сбоев. Поэтому, из расположения участка
$r$  следует, что выбросы из $v_{1}$ лежат по одну сторону от обоих
сбоев.  Пусть  они лежат слева от левого сбоя, тогда выбросы  из
$v_{2}$  лежат  справа  от правого сбоя. Возьмем два выброса
$\alpha_{1}$  и $\alpha_{2}$,  где $\alpha_{1}$  левее $\alpha_{2}$.
Рассмотрим подслово $w$ из $v_{1}$ от правого конца $\alpha_{2}$ до
левого сбоя.  При совершении выброса $\alpha_{2}$, $w$ сдвигается
влево и отождествляется  само  с собой. Следовательно, $w$
периодично с  периодом  длины $|\alpha_{2}|$ (напомним, что по
построению подслова $r$ $|w|\gg |\alpha_{2}|$). Легко видеть, что если
продолжить период вправо за $w$,  то нарушение  его должно произойти
в точности на расстоянии $|\alpha_{2}|$ от левого сбоя, иначе сбой
бы не исчез. Рассуждая аналогично  по  отношению  к $\alpha_{1}$,
легко показать, что $w$ периодично с периодом длины $|\alpha_{1}|$ и
что его нарушение происходит в точности на $|\alpha_{1}|$  правее
левого сбоя.  Поскольку 
$|w|\gg |\alpha_{1}|\cdot |\alpha_{2}|$, $w$  периодично  с  периодом  длины
$|\alpha_{1}|\cdot |\alpha_{2}|$. Нарушение этого большого периода
справа от  левого сбоя является,  очевидно,  нарушением  обоих малых
периодов, а нарушение одного из малых периодов является нарушением
и большого. Так как $|\alpha_{1}|\not= |\alpha_{2}|$ (условие~3), мы
получили противоречие с тем, что нарушения этих двух периодов
произошли в разных местах. Случай, когда  выбросы из $v_{1}$ лежат
правее правого  сбоя,  рассматривается  симметричным образом.
Лемма~\ref{transducer-not-included} доказана.
\end{proof}

Для  полноты  рассмотрим  также  оценку  на $|u|$   в   условиях
доказанной леммы. А.~Вебер в \cite{Web-man87} доказал, что если
преобразователь $\A_{1}$ не вложен в конечнозначный преобразователь
$\A_{2}$,  то существует  пара $\langle u,v\rangle\in
\Gamma(\A_{1})$, $\langle u,v\rangle\notin \Gamma(\A_{2})$, где
$|u|\leqslant\exp(\exp(\poly(n)))$. Покажем,  как это утверждение
можно вывести из  леммы~\ref{transducer-not-included}.  Рассмотрим
пару $\langle u,v\rangle$, существование которой доказано в
лемме~\ref{transducer-not-included}, с минимальной $|u|$  при
данном~$v$.  Предположим,  что $|u|>\exp(\exp(\poly(n)))$,  где
степень полинома  достаточно велика. Так как
$|v|\leqslant\exp(p_{1}(n))$, то на допускающем пути $l_{1}$ из
$\A_{1}$ со  входом $u$  и  выходом $v$  существует достаточно
длинный  (две экспоненты)  отрезок  с пустым  выходом. Выделим на
этом отрезке много точек, в которых $l_{1}$ находится в одном
состоянии. Каждой точке $u'$ из них поставим в соответствие
множество пар вида $\langle q,v'\rangle$, где $v'\subseteq v$,
$q$~--- состояние из $\A_{2}$ такое,  что  в $\A_{2}$ существует
путь из начала  в $q$ со входом $u'$  и  выходом $v'$. Из
теоремы~\ref{values-on-one-word} следует, что количество таких
множеств~--- фиксированная двойная экспонента, поэтому можно выбрать
две точки $u_{1}$, $u_{2}$, которым соответствует одно и то же
множество. По построению, в $\A_{2}$ существует допускающий путь
$l_{2}$  со входом, получающимся  из $u$ выбрасыванием отрезка от
$u_{1}$ до $u_{2}$, и выходом $v$. Пусть $q$~---  состояние,  в
котором кончается $l_{2}(u_{1})$. В силу совпадения соответствующих
множеств, в $\A_{2}$ существует  путь $l'_{2}$ из  начала   в $q$
такой,  что $\вх(l'_{2})=u_{2}$, $\вых(l'_{2})=\вых(l_{2}(u_{1}))$.
Соединяя путь $l'_{2}$ с продолжением  пути $l_{2}$, получим
допускающий путь в $\A_{2}$  со входом $u$  и  выходом $v$. Это
противоречит тому, что $\langle u,v\rangle\notin \Gamma(\A_{2})$.
Утверждение доказано.

Легко  показать,  что  нижняя  оценка  на  длину  выхода $v$   в
формулировке леммы~\ref{transducer-not-included} экспоненциальна. Эта
оценка, очевидно, следует из того, что для любого $n$ существует
недетерминированный автомат $A$ размера  $\poly(n)$,  который  не
допускает  некоторое слово $w$,  где $|w|=\exp(\poly(n))$, но
допускает  все  слова длины меньшей $|w|$.  В качестве $w$ возьмем
конкатенацию записей всех $n$-разрядных  двоичных чисел (младшие
разряды слева), расположенных в порядке  возрастания, начиная от
слова из одних нулей и кончая словом  из  одних  единиц. Автомат $A$
в процессе работы угадывает причину, по которой читаемое слово не
равно $w$.  Причины могут быть такими:  первое  слово  не нулевое;
некоторое  последующее число   не равно   предыдущему, увеличенному
на 1 (в этом случае угадывается неверный разряд); длина всего слова
не кратна $n$; последнее слово не единичное. В  состояниях $A$ (до
угадывания) хранится номер последнего прочитанного  разряда  и
информация  о том, есть  ли левее него  нули  в  текущем  числе.
Дальнейшие детали очевидны.

Авторам неизвестен ответ на следующий

\begin{question}
Существует ли  двухэкспоненциальная  нижняя  оценка  на длину входа
$u$ в формулировке леммы~\ref{transducer-not-included}?
\end{question}

Докажем  теорему~\ref{transducers-inclusion-algorithm}.   Опишем
недетерминированный   алгоритм, подтверждающий   невложенность
$\A_{1}$   в $\A_{2}$   и работающий на экспоненциальной зоне.
Сначала  алгоритм  угадывает выход $v$, где
$|v|\leqslant\exp(p_{1}(n))$ и записывает $v$  на  ленте. После
этого по  шагам угадывается вход и путь в $\A_{1}$. В каждый момент
на ленте указано $v_{1}\subseteq v$~--- выход угаданного начала пути
в $\A_{1}$  и  множество  пар $\langle v',q\rangle$,  где
$v'\subseteq v$, $q$ --- состояние из $\A_{2}$ такое, что существует
путь из начала в $q$ с угаданным к данному моменту входом и выходом
$v'$. На очередном  шаге угадывается очередная буква $a$ входа и
очередной переход  в $\A_{1}$  со входом $a$. Алгоритм проверяет,
что выход у этого перехода  продолжает $v_{1}$ вдоль $v$, и
дописывает его к $v_{1}$. Затем для каждой  пары $\langle
v',q\rangle$  и каждого перехода в $\A_{2}$ 
из $q$ со входом $a$ и выходом,
который  продолжает $v'$ вдоль $v$ и не выводит за его пределы,
естественным  образом строится новая пара. Повторяющиеся пары
удаляются  из  получившегося нового множества. Алгоритм работает до
тех  пор,  пока $v_{1}$  --- начало $v$  и множество пар непусто.
Если $v_{1}=v$ и во множестве пар нет пары $\langle v,q\rangle$, где
$q$  ---  заключительное состояние, то алгоритм   обнаруживает
невложенность $\A_{1}$ в $\A_{2}$. Правильность работы и
экспоненциальная  зона этого алгоритма очевидны.  По  теореме
Сэвича, недетерминированный алгоритм, работающий  на   зоне $S$,
может быть переделан   в детерминированный, распознающий тот  же
язык  и имеющий зону $S^{2}$. Отсюда следует существование искомого
алгоритма. Теорема~\ref{transducers-inclusion-algorithm} доказана.
\end{proof}

Конструкция   выбросов,   использованная   для   доказательства
теоремы~\ref{transducers-inclusion-algorithm}, позволяет получить
следующий результат.

\begin{theorem} \label{finite-value-included} % теорема 7
Пусть $\A_{1}$ и $\A_{2}$ --- конечнозначные  преобразователи без
пустых входов и $\A_{1}$ вложен в $\A_{2}$. Тогда для любого
допускающего  пути $l_{1}$ в $\A_{1}$ со входом $u$ и выходом $v$
существует допускающий путь $l_{2}$ в $\A_{2}$ с теми же входом и
выходом такой, что для любого $u'\subseteq u$  выполняется:
$|d(l_{1},l_{2},u')|\leqslant\exp(\poly(n))$.
\end{theorem}
\begin{proof}
Обозначим через $M_{1}(u,v)$  и $M_{2}(u,v)$  множества допускающих
путей со входом $u$ и выходом $v$ в $\A_{1}$ и $\A_{2}$
соответственно. Предположим  вопреки  утверждению  теоремы,  что
существует   путь $l_{1}\in M_{1}(u,v)$ такой, что для любого  пути
$l_{2}\in M_{2}(u,v)$  существует $u'\subseteq u$ такое,  что
$|d(l_{1},l_{2},u')|>k\geqslant\exp(\poly(n))$,  где   степень
полинома достаточно велика.  По  теореме~\ref{values-on-one-word}  в
$\A_{2}$ существует  не более чем экспоненциальное множество $M$
путей из $M_{2}(u,v)$ такое, что для  любого пути $l\in M_{2}(u,v)$
существует $l'\in M$  такой, что для  любой  точки $u'$
$|d(l,l',u')|\leqslant 2n^4$. Рассмотрим множество $P$ допускающих
путей $l$  в $\A_{1}$, обладающих следующим свойством: на входе $l$
существует множество $T$ из не более $|M|$ точек такое, что для
любого пути $l'\in M_{2}(\вх(l),\вых(l))$ существует  точка $u'\in
T$ такая,  что $|d(l,l',u')|>k_{1}=k-2n^4$.   Легко видеть, что
$l_{1}\in P$, поэтому $P$ не  пусто.  Пусть $l_{0}$  ---  путь  из
$P$  с минимальной  длиной   выхода,  обозначим: $u_{0}=\вх(l_{0})$,
$v_{0}=\вых(l_{0})$. Соответствующее  ему  множество  точек
обозначим $T_{0}$.   Из   наших предположений следует,  что
$|v_{0}|>k_{1}$. Поэтому,  существует  длинный отрезок $r$ пути
$l_{0}$ с большим выходом, не содержащий точек из $T_{0}$.  Для $r$
повторим всю конструкцию  выбросов,  описанную  в  доказательстве
леммы~\ref{transducer-not-included} (обозначениям 
$l_{1}$, $u$, $v_{1}$ из леммы~\ref{transducer-not-included} 
теперь соответствуют $l_{0}$, $u_{0}$, $v_{0}$). 
Единственное отличие будет
состоять в том, что  в  качестве пути $l'_{2}$ в $\A_{2}$ для пути
$l'_{0}$  в  $\A_{1}$  с выбросами,  мы будем  брать  не
произвольный путь, а такой, что для любой  точки $u'\in T_{0}$
выполняется: $|d(l'_{0},l'_{2},u')|\leqslant k_{1}$. Этот путь
существует в силу условия  выбора $l_{0}$  и того, что
$|\вых(l'_{0})|<|\вых(l_{0})|$. Повторив соответствующее
рассуждение, легко доказать, что существует такой выброс нулевого
типа из пути $l_{0}$, что для  ``восстановленного'' пути $l_{2}$  в
$\A_{2}$ $\вх(l_{2})=u_{0}$,  $\вых(l_{2})=v_{0}$. 
Последнее равенство
следует из того, что при доказательстве
леммы~\ref{transducer-not-included} мы получили противоречие,
предполагая,  что  для  всех выбросов $\alpha$
$\вых(l_{2}(\alpha))\not= v_{0}$. Легко видеть, что в силу нулевого
типа и  конструкции вставки, при вставке отрезка отклонение
$d(l'_{0},l'_{2},u')$  пути  в $\A_{1}$  от пути в $\A_{2}$ может
меняться только  для $u'$,  лежащих  между  граничной точкой $u_{b}$
и  вставляемым  на  входе  отрезком (точнее
$d(l''_{0},l''_{2},u'')=d(l'_{0},l'_{2},u')$, где 
$l''_{0}$, $l''_{2}$~--- пути до вставки, $l'_{0}$, $l'_{2}$~--- 
пути после вставки, $u'=u''$ если $u'$ оканчивается левее вставки и
$u'=(u''\mbox{ со вставкой})$, если правее). Следовательно, 
за пределами отрезка $r$ и  в  частности  во  всех  точках 
$u'\in T$ выполняется: $|d(l_{0},l_{2},u')|\leqslant k_{1}$. 
Получили противоречие с тем, что $l_{0}\in P$.  
Теорема~\ref{finite-value-included} доказана.
\end{proof}

В одном частном случае мы можем  усилить  результат
теоремы~\ref{transducers-inclusion-algorithm}. Будем говорить, что
преобразователь $\A$  \emph{имеет конечную задержку}, если
существует такое  натуральное $c$,  что  для  любого пути $l$, если
$|\вх(l)|\geqslant c$, то $|\вых(l)|>0$. Очевидно, что
$c\leqslant\poly(n)$, где $n=|\A|$.

\begin{theorem} \label{not-included-algorithm} % теорема 8
Существует недетерминированный алгоритм, который  за
недетерминированное время $\exp(\poly(n))$  подтверждает
невложенность произвольного преобразователя $\A_{1}$  в
конечнозначный  преобразователь $\A_{2}$, где $\A_{2}$ имеет конечную
задержку.
\end{theorem}
\begin{proof}
Следующая лемма усиливает в этом частном случае
лемму~\ref{transducer-not-included}.

\begin{lemma} \label{not-included-characteristic} % лемма 6
Если преобразователь $\A_{1}$  не  вложен  в конечнозначный
преобразователь  $\A_{2}$  с  конечной  задежкой,   то существует
пара ${\langle u,v\rangle\in\Gamma(\A_{1})}$, ${\langle
u,v\rangle\notin \Gamma(\A_{2})}$ и ${|u|\leqslant\exp(p_{2}(n))}$
($p_{2}(n)$ --- полином).
\end{lemma}
\begin{proof}
Пусть $l_{1}$ --- допускающий путь  в  $\A_{1}$  минимальной длины
такой,  что
$\langle\вх(l_{1}),\вых(l_{1})\rangle\notin\Gamma(\A_{2})$.
Обозначим: $u=\вх(l_{1})$, $v_{1}=\вых(l_{1})$. Предположим, что
$|u|$  достаточно  велико.  Возможны  два случая. Случай 1:
$|v_{1}|>\exp(p_{1}(n))$ ($p_{1}(n)$ ---  полином  из
леммы~\ref{transducer-not-included}). В этом случае приводим это
предположение к противоречию точно так же, как в доказательстве
леммы~\ref{transducer-not-included}. Случай 2:
$|v_{1}|\leqslant\exp(p_{1}(n))$. В этом случае существует
достаточно длинный участок $r$ пути $l_{1}$ с пустым выходом. На нем
будем делать выбросы так же, как в доказательстве
леммы~\ref{transducer-not-included},  только вместо требования чтобы
выход выбрасываемых отрезков был непуст, потребуем, чтобы длина
входа каждого  выбрасываемого  отрезка  была больше $c$. Повторив
соответствующее рассуждение, докажем существование  выброса $\alpha$
нулевого типа. Но в силу свойства конечной задержки, выход любого
отмеченного пути в $\A_{2}$ непустой на выбрасываемых отрезках
входа. Это противоречит тому, что выход участка $r$ пустой.
Лемма~\ref{not-included-characteristic} доказана.
\end{proof}

Докажем теорему~\ref{not-included-algorithm}. Опишем требуемый
алгоритм. Он угадывает вход $u$ и выход $v$,   где
$|u|\leqslant\exp(p_{2}(n))$, $|v|\leqslant n|u|$. После этого
детерминированно определяется, есть ли в $\A_{1}$ и $\A_{2}$
допускающий путь со входом $u$  и  выходом $v$.  Для  этого, для
каждого $u'\subseteq u$, где $u'$ увеличивается побуквенно,
находится множество пар $\langle v',q\rangle$, где $v'\subseteq v$,
$q$ --- состояние такое, что существует путь из начала в $q$ со
входом $u'$ и  выходом $v'$. Подробности   очевидны.   Алгоритм
обнаруживает невложенность $\A_{1}$ в $\A_{2}$,  если $\langle
u,v\rangle\in \Gamma(\A_{1})$, $\langle u,v\rangle\notin
\Gamma(\A_{2})$.  Очевидно, время работы этого алгоритма примерно
$|u|\cdot |v|$. Теорема~\ref{not-included-algorithm} доказана.
\end{proof}


\begin{thebibliography}{99}

\bibitem{Web-diss87}
A. Weber. \emph{\"Uber die  Mehrdeutigkeit  und  Wertigkeit  von
endlichen Automaten  und  Transducern.}   Dissertation,
Goethe-Universitat Frankfurt am Main, 1987.

\bibitem{Web-man87}
A. Weber. \emph{A Decomposition Theorem for Finite Valued Transducers
and an Application to the  Equivalence Problem.} Proceedings of
MFCS'88, LNCS 324, pp.~552--562, 1988.

\bibitem{Web-man89}
A. Weber. \emph{On the valuedness of finite transducers.} Acta 
Informatica 27(8), pp.~749--780, 1989.

\bibitem{Web-man96}
A. Weber. \emph{Decomposing a $k$-valued transducer into $k$ 
unambiguous ones.} RAIRO Informatique Theorique et Applications 30(5), 
pp.~379--413, 1996.

\bibitem{Sakar-Souza}
Jacques Sakarovitch and Rodrigo de Souza. \emph{On the 
decomposition of $k$-valued rational relations.} Proceedings of
Symposium on Theoretical Aspects of Computer Science 2008 (Bordeaux),
pp.~621--632, 2008.

\bibitem{CulKarh86}
K. Culik II,  J. Karhumaki. \emph{The  Equivalence of Finite Valued
Transducers (on HDTOL Languages) is  Decidable.} TCS 47, pp.~71--84,
1986.

\end{thebibliography}



\end{document}
