Можно ли решить, ограничена ли выходная длина преобразователя входной длиной?

Рассматриваемые здесь преобразователи - это те, которые Википедия называет преобразователями конечного состояния . Поведение преобразователя , то есть вычисляемого им отношения, записывается как : слово является выходом для тогда и только тогда, когда . $T$ $[T]$ $y$ $x$ $x[T]y$

Вопрос: разрешима ли следующая проблема:

Дано: преобразователь и регулярный язык Решить: верно ли, что , слово, означает, что ? $T$ $L$
$\forall x \in L$ $\forall y$ $x[T]y$ $|y| \leq |x|$

Я ищу нетривиальный анализ / разрешимые случаи, сведение к известным проблемам и / или связанным ссылкам. (прямо сейчас даже не уверен, что это вообще разрешимо ...?)

Мотивация: эта проблема была вдохновлена анализом / исследованием автоматизированной теоремы, доказывающей теоретико-числовые проблемы в целом, и широко изученной , в частности , гипотезой Коллатца .

ds.algorithms reference-request automata-theory regular-language dfa ВЗН
источник

ps (должен был упомянуть, как давно известно) преобразователи FSM достаточно мощны, чтобы вычислять отдельные итерации TM «мгновенных описаний» . следовательно, проблема, возможно, связана с LBA и CSL .

ВЗН

По

Вы говорите о количестве выходов на входе

, верно? Не размер выходов, в этом случае это было бы довольно просто.

| F (x) |

$|F(x)|$

x

$x$

Микаэль Кадилхак

оба слова и

длина выходного слова. есть некоторые идеи, но не вижу ничего прямолинейного в данный момент, поэтому вопрос. он предположительно нетривиален из-за

входов / выходов на некоторых переходах и т. д.

x, F (x)

$x, F(x)$

| F (x) |

$|F(x)|$

ϵ

$\epsilon$

vzn

Таким образом, вы неявно предполагаете, что ваш преобразователь функционален - с точки зрения записи, мне это было непонятно :-) Так что насчёт следующего: Пусть

(возможно, недетерминированный) преобразователь, а

- заданный регулярный язык. Измените

на преобразователь

чтобы он проверял, находится ли его вход в

, и все ли его состояния достижимы и совместно достижимы. Тогда

для всех

если в преобразователе

нет простого цикла

T

$T$

L

$L$

T

$T$

T^{'}

$T'$

L

$L$

| T (w) | \leq | w |

$|T(w)| \leq |w|$

w \in L

$w \in L$

T^{'}

$T'$ для которого вход меньше, чем выход, и некоторые дополнительные легкие свойства для переходов, не появляющиеся ни в одном SCC.

Михаэль Кадилхак

Хорошо. для "вход меньше выхода" вы имеете в виду за цикл? думаю, что это стоит написать в качестве ответа. был другой способ сформулировать эту / связанную проблему с более строгими критериями, который, предположительно, нелегок (возможно), возможно, попробует еще раз («часть 2 / продолжение / продолжение»), если ваш ответ кажется правильным. эта текущая проблема, вероятно, является почти частным случаем более широкой проблемы.

ВЗН

Ответы:

Другой участник удалил свой ответ, возможно, чтобы я мог расширить свой комментарий выше, так что вот оно.

Пусть возможно недетерминированный преобразователь, а регулярный язык. Измените на преобразователь который проверяет, что его вход находится в (например, путем изменения набора состояний в декартово произведение наборов состояний и и изменения функции перехода так, чтобы часть состояний правильно обновляется, сохраняя при этом поведение ) $T$ $L$ $T$ $T'$ $L$ $T$ $L$ $L$ $T$

Ветвь из представляет собой последовательность $T'$ такоечто является принятие простой путь в , и каждый это сильно связная компонента состояния которой включают в себя назначение (и начало $\rho_1 C_1\rho_2 C_2 \cdots \rho_n C_n \rho_{n+1}$ $\rho_1\rho_2 \cdots \rho_{n+1}$ $T'$ $C_i$ $T'$ $\rho_i$ ). Ветвьручная,если: $\rho_{i+1}$

Длина входного пути больше или равна его выходной длины; $\rho_1\rho_2\cdots\rho_{n+1}$
Для любого , любого простого цикла в входная длина цикла больше или равна его выходной длине. $i$ $C_i$

Факт: Для любого , подразумевается если все ветви ручные. $\big[$ $x, y$ $x[T']y$ $|y| \leq |x|$ $\big]$

Доказательство довольно немедленное. Последнее свойство разрешимо (поскольку число ветвей ограничено, а количество простых циклов тоже), это показывает, что проблема вопроса разрешима.

Михаэль Кадилхак
источник

Из описания видно, что это даже разрешимо в NL (следовательно, в P), предполагая, что

задается FSA.

L

$L$

Эмиль Йержабек

Я отправил вам уведомление (извините, я не прочитал внимательно ваш комментарий перед публикацией), но, вероятно, вы не получили его после удаления ответа :-) ... но сейчас - в качестве возмещения времени - вам следует переключиться на (и решить!) этот хитрый вопрос: « Открытая задача : существует ли

и вычислимая кодировка

такая, что для всех

n \geq 1

$n \geq 1$

S_{n}

$S_n$

k \geq 1

$k \geq 1$ ,

?» :-D :-D

L_{\leq n}^{S_{n}} = L_{\leq n + k}^{S_{n}}

$L^{S_n}_{\leq n} = L^{S_n}_{\leq n+k}$

Марцио де Биаси

@ EmilJeřábek Действительно, это довольно ясно в со-NL (следовательно, в NL).

Микаэль Кадилхак

@MarzioDeBiasi Спасибо! Я действительно не видел вашего уведомления ☺ Я буду работать над возмещением вашего времени, когда у меня будет немного ☺

Микаэль Кадилхак