Может ли постоянная неоднозначность уменьшить сложность состояния обычных языков?

Мы говорим , что НКА является постоянно Неоднозначность , если существует такое , что любое слово принимается либо или (точно) путям. $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Если автомат постоянно неоднозначен при , то называется однозначным FA (UFA). $M$ $k=1$ $M$

Пусть обычный язык. $L$

Может ли какой-то постоянно неоднозначный автомат для быть меньше, чем самый маленький UFA, который принимает ? Насколько меньше это может быть? $M_c$ $L$ $L$

Может ли конечно неоднозначный автомат быть экспоненциально меньшим, чем самый маленький CFA для того же языка?

Известно, что существуют конечно неоднозначные автоматы (существует , так что каждое слово может быть принято до путями), которые экспоненциально меньше, чем наименьшая UFA для того же языка, но я не видел кое-что о постоянной неоднозначности. $k$ $k$

Кроме того, вот связанный вопрос, который я отправил здесь несколько месяцев назад.

РЕДАКТИРОВАТЬ:

Ответ Domotorp показывает, что является полиномиально сводимым к , но не затрагивает вопрос о том, можем ли мы получить это сокращение полиномиального пространства с помощью s. $CFA$ $UFA$ $CFA$

Таким образом, возникает новый вопрос: насколько меньше (линейно / квадратично / и т. Д.) по сравнению с минимальным ? для того же языка? $CFA$ $UFA$

являются

; -переходы разрешено?

ϵ

$\epsilon$

Денис

Возможно , это может быть полезно: в Kupke, Разделяющие константы из полиномиальной неоднозначности конечных автоматов следующая иерархия представлена:

я не проверял соответствующий документ , потому что он находится за платного доступа.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

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

Спасибо @MarzioDeBiasi, но, к сожалению, это не помогает (я также надеялся, когда увидел презентацию). Они используют другое обозначение, чем то, которое я использую (и я видел в разных статьях). Их «постоянная неоднозначность» - это то, что я назвал конечной двусмысленностью, поэтому связь между их Кафа и УФА была мне уже известна. Так как мое приложение подсчитывает решения проблем NPC, мой язык всегда конечен, и поэтому каждое слово принимается

путями, которые они называют «постоянными».

O (1)

$O(1)$

РБ

Мне интересно, помогает ли мое определение уменьшить сложность состояний, поскольку у меня есть CFA, который экспоненциально меньше, чем самая маленькая UFA, которую я знаю, чтобы построить, и мне было интересно, возможно ли, что для языка не существует маленькой UFA.

РБ

@ Денис, да, но поможет ли это уменьшить сложность состояния? Я бы предположил, что вы можете уменьшить количество ребер только такими ходами.

РБ

Я утверждаю , что если на каком - то языке есть CFA с с состояниями и или принятием путей для каждого слова, то есть УФА с состояний. Основная идея состоит в том, что состояния UFA являются (упорядоченными) c-кортежами состояний CFA, и он принимает, если и только если все c состояния принимают. Конечно, мы также должны убедиться, что это были действительно разные вычисления и что мы не считаем все перестановки, поэтому для них нам нужны дополнительные биты памяти. $s$ $0$ $c$ $C_ss^c$ $c!$ $C_s$

Немного более подробное описание основной идеи: если является состоянием UFA, то оно имеет переход из него (читая некоторую букву ) в состояние тогда и только тогда, когда CFA имеет переход (чтение буквы ) от к для каждого . Состояние $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ принимает, если и только если принимает для каждого . Конечно, начальное состояние UFA - это где - начальное состояние CFA. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

Проблема с вышеупомянутым состоит в том, что моделируемые пробеги CFA могли бы быть тем же самым. Таким образом , мы добавим некоторую дополнительную информацию, закодированную, скажем, в графе на вершин, имеет ребро между вершиной и вершина , если во время запуска до сих пор , по крайней мере , когда мы имели , что . $c$ $c$ $i$ $j$ $c_i\ne c_j$

$c!$ $i$ $j$ $i$

domotorp
источник

Спасибо за ваш ответ @domotorp. К сожалению, я не могу сказать, что понимаю это. Можете ли вы дать более подробную информацию (например, как будет закодировано доказательство первичности?). Благодарность !

РБ

Я так или иначе понял, что для этого языка также есть UFA, так что забудьте об этом. Как насчет оставшейся части моего ответа?

Домоторп

M

$M$

k = c

$k=c$

c

$c$

w

$w$ , just that only

c

$c$ of them will end in an accepting state. What would the states of the UFA be? Can you please try to formalize it?

R B

There you go, I hope now it's clear.

domotorp

Может ли постоянная неоднозначность уменьшить сложность состояния обычных языков?

Кроме того, вот связанный вопрос, который я отправил здесь несколько месяцев назад.

Ответы: