Обычный числовой предикат

В информатике и математике , точнее в теории автоматов , теории моделей и формальном языке , регулярный числовой предикат — это своего рода отношение над целыми числами. Обычные числовые предикаты также можно рассматривать как подмножество $\mathbb {N} ^{r}$ для некоторой арности $r$ . Одним из основных преимуществ этого класса предикатов является то, что его можно определить множеством разных способов, используя разные логические формализмы. Более того, большинство определений используют только базовые понятия и, таким образом, позволяют связать основы различных областей фундаментальной информатики, таких как теория автоматов , синтаксическая полугруппа , теория моделей и теория полугрупп .

Класс регулярного числового предиката обозначается ${\mathcal {C}}_{lca}$ , ^[1]^: 140 ${\mathcal {N}}_{\mathtt {thres,mod}}$ ^[2] и РЕГ. ^[3]

Определения

Класс регулярных числовых предикатов допускает множество эквивалентных определений. Их теперь дают. Во всех этих определениях мы фиксируем $r\in \mathbb {N}$ и $P\subseteq \mathbb {N} ^{r}$ (числовой) предикат арности $r$ .

Автоматы с переменными

Первое определение кодирует предикат как формальный язык . Предикат называется регулярным, если формальный язык регулярен . ^[3]^: 25

Пусть алфавит $A$ быть набором подмножества $\{1,\dots ,r\}$ . Учитывая вектор $r$ целые числа $\mathbf {n} =(n_{0},\dots ,n_{r-1})\in \mathbb {N} ^{r}$ , оно представлено словом ${\overline {\mathbf {n} }}$ длины $\max(n_{0},\dots ,n_{r-1})$ чей $i$ -я буква $\{j\mid n_{j}=i\}$ . Например, вектор $(3,1,3)$ представлено словом $\emptyset \{1\}\emptyset \{0,2\}$ .

Затем мы определяем ${\overline {P}}$ как $\{{\overline {\mathbf {n} }}\mid \mathbf {n} \}$ .

Числовой предикат $P$ называется регулярным, если ${\overline {P}}$ это обычный язык над алфавитом $A$ . Это причина использования слова «регулярный» для описания такого рода числового предиката.

Автоматы, читающие унарные числа

Это второе определение аналогично предыдущему. Предикаты кодируются в языках по-другому, и предикат называется регулярным тогда и только тогда, когда язык регулярен. ^[3]^: 25

Наш алфавит $A$ представляет собой набор векторов $r$ двоичные цифры. То есть: $\{0,1\}^{r}$ . Прежде чем объяснить, как закодировать вектор чисел, мы объясним, как закодировать одно число.

Учитывая длину $l$ и номер $n\leq l$ , унарное представление $n$ длины $l$ это слово $\mid {n}\mid _{l}$ над двоичным алфавитом $\{0,1\}$ , начиная с последовательности $n$ «1», за которым следует $n-l$ «0». Например, унарное представление числа 1 длины 4 равно $1000$ .

Учитывая вектор $r$ целые числа $\mathbf {n} =(n_{0},\dots ,n_{r-1})\in \mathbb {N} ^{r}$ , позволять $l=\max(n_{0},\dots ,n_{r-1})$ . Вектор $\mathbf {n}$ представлено словом ${\overline {\mathbf {n} }}\in \left(\{0,1\}^{r}\right)^{*}$ такая, что проекция ${\overline {\mathbf {n} }}$ над своим $i$ -й компонент $\mid {n_{i}}\mid _{\max(n_{0},\dots ,n_{r-1})}$ . Например, представление $(3,1,3)$ является ${\begin{array}{l|l|l}1&1&1\\1&0&0\\1&1&1\end{array}}$ . Это слово, буквы которого являются векторами $(1,1,1)$ , $(1,0,1)$ и $(1,0,1)$ и чьи проекции на каждый компонент равны $111$ , $100$ и $111$ .

Как и в предыдущем определении, числовой предикат $P$ называется регулярным, если ${\overline {P}}$ это обычный язык над алфавитом $A$ .

$(\exists )MSO(+1)$

Предикат является регулярным тогда и только тогда, когда он может быть определен второго порядка . монадической формулой $\phi (x_{0},\dots ,x_{r-1})$ или, что то же самое, с помощью экзистенциальной монадической формулы второго порядка, где единственным атомарным предикатом является функция-преемник $y+1=z$ . ^[3]^: 26

$FO(\leq ,\mod )$

Предикат является регулярным тогда и только тогда, когда его можно определить с помощью логической формулы первого порядка. $\phi (x_{0},\dots ,x_{r-1})$ , где атомарные предикаты:

отношение порядка $y\leq z$ ,
предикат, утверждающий, что число кратно константе $m$ , то есть $y\equiv 0\mod m$ . ^[3]^: 26

Сравнение арифметики

Язык конгруэнтной арифметики ^[1]^: 140 определяется как лучшая из логических комбинаций, где атомарными предикатами являются:

добавление константы $x_{i}+c=x_{j}$ , с $c$ целая константа,
отношение порядка $x_{i}\leq x_{j}$ ,
модульные отношения с фиксированным модульным значением. То есть предикаты вида $x_{i}\equiv c\mod m$ где $c$ и $m$ являются фиксированными константами и $x$ является переменной.

Предикат является регулярным тогда и только тогда, когда его можно определить на языке конгруэнтной арифметики. Эквивалентность предыдущему определению обусловлена исключением квантора. ^[4]

Использование рекурсии и шаблонов

Это определение требует фиксированного параметра $m$ . Множество называется регулярным, если оно $m$ -обычно для некоторых $m\geq 2$ . Для того, чтобы ввести определение $m$ -regular , тривиальный случай, когда $r=0$ следует рассматривать отдельно. Когда $r=0$ , то предикат $P$ является либо константой true, либо константой false. Говорят, что эти два предиката $m$ -регулярный (для каждого $m$ ). Давайте теперь предположим, что $r\geq 1$ . Чтобы ввести определение регулярного предиката в этом случае, нам необходимо ввести понятие сечения предиката .

Раздел $P^{x_{i}=c}$ из $P$ является предикатом арности $r-1$ где $i$ -й компонент зафиксирован $c$ . Формально это определяется как $\{(x_{0},\dots ,x_{i-1},x_{i+1},\dots ,x_{r-1})\mid P(x_{0},\dots ,x_{i-1},c,x_{i+1},\dots ,x_{r-1})\}$ . Например, рассмотрим предикат суммы $S=\{(n_{0},n_{1},n_{2})\mid n_{0}+n_{1}=n_{2}\}$ . Затем $S^{x_{0}=c}=\{(n_{1},n_{2})\mid c+n_{1}=n_{2}\}$ это предикат, который добавляет константу $c$ , и $S^{x_{2}=c}=\{(n_{0},n_{1})\mid n_{0}+n_{1}=c\}$ предикат, который утверждает, что сумма двух его элементов равна $c$ .

Теперь можно дать последнее эквивалентное определение регулярного предиката. Предикат $P$ арности $r\geq 1$ является $m$ -регулярный, если он удовлетворяет двум следующим условиям: ^[5]

все его разделы $m$ -обычный,
существует порог $t\in \mathbb {N}$ такая, что для каждого вектора $(n_{0},\dots ,n_{r})\in \mathbb {N} ^{r}$ с каждым $n_{i}\geq t$ , $P(n_{0},\dots ,n_{r})\iff P(n_{0}+m,\dots ,n_{r}+m)$ .

Второе свойство интуитивно означает, что если числа достаточно велики, их точное значение не имеет значения. Свойства, которые имеют значение, - это отношение порядка между числами и их значением по модулю периода. $m$ .

Использование узнаваемых полугрупп

Учитывая подмножество $s\subseteq \{0,\dots ,r-1\}$ , позволять ${\overline {s}}$ быть характеристическим вектором $s$ . То есть вектор в $\{0,1\}^{r}$ чей $i$ -й компонент равен 1, если $i\in s$ , и 0 в противном случае. Учитывая последовательность $\mathbf {s} =s_{0}\subsetneq \dots \subsetneq s_{p-1}$ наборов, пусть $P_{\mathbf {s} }=\{(n_{0},\dots ,n_{p-1})\in \mathbb {N} ^{p}\mid P(\sum n_{i}e_{i})\}$ .

Предикат $P$ является регулярным тогда и только тогда, когда для каждой возрастающей последовательности множества $\mathbf {s}$ , $P_{\mathbf {s} }$ является узнаваемым субмоноидом $\mathbb {N} ^{p}$ . ^[2]

Определение нерегулярного языка

Предикат $P$ является регулярным тогда и только тогда, когда все языки, которые можно определить в логике первого порядка с атомарными предикатами для букв и атомарным предикатом $P$ являются регулярными. То же самое свойство справедливо для монадической логики второго порядка и модульных кванторов. ^[1]

Уменьшение арности

Следующее свойство позволяет свести сколь угодно сложный нерегулярный предикат к более простому двоичному предикату, который также не является регулярным. ^[5]

Предположим, что $P$ определимо в арифметике Пресбургера. Предикат $P$ нерегулярна тогда и только тогда, когда существует формула в $\mathbf {FO} [\leq ,R]$ которое определяет умножение на рациональное ${\frac {p}{q}}\not \in \{0,1\}$ . Точнее, это позволяет определить нерегулярный предикат $\{(p\times n,q\times n)\mid n\in \mathbb {N} \}$ для некоторых $p\not \in {0,q}$ .

Характеристики

Класс регулярных числовых предикатов обладает многими свойствами.

Удовлетворенность

Как и в предыдущем случае, предположим, что $P$ определимо в арифметике Пресбургера. Выполнимость $\exists \mathbf {MSO} (+1,P)$ разрешимо тогда и только тогда, когда $P$ является регулярным.

Эта теорема обусловлена предыдущим свойством и тем фактом, что выполнимость $\exists \mathbf {MSO} (+1,\times {\frac {p}{q}})$ неразрешимо, когда $p\neq 0$ и $p\neq q$ . ^{[ нужна ссылка ]}

Закрытие свойства

Класс регулярных предикатов замкнут относительно объединения, пересечения, дополнения, сечения, проекции и декартова произведения. Все эти свойства следуют непосредственно из определения этого класса как класса предикатов, определяемых в $\mathbf {FO} (\leq ,\mod )$ . ^{[ нужна ссылка ]}

Разрешимость

Можно решить, является ли предикат, определенный в арифметике Пресбургера, регулярным. ^[2]

Удаление квантора

Логика $\mathbf {FO} (\leq ,+c,\mod )$ рассмотренные выше допускают устранение квантора. Точнее, алгоритм устранения квантора Купера ^[6] не вводит умножение на константы и суммы переменных. Поэтому применительно к $\mathbf {FO} (\leq ,+c,\mod )$ он возвращает формулу без кванторов в $\mathbf {FO} (\leq ,+c,\mod )$ .

Ссылки

^ Jump up to: ^а ^б ^с Пеладо, Пьер (1992). «Формулы, регулярные языки и логические схемы». Теоретическая информатика . 101 : 133–142. дои : 10.1016/0304-3975(92)90152-6 .
^ Jump up to: ^а ^б ^с Шоффрут, Кристиан (январь 2008 г.). «Решение, может ли отношение, определенное в логике Пресбургера, быть определено в более слабой логике» . РАЙРО — Теоретическая информатика и приложения . 42 (1): 121–135. дои : 10.1051/ita:2007047 .
^ Jump up to: ^а ^б ^с ^д ^и Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Биркхазер. ISBN 978-1-4612-0289-9 .
^ Сморинский, Крейг А. (1991). Теория логических чисел. 1., введение . Спрингер. п. 322. ИСБН 978-3-642-75462-3 .
^ Jump up to: ^а ^б Мильчиор, Артур (январь 2017 г.). «Неразрешимость выполнимости разложений FO [<] с полулинейным нерегулярным предикатом над словами». Природа вычислений : 161–170.
^ Купер, округ Колумбия (1972). «Доказательство теорем в арифметике без умножения». Машинный интеллект . 7 : 91–99.

[Peladeau-1] Jump up to: ^а ^б ^с Пеладо, Пьер (1992). «Формулы, регулярные языки и логические схемы». Теоретическая информатика . 101 : 133–142. дои : 10.1016/0304-3975(92)90152-6 .

[Choffrut-2] Jump up to: ^а ^б ^с Шоффрут, Кристиан (январь 2008 г.). «Решение, может ли отношение, определенное в логике Пресбургера, быть определено в более слабой логике» . РАЙРО — Теоретическая информатика и приложения . 42 (1): 121–135. дои : 10.1051/ita:2007047 .

[Straubing-3] Jump up to: ^а ^б ^с ^д ^и Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Биркхазер. ISBN 978-1-4612-0289-9 .

[4] Сморинский, Крейг А. (1991). Теория логических чисел. 1., введение . Спрингер. п. 322. ИСБН 978-3-642-75462-3 .

[milchior-5] Jump up to: ^а ^б Мильчиор, Артур (январь 2017 г.). «Неразрешимость выполнимости разложений FO [<] с полулинейным нерегулярным предикатом над словами». Природа вычислений : 161–170.

[Cooper-6] Купер, округ Колумбия (1972). «Доказательство теорем в арифметике без умножения». Машинный интеллект . 7 : 91–99.

[1]

[2]

[3]

[4]

[5]

[6]