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

10

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

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

Дано: преобразователь и регулярный язык L. Решить: верно ли, что x L , y слово, x [ T ] y означает, что | у | | х | ?TL
ИксLYИкс[T]Y|Y||Икс|

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

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

ВЗН
источник
2
ps (должен был упомянуть, как давно известно) преобразователи FSM достаточно мощны, чтобы вычислять отдельные итерации TM «мгновенных описаний» . следовательно, проблема, возможно, связана с LBA и CSL .
ВЗН
По Вы говорите о количестве выходов на входе х , верно? Не размер выходов, в этом случае это было бы довольно просто. |F(x)|x
Микаэль Кадилхак
оба слова и | F ( х ) | длина выходного слова. есть некоторые идеи, но не вижу ничего прямолинейного в данный момент, поэтому вопрос. он предположительно нетривиален из-за ϵ входов / выходов на некоторых переходах и т. д.Икс,F(Икс)|F(Икс)|ϵ
vzn
Таким образом, вы неявно предполагаете, что ваш преобразователь функционален - с точки зрения записи, мне это было непонятно :-) Так что насчёт следующего: Пусть (возможно, недетерминированный) преобразователь, а L - заданный регулярный язык. Измените T на преобразователь T ', чтобы он проверял, находится ли его вход в L , и все ли его состояния достижимы и совместно достижимы. Тогда | T ( w ) | | ш | для всех w L, если в преобразователе T нет простого циклаTLTTL|T(w)||w|wLTдля которого вход меньше, чем выход, и некоторые дополнительные легкие свойства для переходов, не появляющиеся ни в одном SCC.
Михаэль Кадилхак
Хорошо. для "вход меньше выхода" вы имеете в виду за цикл? думаю, что это стоит написать в качестве ответа. был другой способ сформулировать эту / связанную проблему с более строгими критериями, который, предположительно, нелегок (возможно), возможно, попробует еще раз («часть 2 / продолжение / продолжение»), если ваш ответ кажется правильным. эта текущая проблема, вероятно, является почти частным случаем более широкой проблемы.
ВЗН

Ответы:

8

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

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

Ветвь из представляет собой последовательность ρ 1 C 1 ρ 2T такоечто р 1 р 2р п + 1 является принятие простой путь в Т ' , и каждый из С я это сильно связная компонента T ′, состояния которой включают в себя назначение ρ i (и начало ρ iρ1C1ρ2C2ρnCnρn+1ρ1ρ2ρn+1TCiTρi ). Ветвьручная,если:ρi+1

  1. Длина входного пути больше или равна его выходной длины;ρ1ρ2ρn+1

  2. Для любого , любого простого цикла в C i входная длина цикла больше или равна его выходной длине.iCi

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

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

Михаэль Кадилхак
источник
1
Из описания видно, что это даже разрешимо в NL (следовательно, в P), предполагая, что задается FSA. L
Эмиль Йержабек
Я отправил вам уведомление (извините, я не прочитал внимательно ваш комментарий перед публикацией), но, вероятно, вы не получили его после удаления ответа :-) ... но сейчас - в качестве возмещения времени - вам следует переключиться на (и решить!) этот хитрый вопрос: « Открытая задача : существует ли и вычислимая кодировка S n такая, что для всех k 1N1SNК1 , ?» :-D :-DLNSNзнак равноLN+КSN
Марцио де Биаси
1
@ EmilJeřábek Действительно, это довольно ясно в со-NL (следовательно, в NL).
Микаэль Кадилхак
@MarzioDeBiasi Спасибо! Я действительно не видел вашего уведомления ☺ Я буду работать над возмещением вашего времени, когда у меня будет немного ☺
Микаэль Кадилхак