Асоціативне числення

Асоціативне числення — важлива частина теорії алгоритмів, яка допомагає описувати алгоритми прикладних задач. Асоціативним численням називається сукупність всіх слів в даному абстрактному алфавіті разом з деякою скінченною системою допустимих підстановок. Асоціативне числення задається алфавітом і системою допустимих підстановок.

Асоціативне числення слів

В асоціативному численні слів вводяться допустимі операції підстановок без будь-яких обмежень на порядок їх застосування. Якщо U — деякий алфавіт, а A і B — слова в ньому, то неорієнтована підстановка позначається A ↔ B. Наприклад, підстановка ab ↔ bcb у двохелементному алфавіті U = {a, b} може бути застосована до слова abcbcbab в різному порядку, тобто можна в цьому слові виділяти (не обов'язково зліва) або слово ab, або слово bcb, тобто abcbcbab, або abcbcbab, або abcbcbab або abcbcbab.

Якщо слово A є результатом одного застосування допустимої підстановки до слова B, то очевидно, що слово B також є результатом застосування цієї ж підстановки до слова A; такі два слова називаються суміжними словами. Послідовність слів A₁, A₂,…, A_n, в якій два сусідні слова є суміжними, називається дедуктивним ланцюгом, який з'єднує слова A₁ і A_n. Два слова A і B називаються еквівалентними (позначається A ${\displaystyle \simeq }$ B), якщо існує дедуктивний ланцюг, який з'єднує ці слова. Ясно, що ${\displaystyle \simeq }$ є відношення еквівалентності.

Проблема еквівалентності слів

Проблема еквівалентності слів полягає в тому, що для довільних двох слів даного асоціативного числення необхідно визначити чи еквівалентні вони, чи ні. Ця проблема має важливе теоретичне і практичне значення в математиці.

Індекс входження літери, індекс слова

Індексом входження літери «a» в слово X називається число всіх входжень літери «c», які зустрічаються правіше літери «a». Індексом слова X називається сума індексів всіх входжень літери «a». Наприклад, в слові «accac» перша зліва літера «a» має індекс 3, друга — 1, індекс слова — 4.

Приклад

Асоціативне числення задається алфавітом {a, b,c} і системою допустимих підстановок:

ab ↔ ba

ac ↔ ca

bc ↔ cb

Розглянемо нормальний алгоритм:

A₂: ba → ab

ba → ab

ba → ab

Результатом застосування цього нормального алгоритму до довільного слова X в алфавіті {a, b,c} є слово, у якого є всі літери слова X, але вони упорядковані так, що спочатку йдуть всі літери «a», за ними — всі літери «b», і потім «c». Наприклад:

A₂(bacbaca)=(aaabbcc).

Алгоритм A₂ перетворює еквівалентні слова в даному асоціативному численні в рівні слова.

Джерела та література

• Конспект лекцій з математичної логіки та теорії алгоритмів / В. С. Трохименко — Вінниця: 2007. — 86с.
• Основания теории множеств / Френкель А. А., Бар-Хиллел И. — М.: Мир, 1966. — 557с.
• Введение в математическую логику, т.1 / Черч А. — М.: Издательство иностранной литературы, 1960. — 478.