Асимптотика числа слов в обычном языке заданной длины

28

Для обычного языка , пусть с п ( Ь ) быть число слов в L длины п . Используя Jordan канонической форму (применительно к Неаннотированным матрицам перехода некоторого DFA для L ), можно показать , что при достаточно большой п , с п ( L ) = K Е я = 1 P я ( п ) Л н I , где Р я являются сложными полиномами и λ iLcn(L)LnLn

cn(L)=i=1kPi(n)λin,
Piλiявляются сложными "собственными значениями". (Для малых у нас могут быть дополнительные члены вида C k [ n = k ] , где [ n = k ] равно 1, если n = k, и 0 в противном случае. Они соответствуют жордановым блокам размером не менее k + 1 с Собственное значение 0. )nCk[n=k][n=k]1n=k0k+10

Это представление , кажется, подразумевает , что если бесконечен , то асимптотически, с п ( L ) ~ С п к λ п для некоторого C , λ > 0 . Однако это явно неверно: для языка L, превышающего { 0 , 1 } всех слов четной длины, c 2 n ( L ) = 2 2 n, но c 2 n + 1 ( L ) =Lcn(L)CnkλnC,λ>0L{0,1}c2n(L)=22n . Это говорит о том, что для некоторого d и для всех a { 0 , , d - 1 } либо c d m + a ( L ) = 0 для достаточно большого m, либо c d m + aC a ( d m + a ) k a λ d m + a a . Это доказано вFlajolet & Sedgewickc2n+1(L)=0da{0,,d1}cdm+a(L)=0mcdm+aCa(dm+a)kaλadm+a (Теорема V.3), которые приписывают доказательство Берстелю.

Доказательство, предоставленное Фолоулетом и Седжвиком, является в некоторой степени техническим; настолько технически, на самом деле, что они только зарисовывают это. Я попытался получить более элементарное доказательство, используя теорию Перрона-Фробениуса. Мы можем рассматривать граф перехода ДФА как орграф. Если орграф примитивен, то результат следует почти непосредственно из теоремы Перрона-Фробениуса. Если орграф неприводим, но импримитивен с индексом , то, учитывая « r- ую степень» DFA (каждый переход соответствует r символам), мы получаем тот же результат. Трудный случай, когда орграф сводим. Мы можем свести к случаю пути сильно связных компонент, а затем получить результат, оценив суммы вида m 1 +rrr (Каждая такая сумма соответствует определенному способу принятия слова, проходя через различные компоненты определенным образом.) Эта сумма, в свою очередь, может быть оценена путем точного определения наибольшего члена, который соответствуетmilogλi. Для каждого собственного значения, которое повторяетсяrраз, мы получаем дополнительный множительΘ(m r - 1 ).

m1++mk=mi=1kλimi.
milogλirΘ(mr1)

Cλim

cn(L)ddm+aCnkλnd

cn(L)

Юваль Фильмус
источник
Какое «асимптотическое свойство» вы имеете в виду, одно прямо вверху?
Рафаэль
Именно это свойство.
Юваль Фильмус
Для приводимого случая, нет ли простых комбинаторных границ (возможно, полученных с учетом подмножеств путей и мультимножеств путей)?
Андрас Саламон
Есть простые границы, но вы, вероятно, теряете там полиномиальные факторы. Существует сумма с полиномиально большим количеством слагаемых, и мы можем оценить ее, используя наибольший слагаемый. Тем не менее, это не даст нам правильную асимптотику, так как другие слагаемые затухают довольно быстро. Возможно, оценка с интегралом возможна, но это уже становится немного грязным.
Юваль Фильмус
1
как правило, поиск альтернативных или более элементарных доказательств проблем может быть очень трудным, и в основном это теоретическое упражнение ... есть ли какая-то дополнительная мотивация / bkg / application? Предлагаю перейти на другую сторону.
vzn

Ответы:

3

Набросок, который вы набросали, похоже, соответствует трактовке Ричарда Стэнли метода матричного переноса в перечислительной комбинаторике, том 1 (ссылка: стр. 573; печать: стр. 500).

Он начинает с производящей функции и распаковывает ее, рассматривая орграфы и допустимые и запрещенные факторы. Затем он абстрагируется от бесплатных моноидов, где использует уточненную версию сумм, которые вы дали для доказательства:

BABB(λ)=(IB(λ))1

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

JSS
источник
Можете ли вы указать на теорему в тексте Стэнли, дающую асимптотические оценки?
Юваль Фильмус
Я не могу найти какой-либо непосредственной, явной ссылки на Стэнли, но Флажолет и Седжвик признают его влияние на их обращение с методом матрицы переноса в разделе V.6. В частности, следствие V.1 включает предыдущие теоремы (V.7, V.8), которые, кажется, следуют вашей линии рассуждений. Похоже, они также следуют плану Стэнли, начиная с подраздела V.5, где предложение V.6 соответствует теореме Стэнли 4.7.2 и следствию 4.7.3
JSS
Я специально ищу асимптотический анализ. Точная формула для количества слов заданной длины, заданного методом матрицы переноса, - это то, что я считаю само собой разумеющимся.
Ювал Фильмус