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

9

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

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

Учитывая, что для |Σ|=2 функция перехода DFA размера не более mэто график. Поскольку степень узлов ограничена2для каждого узла есть m2Возможности пар дуг (как это предлагается в комментариях). На этом графике не болееm возможные варианты исходного состояния и не более 2mвозможные варианты выбора конечных состояний. Таким образом, максимальное количество DFA размером не болееm является f(m)m2mm2m=2mm2m+1,

Мы можем обобщить на произвольный алфавит Σ: граница становится f(m)2mm|Σ|m+1,

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

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

Luz
источник
1
Я не думаю, что ваша верхняя граница верна. Похоже, так и должно бытьf(m)m×2m×m2m, скорее, чем f(m)m×2m×22m, Для каждого узла рассмотрим две дуги, выходящие из этого узла; естьm возможности, где идет первая дуга, и m возможности, где идет вторая дуга, так m2Всего возможностей. Естьm узлы, поэтому мы получаем (m2)m=m2mвозможности для множества дуг. Обобщение будетf(m)m×2m×m|Σ|m,
DW
4
Вот ссылка, которая может быть полезна: «О ЧИСЛЕ РАЗЛИЧНЫХ ЯЗЫКОВ, ПРИНЯТЫХ КОНЕЧНЫМИ АВТОМАТАМИ С n ГОСУДАРСТВАМИ» - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838
Майкл Вехар,
2
Спасибо вам обоим за то, что исправили мою ошибку и дали мне эту ссылку, которая действительно является подходящей.
Луз

Ответы:

7

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

d=d(n,k):=(k1+o(1))nlog2n.
Отсюда следует, что есть как минимум 2d отчетливый nавтоматы на kалфавит Верхняя граница числа таких автоматов вытекает из простого счетного аргумента (приведенного в статье) и составляет не более2d,
Арье
источник
Спасибо. Я понимаю из вашего ответа, что естьm(|Σ|1+o(1))m mDFAs-состояний (по крайней мере и самое большее). Но я заинтересован в подсчете минимальных значений DFA. Таким образом, ваша верхняя граница не противоречит приведенной в моем ответе, верно?
Луз
Я думаю, что это также учитывает минимальное количество DFA, поскольку VC-измерение не зависит от представления, оно фактически учитывает разные языки, которые соответствуют минимальным DFA.
Арье
оу :( тогда ваша граница противоречит моей ... так как у моей большой знаменатель (m1)!что делает его намного ниже твоего ... как получилось ??
Луз
Я не вижу противоречия - большой знаменатель (m1)! все еще завален mmв числителе.
Арье
На самом деле, если вы посмотрите на доказательство Thm. 3.2 в статье, которую я связал, вы увидите это точное выражение в знаменателе.
Арье
4

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

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

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

  • f|Σ|(m)Функция обеспечивает количество различных неизоморфных минимальных DFA сm-состояния более |Σ|алфавит ,
  • g|Σ|(m)Функция дает количество различных языков, принятых DFA сm говорится более |Σ|-Письмо алфавит .

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

Что я понимаю со страницы 6 ниже теорема 8 в том, что g|Σ|(m)2mm|Σ|m(m1)! что лучше, чем тот, который указан в моем вопросе (т.е. 2mm|Σ|m+1). Это частично отвечает на мой вопрос.

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

Luz
источник