Какое минимальное расширение FO охватывает класс регулярных языков?

Контекст: отношения между логикой и автоматами

Теорема Бучи гласит, что монадическая логика второго порядка над строками (MSO) охватывает класс регулярных языков. Фактически доказательство показывает, что экзистенциальный MSO ( или EMSO ) над строками достаточен для захвата обычных языков. Это может быть немного удивительно, так как над общими структурами MSO строго более выразителен, чем . $\exists\text{MSO}$ $\exists\text{MSO}$

Мой (оригинальный) вопрос: минимальная логика для обычных языков?

Существует ли логика, которая по сравнению с общими структурами строго менее выразительна, чем , но которая все еще охватывает класс регулярных языков при рассмотрении над строками? $\exists\text{MSO}$

В частности, я хотел бы знать, какой фрагмент регулярных языков захватывается FO по строкам при расширении оператором с наименьшей фиксированной точкой (FO + LFP). Это кажется естественным кандидатом на то, что я ищу (если это не ). $\exists\text{MSO}$

Первый ответ

Согласно ответу @ makoto-kanazawa , FO (LFP) и FO (TC) захватывают больше, чем обычные языки, где TC является оператором транзитивного замыкания бинарных отношений. Еще неизвестно, может ли TC быть заменен другим оператором или набором операторов таким образом, чтобы расширение захватывало ровно класс обычных языков, и никакие другие.

Одной логики первого порядка, как мы знаем, недостаточно, поскольку она захватывает языки без звезд, надлежащий подкласс обычных языков. Как классический пример, паритет языка нельзя выразить с помощью предложения FO. $\;\;=(aa)^*$

Обновленный вопрос

Вот новая формулировка моего вопроса, которая остается без ответа.

Каково минимальное расширение логики первого порядка, такое, что FO + это расширение, когда принимается над строками, точно захватывает класс регулярных языков?

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

reference-request lo.logic regular-language finite-model-theory Janoma
источник

μ

$\mu$

μ

$\mu$

По-видимому, это доказано в dx.doi.org/10.1109/LICS.1988.5137 для бесконечного дерева и в dx.doi.org/10.1007/3-540-61604-7_60 для эквивалентности с инвариантным к бисимуляции фрагментом MSO над произвольными структурами.

Сильвен

Я смотрю на вторую статью, хотя боюсь, что многие концепции для меня новы. В частности, я не знал о бисимуляционно-инвариантных переходных системах. Похоже, что DFA являются частными случаями переходной системы, но я не знаю, являются ли они инвариантными по бисимуляции. Если бы они были, это ответило бы на часть моего вопроса (могла бы быть еще одна менее выразительная логика для обычных языков); в противном случае, я думаю, ничего нельзя сказать, поскольку при рассмотрении только строк может существовать эквивалентность.

Янома

a_{1} \dots a_{n}

$a_1\cdots a_n$

Σ^{*}

$\Sigma^\ast$

Σ = 2^{P r o p}

$\Sigma=2^{\mathit{Prop}}$

⟨ {1, \dots, n}, 1, {(i, i + 1) ∣ i < n}, {i ∣ p \in a_{i}}_{p \in P r o p} ⟩

$\langle\{1,\dots,n\},1,\{(i,i+1)\mid i<n\},\{i\mid p\in a_i\}_{p\in\mathit{Prop}}\rangle$

FO (LFP) захватывает PTIME для упорядоченных структур, а строки - упорядоченные структуры. Таким образом, языки, определяемые FO (LFP), включают в себя все обычные языки и многое другое. http://dx.doi.org/10.1016/S0019-9958(86)80029-8

$\{ a^n b^n \mid n \geq 1 \}$

Макото Канадзава
источник

Отлично. Я не знаю, что вы подразумеваете под TC ^ 1 и TC ^ 2, это опечатка? Насколько я знаю, в книге вы упоминаете обозначение FO (TC) для расширения FO с транзитивным замыканием и FO (DTC) для расширения FO с детерминированным транзитивным замыканием , которое определяется по-разному. Однако я не нашел упомянутое вами упражнение. Осталось выяснить, есть ли оператор менее выразительный, чем TC, который все еще позволяет фиксировать обычные языки. Я обновлю свой вопрос соответственно.

Janoma

Какое минимальное расширение FO охватывает класс регулярных языков?

Контекст: отношения между логикой и автоматами

Мой (оригинальный) вопрос: минимальная логика для обычных языков?

Первый ответ

Обновленный вопрос

Ответы: