Максимальное количество минимальных значений DFA

Позволять $\Sigma$ быть алфавитом размера $2$ и рассмотрим минимальные DFA, размер которых ограничен не более $m$ , Позволять $f(m)$ обозначим количество различных таких минимальных ДФА.

Можем ли мы найти формулу замкнутой формы для $f(m)$ ?

Учитывая, что для $|\Sigma|=2$ функция перехода DFA размера не более $m$ это график. Поскольку степень узлов ограничена $2$ для каждого узла есть $m^2$ Возможности пар дуг (как это предлагается в комментариях). На этом графике не более $m$ возможные варианты исходного состояния и не более $2^m$ возможные варианты выбора конечных состояний. Таким образом, максимальное количество DFA размером не более $m$ является $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$ ,

Мы можем обобщить на произвольный алфавит $\Sigma$ : граница становится $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$ ,

Но мы ограничили здесь произвольные DFA, и я заинтересован в ограничении количества минимальных DFA. Таким образом, похоже, что эта граница может быть более жесткой ... У кого-то есть лучшая оценка?

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

cc.complexity-theory automata-theory nondeterminism dfa Luz
источник

Я не думаю, что ваша верхняя граница верна. Похоже, так и должно быть

f (m) \leq m \times 2^{m} \times m^{2 m}

$f(m) \le m \times 2^m \times m^{2m}$ , скорее, чем

f (m) \leq m \times 2^{m} \times 2^{2 m}

$f(m) \le m \times 2^m \times 2^{2m}$ , Для каждого узла рассмотрим две дуги, выходящие из этого узла; есть

m

$m$ возможности, где идет первая дуга, и

m

$m$ возможности, где идет вторая дуга, так

m^{2}

$m^2$ Всего возможностей. Есть

m

$m$ узлы, поэтому мы получаем

(m^{2})^{m} = m^{2 m}

$(m^2)^m = m^{2m}$ возможности для множества дуг. Обобщение будет

f (m) \leq m \times 2^{m} \times m^{| Σ | m}

$f(m) \le m \times 2^m \times m^{|\Sigma| m}$ ,

Вот ссылка, которая может быть полезна: «О ЧИСЛЕ РАЗЛИЧНЫХ ЯЗЫКОВ, ПРИНЯТЫХ КОНЕЧНЫМИ АВТОМАТАМИ С n ГОСУДАРСТВАМИ» - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838

Майкл Вехар,

Спасибо вам обоим за то, что исправили мою ошибку и дали мне эту ссылку, которая действительно является подходящей.

Луз

Ответы:

Согласно Ишигами Й., Тани С. (1993). VC-измерения конечных автоматов с n состояниями, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , VC-измерение концептуальный класс $n$ DFAs по алфавиту размера $k$ является

d = d (n, k) := (k - 1 + o (1)) n \log_{2} n .

$d=d(n,k) := (k-1+o(1))n\log_2 n.$ Отсюда следует, что есть как минимум

2^{d}

$2^d$ отчетливый

n

$n$ автоматы на

k

$k$ алфавит Верхняя граница числа таких автоматов вытекает из простого счетного аргумента (приведенного в статье) и составляет не более

2^{d}

$2^d$ ,

Арье
источник

Спасибо. Я понимаю из вашего ответа, что есть

m^{(| Σ | - 1 + o (1)) m}

$m^{(|\Sigma| - 1 + o(1)) m}$

m

$m$ DFAs-состояний (по крайней мере и самое большее). Но я заинтересован в подсчете минимальных значений DFA. Таким образом, ваша верхняя граница не противоречит приведенной в моем ответе, верно?

Луз

Я думаю, что это также учитывает минимальное количество DFA, поскольку VC-измерение не зависит от представления, оно фактически учитывает разные языки, которые соответствуют минимальным DFA.

Арье

оу :( тогда ваша граница противоречит моей ... так как у моей большой знаменатель

(m - 1)!

$(m-1)!$ что делает его намного ниже твоего ... как получилось ??

Луз

Я не вижу противоречия - большой знаменатель

(m - 1)!

$(m-1)!$ все еще завален

m^{m}

$m^m$ в числителе.

Арье

На самом деле, если вы посмотрите на доказательство Thm. 3.2 в статье, которую я связал, вы увидите это точное выражение в знаменателе.

Арье

(Примечание: верхняя граница, указанная в принятом ответе, лучше или равна приведенной здесь)

Верхняя граница предложена в этой статье, приведенной в одном из предыдущих комментариев: « О количестве различных языков, принимаемых конечными автоматами с n состояниями » (2002, М. Домарацки, Д. Кисман, Дж. Шаллит) .

В этом документе:

$f_{|\Sigma|}(m)$ Функция обеспечивает количество различных неизоморфных минимальных DFA с $m$ -состояния более ${|\Sigma|}$ алфавит ,
$g_{|\Sigma|}(m)$ Функция дает количество различных языков, принятых DFA с $m$ говорится более ${|\Sigma|}$ -Письмо алфавит .

Нас интересует верхняя граница для $g_{|\Sigma|}(m)$ функция, так как мой вопрос задать верхнюю границу для количества минимальных DFA с не более $m$ состояния (и не совсем $m$ ).

Что я понимаю со страницы $6$ ниже теорема $8$ в том, что $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ что лучше, чем тот, который указан в моем вопросе (т.е. $2^m\cdot m^{|\Sigma|m+1}$ ). Это частично отвечает на мой вопрос.

Но в статье утверждается, что эта верхняя граница тривиальна и может быть улучшена. Тем не менее, улучшение касается только $f_{|\Sigma|}(m)$ (насколько я понимаю).

Luz
источник