Квадратичная связь между недетерминированным и детерминированным пространством?

16

Теорема Савича показывает, что для всех достаточно больших функций , и доказательство того, что это тесно, является открытой проблемой на протяжении десятилетий ,NSPACE(f(n))DSPACE(f(n)2)f

Предположим, мы подходим к проблеме с другого конца. Для простоты предположим булев алфавит. Объем пространства, используемого ТМ для выбора вычислимого языка, часто тесно связан с логарифмом числа состояний, используемых автоматом, моделирующим ТМ, для каждого регулярного фрагмента языка. Это мотивирует следующий вопрос.

Пусть - количество синтаксически различных DFA с состояниями, а - количество различных NFA с состояниями. Нетрудно показать, что близко к .DnnNnnlgNn(lgDn)2

Кроме того, пусть будет числом различных регулярных языков, которые могут быть распознаны DFA с состояниями, и пусть будет числом, распознанным NFA.DnnNn

Известно ли, что близко к ?lgNn(lgDn)2

Мне не ясно, как и , или и , связаны друг с другом или насколько тесно. Если все это относится к общеизвестному вопросу в теории автоматов, то будет полезен намек или указатель. Этот же вопрос актуален и для двусторонних автоматов по той же причине, и я особенно заинтересован в этой версии.DnDnNnNn

Андраш Саламон
источник
См. Также соответствующий вопрос cstheory.stackexchange.com/q/7913/109
Саламон,

Ответы:

18

В моей статье с Домарацки и Кисманом «О количестве различных языков, принимаемых конечными автоматами с n состояниями», опубликованной в J. Automata, Languages ​​and Combinatorics 7 (2002), мы доказали, что если есть число отдельные языки, принятые NFA с n состояниями в алфавите k- буквы, и g k ( n ) аналогично числу различных языков, принятых DFA, тогда для фиксированных k 2Gk(n)nkgk(n)k2

(i) асимптотически с точностью до порядка меньшего порядка k n log nloggk(n)knlogn

(ii) , с точностью до членов меньшего порядка, асимптотически между ( k - 1 ) n 2 и k n 2 .logGk(n)(k1)n2kn2

Джеффри Шаллит
источник
Препринт: cs.umanitoba.ca/~mdomarat/pubs/enum_jalc.pdf
Саламон,