Система Semi-Thue

редактировать

В теоретической информатике и математической логике a перезапись строки система (SRS ), исторически называемая полу- Thue system, представляет собой перезапись системы поверх строк из (обычно конечного ) алфавита. Учитывая бинарное отношение $R {\ displaystyle R}$ $R$ между фиксированными строками в алфавите, называемое правилами перезаписи, обозначаемое $s → t {\ displaystyle s \ rightarrow t}$ $s \ rightarrow t$ , SRS расширяет отношение перезаписи на все строки, в которых левая и правая части правил отображаются как подстроки, то есть $usv → utv {\ displaystyle usv \ rightarrow utv}$ $usv \ rightarrow utv$ , где $s {\ displaystyle s}$ $s$ , $t {\ displaystyle t}$ $t$ , $u {\ displaystyle u}$ $u$ и $v {\ displaystyle v}$ $v$ - строки.

Понятие системы полу-Туэ по существу совпадает с представлением моноида. Таким образом, они составляют естественную основу для решения проблемы слов для моноидов и групп.

SRS можно определить напрямую как абстрактную систему перезаписи. Это также можно рассматривать как ограниченный вид системы переписывания терминов. В качестве формализма системы перезаписи строк полны по Тьюрингу. Название полу-Туэ происходит от норвежского математика Акселя Туэ, который представил систематическое рассмотрение систем перезаписи строк в статье 1914 года. Туэ ввел это понятие в надежде решить проблему слов для конечно определенных полугрупп. Только в 1947 году проблема оказалась неразрешимой - этот результат независимо друг от друга получили Эмиль Пост и А. А. Марков-младший

Содержание

1 Определение
2 Конгруэнция Туэ
3 Факторные моноиды и представления моноидов
4 Проблема слов для систем полутуэ
5 Связи с другими понятиями
6 История и значение
7 См. Также
8 Примечания
9 Ссылки
- 9.1 Монографии
- 9.2 Учебники
- 9.3 Обзоры
- 9.4 Достопримечательности

Определение

A система перезаписи строк или система полутхуэ - это кортеж $(Σ, R) {\ displaystyle (\ Sigma, R)}$ $(\ Sigma, R)$ где

Σ - алфавит, обычно предполагаемый конечным. Элементы множества $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ (* здесь звезда Клини ) являются конечными (возможно, пустыми) строками на Σ, иногда называются словами в официальных языках ; мы будем называть их здесь просто строками.
R - это бинарное отношение на строках из Σ, то есть $R ⊆ Σ ∗ × Σ ∗. {\ Displaystyle R \ substeq \ Sigma ^ {*} \ times \ Sigma ^ {*}.}$ $R \ substeq \ Sigma ^ {*} \ times \ Sigma ^ {*}.$ Каждый элемент $(u, v) ∈ R {\ displaystyle (u, v) \ in R}$ $(u, v) \ in R$ называется правилом (перезаписи) и обычно записывается как $u → v {\ displaystyle u \ rightarrow v}$ $u \ rightarrow v$ .

Если отношение R симметрично, то система называется системой Thue .

. Правила перезаписи в R могут быть естественным образом распространены на другие строки в $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ , разрешив подстроки быть переписанным в соответствии с R. Более формально, отношение одношаговой перезаписи отношение $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ вызвало на R на $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ для любых строк $s, t ∈ Σ ∗ {\ displaystyle s, t \ in \ Sigma ^ {*} }$ $s, t \ in \ Sigma ^ {*}$ :

s → R t {\ displaystyle s {\ xrightarrow [{R}] {}} t}

s {\ xrightarrow [{R}] {}} t

тогда и только тогда, когда существуют

x, y, u, v ∈ Σ ∗ {\ displaystyle x, y, u, v \ in \ Sigma ^ {*}}

x, y, u, v \ in \ Sigma ^ {*}

так, что

s = xuy {\ displaystyle s = xuy}

s=xuy

t = xvy {\ displaystyle t = xvy}

t = xvy

u → v {\ displaystyle u \ rightarrow v}

u \ rightarrow v

Поскольку $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ является отношением на $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ , пара $(Σ ∗, → R) {\ displaystyle (\ Sigma ^ {*}, { \ xrightarrow [{R}] {}})}$ $(\ Sigma ^ {*}, {\ xrightarrow [{R}] {}})$ соответствует определению абстрактной системы перезаписи. Очевидно, что R является подмножеством $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ . Некоторые авторы используют другое обозначение стрелки в $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ (например, $→ R {\ displaystyle {\ xrightarrow [ {R}] {}}}$ ${\ xrightarrow [{R}] {}}$ ), чтобы отличить его от самого R ( $→ {\ displaystyle \ rightarrow}$ $\ rightarrow$ ), потому что позже они захотят иметь возможность отбрасывать нижний индекс и все же избежать путаницы между R и одношаговой перезаписью, вызванной R.

Очевидно, что в системе полутуэ мы можем сформировать (конечную или бесконечную) последовательность строк, полученную, начиная с начальной строки $s 0 ∈ Σ ∗ {\ displaystyle s_ {0} \ in \ Sigma ^ {*}}$ $s_ {0} \ in \ Sigma ^ {*}$ и многократно переписывая его, выполняя одну замену подстроки за раз:

s 0 → R s 1 → R s 2 → R… {\ displaystyle s_ {0} \ {\ xrightarrow [{R}] {}} \ s_ {1} \ {\ xrightarrow [{R}] {}} \ s_ {2 } \ {\ xrightarrow [{R}] {}} \ \ ldots}

s_0 \ \ xrightarrow [R] {} \ s_1 \ \ xrightarrow [R] {} \ s_2 \ \ xrightarrow [R] {} \ \ ldots

Подобная перезапись с нулевым или большим количеством шагов фиксируется рефлексивным транзитивным замыканием из $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ , обозначается $→ R ∗ {\ displaystyle {\ xrightarrow [{R}] {*}}}$ ${\ xrightarrow [{R}] {*}}$ (см. абстрактная система переписывания # Основные понятия ). Это называется отношением перезаписи или отношением редукции на $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ , индуцированным R.

Thue congruence

В общем, набор $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ строк в алфавите образует свободный моноид вместе с бинарной операцией конкатенации строк (обозначается как $⋅ {\ displaystyle \ cdot}$ $\ cdot$ и записывается мультипликативно путем отбрасывания символа). В SRS отношение редукции $→ R ∗ {\ displaystyle {\ xrightarrow [{R}] {*}}}$ ${\ xrightarrow [{R}] {*}}$ совместимо с операцией моноида, что означает, что $x → R ∗ y {\ displaystyle x {\ xrightarrow [{R}] {*}} y}$ $x {\ xrightarrow [{R}] {*}} y$ подразумевает $uxv → R ∗ uyv {\ displaystyle uxv {\ xrightarrow [{R}] {*} } uyv}$ $uxv {\ xrightarrow [{R}] {*}} uyv$ для всех строк $x, y, u, v ∈ Σ ∗ {\ displaystyle x, y, u, v \ in \ Sigma ^ {*}}$ $x, y, u, v \ in \ Sigma ^ {*}$ . Поскольку $→ R ∗ {\ displaystyle {\ xrightarrow [{R}] {*}}}$ ${\ xrightarrow [{R}] {*}}$ по определению является предварительным заказом, $(Σ ∗, ⋅, → R ∗) {\ displaystyle \ left (\ Sigma ^ {*}, \ cdot, {\ xrightarrow [{R}] {*}} \ right)}$ $\ left (\ Sigma ^ *, \ cdot, \ xrightarrow [R] {*} \ right)$ образует моноидальный предзаказ.

Аналогично, рефлексивное транзитивное симметричное замыкание для $→ R {\ displaystyle {\ xrightarrow [{R}] {}}}$ ${\ xrightarrow [{R}] {}}$ , обозначенное $↔ R ∗ {\ displaystyle {\ overset {*} {\ underset {R} {\ leftrightarrow}}}}$ ${ \ overset {*} {\ underset {R} {\ leftrightarrow}}}$ (см. абстрактная система переписывания # Основные понятия ), является конгруэнцией, что означает, что это отношение эквивалентности (по определению), и оно также совместимо с конкатенацией строк. Отношение $↔ R ∗ {\ displaystyle {\ overset {*} {\ underset {R} {\ leftrightarrow}}}}$ ${ \ overset {*} {\ underset {R} {\ leftrightarrow}}}$ называется конгруэнцией Туэ, сгенерированной R. В системе Туэ, т.е. если R симметрично, отношение перезаписи $→ R ∗ {\ displaystyle {\ xrightarrow [{R}] {*}}}$ ${\ xrightarrow [{R}] {*}}$ совпадает с конгруэнцией Туэ $↔ R ∗ {\ displaystyle {\ overset {*} {\ underset {R} {\ leftrightarrow}}}}$ ${ \ overset {*} {\ underset {R} {\ leftrightarrow}}}$ .

Фактор моноида и представления моноида

Начиная с $↔ R ∗ {\ displaystyle {\ overset {*} {\ underset {R} {\ leftrightarrow}}}}$ ${ \ overset {*} {\ underset {R} {\ leftrightarrow}}}$ является конгруэнцией, мы можем определить факторный моноид $MR = Σ ∗ / ↔ R ∗ {\ displaystyle {\ mathcal {M}} _ {R} = \ Sigma ^ {*} / {\ overset {*} {\ underset {R} {\ leftrightarrow}}}}$ ${\ mathcal {M}} _ {R} = \ Sigma ^ {*} / {\ overset {*} {\ underset {R} {\ leftrightarrow}}}$ из свободный моноид $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ в соответствии с конгруэнцией Туэ в обычной манере. Если моноид $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ изоморфен с $MR {\ displaystyle {\ mathcal {M}} _ {R }}$ ${\ mathcal {M}} _ {R}$ , тогда система полу-Туэ $(Σ, R) {\ displaystyle (\ Sigma, R)}$ $(\ Sigma, R)$ называется моноидным представлением of $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ .

Мы сразу получаем очень полезные связи с другими областями алгебры. Например, алфавит {a, b} с правилами {ab → ε, ba → ε}, где ε - пустая строка, представляет собой представление свободной группы на один генератор. Если вместо этого правила просто {ab → ε}, то мы получаем представление бициклического моноида.

. Важность полутонных систем как представления моноидов усиливается следующим:

Теорема : каждый моноид имеет представление формы $(Σ, R) {\ displaystyle (\ Sigma, R)}$ $(\ Sigma, R)$ , поэтому он всегда может быть представлен системой полутуэ, возможно над бесконечным алфавитом.

В этом контексте набор $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ называется набором генераторов из $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ и $R {\ displaystyle R}$ $R$ называется набором определяющих отношений $М {\ Displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ . Мы можем сразу же классифицировать моноиды на основе их представления. $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ называется

конечно порожденным, если $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ конечно.
конечно представленный, если оба $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ и $R {\ displaystyle R}$ $R$ конечны.

Проблема слов для систем полутуэ

Проблема слов для систем полутуэ может быть сформулирована следующим образом: Для данной системы полутуэ $T: = (Σ, R) {\ displaystyle T: = (\ Sigma, R)}$ $T: = (\ Sigma, R)$ и два слова (строки) $u, v ∈ Σ ∗ {\ displaystyle u, v \ in \ Sigma ^ {*}}$ $и, v \ in \ Sigma ^ {*}$ , можно $u {\ displaystyle u}$ $u$ преобразовать в $v {\ displaystyle v}$ $v$ , применив правила из $R {\ displaystyle R}$ $R$ ? Эта проблема неразрешима, т.е. нет общего алгоритма решения этой проблемы. Это справедливо даже в том случае, если мы ограничиваем ввод конечными системами.

Мартин Дэвис предлагает обычному читателю двухстраничное доказательство в своей статье «Что такое вычисления?» С. 258–259 с комментарием с. 257. Дэвис формулирует доказательство следующим образом: «Придумайте [словесную проблему], решение которой приведет к решению проблемы остановки ».

Связи с другими понятиями

Система полу-Туэ также является системой переписывания терминов - система, имеющая монадические слова (функции), заканчивающиеся в той же переменной, что и члены левой и правой части, например термин правило $f 2 (f 1 (x)) → g (x) {\ displaystyle f_ {2} (f_ {1} (x)) \ rightarrow g (x)}$ $f_ {2} (f_ {1} (x)) \ rightarrow g (x)$ эквивалентно строковому правилу $f 1 f 2 → g {\ displaystyle f_ {1} f_ {2} \ rightarrow g}$ $f_ {1} f_ {2} \ rightarrow g$ .

Система полу-Туэ также является особым типом канонической системы Post, но любую каноническую систему Post также можно свести к SRS. Оба формализма являются полными по Тьюрингу и, таким образом, эквивалентны неограниченным грамматикам Ноама Хомского , которые иногда называют полутюринговыми грамматиками. Формальная грамматика отличается от системы полу-Туэ только разделением алфавита на терминалы и нетерминалы, а также фиксацией начального символа среди нетерминалов. Меньшинство авторов фактически определяет систему полутуэ как тройку $(Σ, A, R) {\ displaystyle (\ Sigma, A, R)}$ $(\ Sigma, A, R)$ , где $A ⊆ Σ ∗ {\ displaystyle A \ substeq \ Sigma ^ {*}}$ $A \ substeq \ Sigma ^ {*}$ называется набором аксиом. Согласно этому «порождающему» определению системы полутуэ, неограниченная грамматика - это просто система полутуэ с единственной аксиомой, в которой алфавит разбивается на терминальные и нетерминальные и делает аксиому нетерминальной. Простая уловка разделения алфавита на терминалы и нетерминалы - очень мощный прием; он позволяет определять иерархию Хомского на основе того, какую комбинацию терминалов и нетерминалов содержат правила. Это было решающим событием в теории формальных языков.

. В квантовых вычислениях можно развить понятие квантовой системы Туэ. Поскольку квантовые вычисления по своей сути обратимы, правила перезаписи по алфавиту $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ должны быть двунаправленными (т.е. базовая система является системой Туэ, а не системой полу-Туэ.). К подмножеству символов алфавита $Q ⊆ Σ {\ displaystyle Q \ substeq \ Sigma}$ ${\ displaystyle Q \ substeq \ Sigma}$ можно прикрепить гильбертово пространство $C d {\ displaystyle \ mathbb {C} ^ {d} }$ ${\ displaystyle \ mathbb {C} ^ {d}}$ , а правило перезаписи, переводящее одну подстроку в другую, может выполнять унитарную операцию над тензорным произведением гильбертова пространства, присоединенного к строкам; это означает, что они сохраняют количество символов из набора $Q {\ displaystyle Q}$ $Q$ . Подобно классическому случаю, можно показать, что квантовая система Туэ является универсальной вычислительной моделью для квантовых вычислений в том смысле, что выполняемые квантовые операции соответствуют унифицированным классам схем (например, в BQP, когда, например, гарантируется завершение правил перезаписи строки в пределах полиномиального количества шагов от входного размера), или, что то же самое, квантовая машина Тьюринга.

История и важность

Системы Semi-Thue были разработаны как часть программы для добавления дополнительные конструкции к логике для создания таких систем, как логика высказываний, которые позволили бы выразить общие математические теоремы на формальном языке, а затем доказать и проверяется автоматическим, механическим способом. Была надежда, что акт доказательства теоремы затем можно свести к набору определенных манипуляций с набором строк. Впоследствии выяснилось, что системы полу-Туэ изоморфны неограниченным грамматикам, которые в свою очередь, как известно, изоморфны машинам Тьюринга. Этот метод исследования оказался успешным, и теперь компьютеры можно использовать для проверки доказательств математических и логических теорем.

По предложению Алонзо Чёрча, Эмиль Пост в статье, опубликованной в 1947 году, впервые доказал неразрешимость «определенной проблемы Туэ», что Мартин Дэвис заявляет как «... первое доказательство неразрешимости проблемы из классической математики - в данном случае проблема слов для полугрупп».

Дэвис также утверждает, что доказательство было независимо предложено А. А. Марков.

См. Также

Примечания

Ссылки

Монографии

Рональд В. Книга и Фридрих Отто, Системы перезаписи строк, Springer, 1993, ISBN 0-387-97965-4.
Маттиас Янцен, Перезапись сливающихся строк, Биркхойзер, 1988, ISBN 0-387-13715-7.

Учебники

Мартин Дэвис, Рон Сигал, Элейн Дж. Вейкер, Вычислимость, сложность и языки: основы теоретической информатики, 2-е изд.., Academic Press, 1994, ISBN 0-12-206382-1, глава 7
Элейн Рич, Автоматы, вычислимость и сложность: теория и заявки, Prentice Hall, 2007, ISBN 0-13-228806-0, глава 23.5.

Опросы

Самсон Абрамски, Дов М. Габбей, Томас С.Э. Майбаум (редактор), Справочник по логике в компьютерных науках: семантическое моделирование, Oxford University Press, 1995, ISBN 0-19-853780-8.
Гжегож Розенберг, Арто Саломаа (ред.), Справочник по форме al Языки: Word, язык, грамматика, Springer, 1997, ISBN 3-540-60420-0.

Ориентирные статьи

Эмиль Пост (1947) Рекурсивная неразрешимость проблемы Туэ, The Journal of Symbolic Logic 12: 1–11 через Project Euclid.