Языки, распознаваемые DFA полиномиального размера

23

Для фиксированного конечного алфавита , формальный язык над является регулярным , если существует детерминированный конечный автомат (ДКА) над , которая принимает ровно .L ΣΣLΣLΣL

Я интересуюсь языками, которые «почти» регулярны в том смысле, что они могут распознаваться автоматическими семействами размеров, которые растут только полиномиально с длиной слова.

Формально, позвольте мне сказать , что формальный язык является признанным на DFA семьи , если для каждого слова , что позволяет, находится в если принимает (независимо от того, принимают ли другие это или нет), и позвольте мне определить p-регулярные языки как языки, распознаваемые с помощью PTIME-вычисляемого семейства DFA полиномиального размера, а именно: многочлен P такой, что | A_n | \ leq P (n) для всех nL w Σ n = | ш | w L A n w A i(An)wΣn=|w|wLAnwAiP | A n | P ( n ) n(An)P|An|P(n)n, (Это имя, «p-регулярный», я придумал, мой вопрос состоит в том, чтобы узнать, существует ли другое имя для этого. Обратите внимание, что это не то же самое, что p-регулярные языки в смысле автоматов перестановки .)

Этот класс p-регулярных языков включает, конечно, обычные языки (просто возьмите An=A для всех n , где A - некоторый DFA, распознающий обычный язык); но это строгий надмножество: например, хорошо известно, что {anbnnN} зависит от контекста, но не является регулярным, но это p- обычный ( An просто должен посчитать n вхождений a и n вхождений b ). Однако, поскольку я требую, чтобы автоматы были DFA полиномиального размера , некоторые формальные языки (фактически некоторые языки без контекста) не являютсяр-регулярный: например, язык палиндромов не является р-регулярным, потому что, интуитивно, когда вы прочитали первую половину слова, вам нужно иметь столько разных состояний, сколько есть возможных слов, потому что вам понадобится чтобы точно соответствовать этой первой половине со второй.

Таким образом, класс p-регулярных языков является строгим надмножеством обычных языков, которое несопоставимо с языками без контекста. На самом деле, кажется, что вы даже можете получить иерархию языков, различая p-регулярные языки на основе наименьшей степени полинома для которого они -регулярны. Нетрудно построить примеры, чтобы показать, что эта иерархия строгая; хотя я пока не очень хорошо понимаю взаимодействие между этим и альтернативным определением иерархии, которое также ограничило бы сложность вычисления .P A nPPAn

Мой вопрос: был ли этот класс, который я называю р-регулярным, и связанную с ним иерархию изучаться ранее? Если да, то где и под каким именем?

(Возможная связь с полевыми или потоковыми или онлайн-алгоритмами. В терминологии потоковых алгоритмов для задач распознавания языков меня интересует класс (или иерархия) языков, которые могут иметь детерминированные однопроходные алгоритмы распознавания, используя полиномиальное число состояний (таким образом, логарифмический объем памяти), но я не нашел определения этого класса в этой статье или в связанных с ней работах. Обратите внимание, однако, что в моей формулировке проблемы длина слова известна заранее , что менее естественно в контексте потоковой передачи: при потоковой передаче вы можете видеть это как бесконечный автомат, специальный символ «конца слова» и ограничение на то, что число достижимых состояний после чтения символов является полиномиальным понnn, Я думаю, что это различие имеет значение, возможный пример: язык бинарных слов, значение которых делится на их длину, что легко для фиксированной длины, но (я предполагаю) не может быть представлено бесконечным автоматом в предыдущем смысле, потому что нет идентификации можно сделать, если длина заранее не известна.)

(Мотивация для этого p-регулярного класса заключается в том, что некоторые проблемы, такие как вероятность членства в языке для вероятностных слов, кажутся PTIME не только тогда, когда язык является регулярным, но также и когда он является p-регулярным, и я пытаюсь точно определить, при каких обстоятельствах эти проблемы поддаются решению.)

a3nm
источник
1
Argh, я не уделил должного внимания вопросу о вычислимости . Спасибо за указание на это. Я только добавил требование, что они вычислимы. Надеемся, что нет плохих ситуаций с p-регулярными языками, в которых нужно использовать вычислимые, но высокосложные ( A n ) семейства? (An)(An)
a3nm
1
Хорошо, я удалил "невычислимый" комментарий. Но даже с вычислимым ограничением вы все равно можете получить странные вещи, такие как: выберите и B является NEXP-полным ( A n = ∅ в противном случае). Возможно, вы можете ограничить его, добавив ограничение, что A n должно быть вычислено за полиномиальное время?!? An={1nnB}BAn=An
Марцио Де Биаси
1
Марцио: Аааа, ты прав. Для моей мотивации правильное представление о том, что являются PTIME-вычислимыми, да, поэтому я перешел к этому ... тем не менее, меня немного беспокоит, что сложность вычисления ( A n ) оказывает такое влияние на результирующий класс (потому что это означает, что это дополнительный выбор, который должен быть сделан в определении ...). Это также усложняет картину иерархии, о которой я думал. An(An)
3
2
Я не вижу, что не так с невычислимостью, что вы определяете как неоднородный языковой класс, как и многие классы схем.
domotorp
3
Если вы укрепите условие единообразия для пространства журналов, то все такие языки будут вычислимы в пространстве журналов. Согласно приведенному определению, все p-регулярные языки находятся в «P-равномерном L» (распознаваемом по P-равномерному семейству программ ветвления или по пространству журналов TM с p-вычисляемым советом).
Эмиль Йержабек поддерживает Монику

Ответы:

3

вопрос, кажется, мало изучен (одна возможность - попытаться найти связь с «соседним» классом сложности, скажем, P / poly и т. д.); хотя здесь есть хотя бы одна ссылка, касающаяся этого:

  • Языковые операции с регулярными выражениями полиномиального размера Gruber / Holzer

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

n

ВЗН
источник
4
Хотя это явно не указано там, доказательство основного результата следующей статьи подразумевает, что класс p-регулярных языков не содержится в монотонном NC ^ 1. Х. Грубер и Дж. Йоханнсен: «Оптимальные нижние границы для размера регулярного выражения с использованием сложности связи», FoSSaCS 2008, LNCS 4962, с. 273-286. hermann-gruber.com/data/fossacs08.pdf
Герман Грубер
1
Приложение, натолкнулось на эту кандидатскую диссертацию 2010 Классы сложности конечных автоматов / Краловича, которые определяют что-то похожее на то, что запрашивается для p11 «маленькие языки». Кажется, что это всесторонний обзор этой общей области и строит общие теоретические рамки / абстракции связанных понятий. однако не вижу много теорем, непосредственно относящихся к определенному классу «семейств DFA размера P».
vzn
1
@vzn: определение в p11 тезиса Краловича немного отличается, потому что оно касается языковых семейств, тогда как в моем вопросе различные языки - это слова фиксированной длины, взятые только из одного основного языка. Я не уверен ни в связи с вашей работой Грубера и Хольцера, я не понимаю, как в моем вопросе вы могли бы подумать, что автоматы являются результатом операций по сохранению регулярности в целом. Что касается Gawrychowski и др., Я согласен, что это может быть тангенциально связано.
a3nm
2
ссылка Грубера / Хольцера, кажется, помогает с идеей P-регулярных редукций относительно свойств типа "P-регулярное замыкание". согласился, что твой ответ кажется другим, чем что-либо еще изученное. другими словами, есть предположительно сокращения между некоторыми из этих проблем / классов, и ссылки идут в этих направлениях, и можно искать похожие на редукцию операции, которые связывают ваше определение с ранее изученными / опубликованными классами (согласие, что ваше определение не подразумевает какого-либо конкретного сокращение операций). может быть, строгий ответ на ваш вопрос «нет, ваш класс не был изучен точно»
vzn