Π”ΠΈΠΏΠ»ΠΎΠΌ, курсовая, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ Ρ€Π°Π±ΠΎΡ‚Π°
ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² написании студСнчСских Ρ€Π°Π±ΠΎΡ‚

Алгоритмы Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ

Π”ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΡΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

Как ΡƒΠΆΠ΅ Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, благодаря выполнимости Π·Π°ΠΊΠΎΠ½Π° Π»Π΅Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ подстановок ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ, Π·Π°Π΄Π°Ρ‡Π° вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Ρ€Π΅ΡˆΠ΅Π½Π° ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρ‹ вычислСния Ρ‚ΠΎΡ‡Π½Ρ‹Ρ… Π½ΠΈΠΆΠ½ΠΈΡ… Π³Ρ€Π°Π½Π΅ΠΉ Π² Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ΅ подстановок (вычислСния Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ΠΎΠ²… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅

  • 1. Алгоритмы Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок
    • 1. 1. ΠŸΠΎΠ΄ΡΡ‚Π°Π½ΠΎΠ²ΠΊΠΈ ΠΈ ΠΈΡ… ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»Π΅Π½ΠΈΠ΅
      • 1. 1. 1. ΠŸΠΎΠ΄ΡΡ‚Π°Π½ΠΎΠ²ΠΊΠΈ, Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ° подстановок
      • 1. 1. 2. Π“Ρ€Π°Ρ„ΠΎΠ²Ρ‹Π΅ прСдставлСния подстановок
    • 1. 2. Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π² ΠΊΠ»Π°ΡΡΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
      • 1. 2. 1. Алгоритм Ρ€Π΅Π΄ΡƒΠΊΡ†ΠΈΠΈ
      • 1. 2. 2. Алгоритм Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ для подстановок, прСдставлСнных ацикличСскими ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ Π³Ρ€Π°Ρ„Π°ΠΌΠΈ
      • 1. 2. 3. НиТняя ΠΎΡ†Π΅Π½ΠΊΠ° слоТности Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок
    • 1. 3. ΠŸΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹
      • 1. 3. 1. Алгоритм распознавания Ρ‚ΠΎΡ‡Π½ΠΎΠ³ΠΎ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π°
      • 1. 3. 2. Алгоритм построСния Ρ‚ΠΎΡ‡Π½ΠΎΠ³ΠΎ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π°
    • 1. 4. ВычислСниС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ с ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок
      • 1. 4. 1. МодСль ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹
      • 1. 4. 2. Π˜Π½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ равСнства ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΠΈΡ… Π²Ρ‹Ρ‡ΠΈΡΠ»Π΅Π½ΠΈΡ
  • 2. ΠžΠ±ΠΎΠ±Ρ‰Π΅Π½Π½Ρ‹Π΅ подстановки
    • 2. 1. ΠœΠ΅Ρ‚Π°ΠΊΠΎΠ½Ρ‚Π΅ΠΊΡΡ‚Ρ‹ ΠΈ ΠΌΠ΅Ρ‚аподстановки
      • 2. 1. 1. ΠŸΠΎΠ½ΡΡ‚ΠΈΡ контСкста ΠΈ ΠΌΠ΅Ρ‚аконтСкста
      • 2. 1. 2. Π Π΅ΡˆΠ΅Ρ‚ΠΊΠ° мСтаконтСкстов
      • 2. 1. 3. ΠœΠ΅Ρ‚Π°ΠΏΠΎΠ΄ΡΡ‚Π°Π½ΠΎΠ²ΠΊΠΈ ΠΈ ΠΈΡ… ΠΎΡΠ½ΠΎΠ²Π½Ρ‹Π΅ алгСбраичСскиС свойства
      • 2. 1. 4. ΠžΠΏΠ΅Ρ€Π°Ρ†ΠΈΡ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚ΠΈΠ·Π°Ρ†ΠΈΠΈ мСтаподстановок
    • 2. 2. Антиунификация для мСтаподстановок
      • 2. 2. 1. ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²Π»Π΅Π½ΠΈΠ΅ мСтаконтСкстов ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΌΠΈ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°ΠΌΠΈ
      • 2. 2. 2. Алгоритм Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ мСтаконтСкстов
  • 3. Π˜Π½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ
    • 3. 1. ΠœΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Π΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΈ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ равСнства
      • 3. 1. 1. МодСль ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹
      • 3. 1. 2. Π˜Π½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ равСнства ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ ΠΈ ΠΈΡ… ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»Π΅Π½ΠΈΠ΅ ΠΌΠ΅Ρ‚Π°-подстановками
      • 3. 1. 3. ΠΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΡƒΡŽΡ‰ΠΈΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ
    • 3. 2. ВычислСниС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ мСтаподстановок
      • 3. 2. 1. ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ Π°ΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ
      • 3. 2. 2. Алгоритм построСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства

Алгоритмы Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

Π—Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ (Π°Π½Π³Π». anti-unification, generalization) Π±Ρ‹Π»Π° Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ рассмотрСна Π² Ρ€Π°Π±ΠΎΡ‚Π°Ρ… [18] ΠΈ [20]. Π’ ΠΎΠ±Ρ‰Π΅ΠΌ Π²ΠΈΠ΄Π΅ ΠΎΠ½Π° состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ для Π΄Π²ΡƒΡ… Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π• ΠΈ Π•2 ΠΎΡ‚Ρ‹ΡΠΊΠ°Ρ‚ΡŒ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π•0, ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΎΠ±Π° выраТСния ΠΈ Π•2, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ подстановки ΠΈ Π΄2. для ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ равСнства Π• = Π•0Π΄ ΠΈ Π•2 = Π•ΠΎ$ 2- Π’Π°ΠΊΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π•0 называСтся Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰ΠΈΠΌ шаблоном Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π• ΠΈ Π•2.

Π—Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ двойствСнна Π³ΠΎΡ€Π°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ ΡˆΠΈΡ€ΠΎΠΊΠΎ исслСдованной Π·Π°Π΄Π°Ρ‡Π΅ ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ. ПослСдняя состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ для Π΄Π²ΡƒΡ… Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ Π• ΠΈ Π•2 ΠΎΡ‚Ρ‹ΡΠΊΠ°Ρ‚ΡŒ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π•0, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ являСтся ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ ΠΎΠ±ΠΎΠΈΡ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π• ΠΈ Π•2, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ удовлСтворяСт равСнствам Π•0 = Π•Ρ‰ ΠΈ Π•0 — Π•2Ρ†2 для Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… подстановок Ρ‰ ΠΈ Π³/2. Π’Π°ΠΊΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Eq Π½Π°Π·Ρ‹Π²Π°Π΅Ρ‚ся Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΎΠ±Ρ‰ΠΈΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΈ Π•2. Π—Π°Π΄Π°Ρ‡Π° ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π±Ρ‹Π»Π° Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ исслСдована Π”ΠΆ. Робинсоном [21] Π² 1965 Π³ΠΎΠ΄Ρƒ Π² ΡΠ²ΡΠ·ΠΈ с ΡΠΎΠ·Π΄Π°Π½ΠΈΠ΅ΠΌ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Ρ€Π΅Π·ΠΎΠ»ΡŽΡ†ΠΈΠΉ для автоматичСского Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²Π° Ρ‚Π΅ΠΎΡ€Π΅ΠΌ. Π’ Π΄Π°Π»ΡŒΠ½Π΅ΠΉΡˆΠ΅ΠΌ ΠΌΠ΅Ρ‚ΠΎΠ΄ Ρ€Π΅Π·ΠΎΠ»ΡŽΡ†ΠΈΠΉ послуТил ΠΎΡ‚ΠΏΡ€Π°Π²Π½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΎΠΉ для Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ логичСского программирования, ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ фактичСски стали основным срСдством вычислСния логичСских ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π—Π° ΠΏΡ€ΠΎΡˆΠ΅Π΄ΡˆΠΈΠ΅ Π³ΠΎΠ΄Ρ‹ Π·Π°Π΄Π°Ρ‡Π° ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π±Ρ‹Π»Π° Π΄Π΅Ρ‚Π°Π»ΡŒΠ½ΠΎ исслСдована. Π’ Ρ‡Π°ΡΡ‚ности, Π±Ρ‹Π» Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ ΡˆΠΈΡ€ΠΎΠΊΠΈΠΉ спСктр эффСктивных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ [2, 12, 17, 27, 28], ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ… ΠΏΠΎΡ‡Ρ‚ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ, Π° Ρ‚Π°ΠΊΠΆΠ΅ Π±Ρ‹Π»ΠΈ Π½Π°ΠΉΠ΄Π΅Π½Ρ‹ подходящиС структуры Π΄Π°Π½Π½Ρ‹Ρ… для практичСской Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ этих Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ². Одной ΠΈΠ· Ρ‚Π°ΠΊΠΈΡ… структур для прСдставлСния подстановок ΡΠ²Π»ΡΡŽΡ‚ΡΡ ацикличСскиС ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π³Ρ€Π°Ρ„Ρ‹, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌΡ‹Π΅ ΠΈΠ· Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π² «ΡΠΊΠ»Π΅ΠΈΠ²Π°Π½ΠΈΠ΅ΠΌ» ΠΈΠ·ΠΎΠΌΠΎΡ€Ρ„Π½Ρ‹Ρ… ΠΏΠΎΠ΄Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π². Π’Π°ΠΆΠ½Ρ‹ΠΌ частным случаСм Π·Π°Π΄Π°Ρ‡ΠΈ ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ являСтся Π·Π°Π΄Π°Ρ‡Π° ΠΌΠ΅Ρ‚Ρ‡ΠΈΠΏΠ³Π° (ΠΎΡ‚ Π°Π½Π³Π». matching — ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² ΡΠΎΠΎΡ‚вСтствиС). Она состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ для Π΄Π²ΡƒΡ… Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π•0 ΠΈ Ei ΠΎΡ‚Ρ‹ΡΠΊΠ°Ρ‚ΡŒ подстановку ?/, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰ΡƒΡŽ равСнству Π•Ρ… = Π•0Π³).

Π—Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ (построСния Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰ΠΈΡ… шаблонов) Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Π»Π°ΡΡŒ Π² Ρ€ΡΠ΄Π΅ Ρ€Π°Π±ΠΎΡ‚ [5, 10, 11, 14, 15, 18, 20, 22, 24, 25, 36]. Π’ ΡΡ‚ΠΈΡ… Ρ€Π°Π±ΠΎΡ‚Π°Ρ… Π±Ρ‹Π»ΠΈ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Ρ‹ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ, ΠΈ Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… случаях Π±Ρ‹Π»Π° исслСдована ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этой Π·Π°Π΄Π°Ρ‡ΠΈ. Π’Π°ΠΊ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π² ΡΡ‚Π°Ρ‚ΡŒΠ΅ [10] Π±Ρ‹Π»ΠΎ установлСно, Ρ‡Ρ‚ΠΎ Π·Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ для Ρ‚Π΅Ρ€ΠΌΠΎΠ², прСдставлСнных Π² Π²ΠΈΠ΄Π΅ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², являтся JVC-ΠΏΠΎΠ»Π½ΠΎΠΉ (Π² ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ Π·Π°Π΄Π°Ρ‡ΠΈ ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ, которая относится ΠΊ Ρ‡ΠΈΡΠ»Ρƒ Π -ΠΏΠΎΠ»Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡). Π’ ΡΡ‚Π°Ρ‚ΡŒΠ΅ [5] Π±Ρ‹Π»ΠΈ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Ρ‹ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ для Ρ‚Π΅Ρ€ΠΌΠΎΠ², прСдставлСнных Π² Π²ΠΈΠ΄Π΅ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π². Π‘Ρ‹Π»ΠΎ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ Ρ‚Π΅Ρ€ΠΌΠΎΠ², прСдставлСнных Π΄Π΅Ρ€Π΅Π²ΡŒΡΠΌΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° N, ΠΌΠΎΠΆΠ½ΠΎ провСсти Π·Π° Π²Ρ€Π΅ΠΌΡ О (log2 А'") с ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ TV/log2 N ΠΏΡ€ΠΎΡ†Π΅ΡΡΠΎΡ€ΠΎΠ² Π² ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Ρ… вычислСний EREW PRAM, Π½Π΅ Π΄ΠΎΠΏΡƒΡΠΊΠ°ΡŽΡ‰Π΅ΠΉ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ΅ считываниС ΠΈ Π·Π°ΠΏΠΈΡΡŒ Π΄Π°Π½Π½Ρ‹Ρ… нСсколькими процСссорами Π² ΠΎΠ΄Π½Ρƒ ΠΈ Ρ‚Ρƒ ΠΆΠ΅ ячСйку памяти. Π’ ΡΡ‚ΠΎΠΉ ΠΆΠ΅ Ρ€Π°Π±ΠΎΡ‚Π΅ Π±Ρ‹Π»ΠΎ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π² Ρ‚ΠΎΠΌ случаС, ΠΊΠΎΠ³Π΄Π° нСскольким процСссорам Ρ€Π°Π·Ρ€Π΅ΡˆΠ°Π΅Ρ‚ΡΡ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΏΡ€ΠΎΠ²ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ считывания ΠΈ Π·Π°ΠΏΠΈΡΠΈ, относящиСся ΠΊ ΠΎΠ΄Π½ΠΎΠΉ ΠΈ Ρ‚ΠΎΠΉ ΠΆΠ΅ ячСйкС ΠΎΠ±Ρ‰Π΅ΠΉ памяти (модСль ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Ρ… вычислСний CRCW PRAM), Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ дрСвСсных Ρ‚Π΅Ρ€ΠΌΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ провСсти Π·Π° Π²Ρ€Π΅ΠΌΡ О (log N) с ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ N/ log Аг ΠΏΡ€ΠΎΡ†Π΅ΡΡΠΎΡ€ΠΎΠ². Однако ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ для Ρ‚Π΅Ρ€ΠΌΠΎΠ², для прСдставлСния ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ структуры Π΄Π°Π½Π½Ρ‹Ρ…, ΠΎΡ‚Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΡ‚ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², Ρ€Π°Π½Π΅Π΅ Π½Π΅ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π»Π°ΡΡŒ.

ЦСль Π³Π»Π°Π²Ρ‹ 1 этой Ρ€Π°Π±ΠΎΡ‚Ρ‹ — Π²Ρ‹ΡΡΠ½ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊΠΎΠ²Π° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π² Ρ‚ΠΎΠΌ случаС, ΠΊΠΎΠ³Π΄Π° рассматриваСмыС Ρ‚Π΅Ρ€ΠΌΡ‹ прСдставлСны ацикличСскими ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ Π³Ρ€Π°Ρ„Π°ΠΌΠΈ. Π—Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Ρ‚Π΅Ρ€ΠΌΠΎΠ² эквивалСнтна Π·Π°Π΄Π°Ρ‡Π΅ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок. Под подстановкой Π² Π΄Π°Π½Π½ΠΎΠΌ случаС понимаСтся ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ мноТСства ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π² ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ Ρ‚Π΅Ρ€ΠΌΠΎΠ², построСнноС Π½Π°Π΄ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΌ мноТСством Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌ мноТСством ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 1.2.2 прСдставлСн ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ зависит ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° вычисляСмого ΠΈΠΌ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ шаблона. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, устанавливаСтся, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈ ΠΈΠ·ΠΌΠ΅Ρ€Π΅Π½ΠΈΠΈ слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² исходных Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΠ΅ΠΌΠΎΠ³ΠΎ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π° Π·Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΏΠΎΡ‡Ρ‚ΠΈ Ρ‚Π°ΠΊΡƒΡŽ ΠΆΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΈ Π·Π°Π΄Π°Ρ‡Π° ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ, нСзависимо ΠΎΡ‚ Ρ„ΠΎΡ€ΠΌΡ‹ прСдставлСния Ρ‚Π΅Ρ€ΠΌΠΎΠ². Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 1.2.3 даСтся ниТняя ΠΎΡ†Π΅Π½ΠΊΠ° слоТности Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ для подстановок, прСдставлСнных ацикличСскими ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ Π³Ρ€Π°Ρ„Π°ΠΌΠΈ. Для этого прСдставлСн ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΏΠ°Ρ€ подстановок, Ρ€Π°Π·ΠΌΠ΅Ρ€ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰ΠΈΡ… шаблонов ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎ зависит ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² исходных подстановок. ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ ΠΏΠΎΠ΄Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π΅Ρ‚ сущСствСнноС ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ‚ΠΎΡ€Π½ΠΎΠ΅ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΎΡ‚ Π·Π°Π΄Π°Ρ‡ΠΈ ΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ. Π˜Π·Π²Π΅ΡΡ‚Π½ΠΎ, Ρ‡Ρ‚ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° Π΄Π²ΡƒΡ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ Π·Π°Π²ΠΈΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² самих Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ, Ссли эти выраТСния прСдставлСны Π² Π²ΠΈΠ΄Π΅ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π². Однако Π² Ρ‚ΠΎΠΌ случаС, Ссли для прСдставлСния Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ацикличСскиС ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ Π³Ρ€Π°Ρ„Ρ‹, Ρ‚ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½ΠΎΠΉ, Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ зависящСй ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² исходных Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ. Для Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ всС происходит Π½Π°ΠΎΠ±ΠΎΡ€ΠΎΡ‚: Ссли выраТСния прСдставлСны Π² Π²ΠΈΠ΄Π΅ Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², Ρ‚ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ шаблона Π΄Π²ΡƒΡ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π½Π΅ ΠΏΡ€Π΅Π²ΠΎΡΡ…ΠΎΠ΄ΠΈΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² самих исходных Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ, Π° Π΅ΡΠ»ΠΈ для прСдставлСния Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ацикличСскиС ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ Π³Ρ€Π°Ρ„Ρ‹ (Π±ΠΎΠ»Π΅Π΅ «ΠΊΠΎΠΌΠΏΠ°ΠΊΡ‚Π½ΡƒΡŽ» структуру Π΄Π°Π½Π½Ρ‹Ρ…), Ρ‚ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ шаблона ΠΌΠΎΠΆΠ΅Ρ‚ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎ Π·Π°Π²ΠΈΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² исходных Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ сущСствСнно зависит ΠΎΡ‚ ΡΠΏΠΎΡΠΎΠ±Π° прСдставлСния исходных Π΄Π°Π½Π½Ρ‹Ρ….

Π’ Ρ€Π°Π·Π΄Π΅Π»Π΅ 1.3 рассмотрСны ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок, прСдставлСнных ацикличСскими ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ Π³Ρ€Π°Ρ„Π°ΠΌΠΈ. ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ· Π½ΠΈΡ… — ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Π² ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 1.3.1 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ распознавания Ρ‚ΠΎΡ‡Π½ΠΎΠ³ΠΎ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π° — провСряСт, являСтся Π»ΠΈ заданная подстановка Π³] Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΡŒΡŽ Π΄Π²ΡƒΡ… Π΄Ρ€ΡƒΠ³ΠΈΡ… Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… подстановок ΠΈ Π—Π°Ρ‚Π΅ΠΌ Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ этого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° показываСтся, Ρ‡Ρ‚ΠΎ Π·Π°Π΄Π°Ρ‡Π° распознавания Ρ‚ΠΎΡ‡Π½ΠΎΠ³ΠΎ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π° для подстановок, прСдставлСнных Π² Π²ΠΈΠ΄Π΅ ацикличСских ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π³Ρ€Π°Ρ„ΠΎΠ², ΠΏΡ€ΠΈΠ½Π°Π΄Π»Π΅ΠΆΠΈΡ‚ классу слоТности N0. Однако ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ этот Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для вычислСния Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ подстановок Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 1.3.2 рассмотрСн Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΈΠ· Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² — ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ построСния ацикличСского ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³Ρ€Π°Ρ„Π°, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅Π³ΠΎ Ρ‚ΠΎΡ‡Π½ΡƒΡŽ ниТнюю Π³Ρ€Π°Π½ΡŒ Π΄Π²ΡƒΡ… подстановок, — ΠΈ ΠΎΡ†Π΅Π½Π΅Π½Π° Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ.

Одной ΠΈΠ· ΠΎΡΠ½ΠΎΠ²Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ статичСского Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ являСтся Π·Π°Π΄Π°Ρ‡Π° вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ², Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρƒ Π΄Π°Π½Π½Ρ‹ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ для Π»ΡŽΠ±Ρ‹Ρ… вычислСний ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹. Π—Π½Π°Π½ΠΈΠ΅ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ практичСских Π·Π°Π΄Π°Ρ‡ Π²Π΅Ρ€ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ, ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ, синтСза ΠΈ Ρ€Π΅ΠΎΡ€Π³Π°Π½ΠΈΠ·Π°Ρ†ΠΈΠΈ (Ρ€Π΅Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ½Π³Π°) ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ [1]. Π’ Ρ‚ΠΎ ΠΆΠ΅ врСмя, Π² ΠΎΠ΄Π½ΠΎΠΉ ΠΈ Ρ‚ΠΎΠΉ ΠΆΠ΅ Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ сущСствуСт бСсконСчно ΠΌΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Ρ€Π°Π·Π»ΠΈΡ‡Π½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π°. Π’ Ρ‡Π°ΡΡ‚ности, любая тоТдСствСнно истинная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΡΡ‚ΡƒΠΏΠ°Ρ‚ΡŒ Π² Ρ€ΠΎΠ»ΠΈ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π°. Π˜Π·Π²Π΅ΡΡ‚Π½ΠΎ Ρ‚Π°ΠΊΠΆΠ΅, Ρ‡Ρ‚ΠΎ Π² ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹Ρ… модСлях вычислСний Π·Π°Π΄Π°Ρ‡Π° ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ заданная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° являСтся ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹, Π°Π»Π³ оритмичСски Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠ°. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΌ исслСдовании, посвящСнном Π²Ρ‹Ρ‡ΠΈΡΠ»Π΅Π½ΠΈΡŽ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ², Ρ€Π°Π·ΡƒΠΌΠ½ΠΎ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡ΠΈΡ‚ΡŒΡΡ поиском ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π°.

Π’ ΡΡ‚ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ исслСдуСтся Π·Π°Π΄Π°Ρ‡Π° вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ прСдставимы Ρ„ΠΎΡ€ΠΌΡƒΠ»ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΏΡ€Π΅Π΄ΠΈΠΊΠ°Ρ‚ΠΎΠ² ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ порядка Π²ΠΈΠ΄Π°

3Ρƒ13Ρƒ2 Β¦ β€’ β€’ 3ΡƒΠΊ (ΡŠΡ… = ?1 Π› Π³>2 = ?2 А β€’ Β¦ β€’ Π› Π£Ρ‚ = ¿-Ρ‚), Π³Π΄Π΅ ?1, /2,., ~ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Ρ‚Π΅Ρ€ΠΌΡ‹. ОсновноС Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡƒΠ΄Π΅Π»Π΅Π½ΠΎ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ для ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ сильного ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° Π² ΠΊΠ»Π°ΡΡΠ΅ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Ρ‚Π°ΠΊΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹, ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π² ΡΠ²ΠΎΠ±ΠΎΠ΄Π½Ρ‹Ρ… эрбрановских) интСрпрСтациях логичСски ΡΠ»Π΅Π΄ΡƒΡŽΡ‚ всС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ равСнства Π² ΡΡ‚ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅.

ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства сущСствСнно зависят ΠΎΡ‚ ΠΌΠΎΠ΄Π΅Π»ΠΈ исслСдуСмой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹. Π’ Ρ€Π°Π·Π΄Π΅Π»Π΅ 1.4 Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ ΠΌΠ΅Ρ‚ΠΎΠ΄ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, мноТСство ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π΅ ΡΠΎΠ΄Π΅Ρ€ΠΆΠΈΡ‚ Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€. Π’ ΡΡ‚ΠΎΠΌ случаС вычислСниС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства СстСствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ сводится ΠΊ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½Π½ΠΎΠΉ Π² Ρ€Π°Π·Π΄Π΅Π»Π°Ρ… 1.2 ΠΈ 1.3 Π·Π°Π΄Π°Ρ‡Π΅ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΊ Π·Π°Π΄Π°Ρ‡Π΅ вычислСния Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ Π² Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ΅ подстановок. Π’Π°ΠΆΠ½Ρ‹ΠΌ свойством подстановок, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‰ΠΈΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΡŽ для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, являСтся Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ Π·Π°ΠΊΠΎΠ½Π° Π»Π΅Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ подстановок ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ. Π­Ρ‚ΠΎ свойство позволяСт ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ быстрыС ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ вычислСния Π½Π΅ΠΏΠΎΠ΄Π²ΠΈΠΆΠ½Ρ‹Ρ… Ρ‚ΠΎΡ‡Π΅ΠΊ, ΡˆΠΈΡ€ΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°Ρ‡ статичСского Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ Π²Π΅Ρ€ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ (см., Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, [13]).

Помимо Π·Π°Π΄Π°Ρ‡ΠΈ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ², ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚ ΠΈ ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π΄Ρ€ΡƒΠ³ΠΈΡ… Π·Π°Π΄Π°Ρ‡ Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π’Π°ΠΊ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Π»ΠΎΠ³ΠΈΠΊΠΎ-Ρ‚Π΅Ρ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ эквивалСнтности ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Π’. К. Π‘Π°Π±Π΅Π»ΡŒΡ„Π΅Π»ΡŒΠ΄ΠΎΠΌ [35], фактичСски ΠΏΡ€ΠΎΠ²ΠΎΠ΄ΠΈΡ‚ вычислСниС ΠΈ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ ΠΎΠ±Ρ‰ΠΈΡ… шаблонов Ρ‚Π΅Ρ€ΠΌΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΠΏΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ΡΡ Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ Π°Π½Π°Π»ΠΈΠ·ΠΈΡ€ΡƒΠ΅ΠΌΡ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π’ Ρ€Π°Π±ΠΎΡ‚Π΅ [3] антиунификация Ρ‚Π΅Ρ€ΠΌΠΎΠ² использовалась для поиска «ΠΊΠ»ΠΎΠ½ΠΎΠ²» Π² Ρ‚СкстС ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Ρ„Ρ€Π°Π³ΠΌΠ΅Π½Ρ‚ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Ρ‹ Π΄Ρ€ΡƒΠ³ ΠΈΠ· Π΄Ρ€ΡƒΠ³Π° Π·Π°ΠΌΠ΅Π½ΠΎΠΉ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΏΠΎΠ΄Ρ„Ρ€Π°Π³ΠΌΠ΅Π½Ρ‚ΠΎΠ². Π’ ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ всС ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ исслСдуСмой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ дСлятся ΠΏΠ° ΠΊΠ»Π°ΡΡ‚Π΅Ρ€Ρ‹, Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ Ρ‡Π΅Π³ΠΎ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΊ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ΠΎΠ² Ρ‚Π°ΠΊΠΈΡ… кластСров. ПослС этого снова ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π² ΡΡ‚ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π²Ρ‹Π΄Π΅Π»ΡΡŽΡ‚ΡΡ «ΠΏΠΎΡ…ΠΎΠΆΠΈΠ΅» ΠΏΠΎΠ΄ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. Π’ Ρ€Π°Π±ΠΎΡ‚Π΅ [14] антиунификация использовалась для выявлСния ΡˆΠΈΡ€ΠΎΠΊΠΎΡ€Π°ΡΠΏΡ€ΠΎΡΡ‚Ρ€Π°Π½Π΅Π½Π½Ρ‹Ρ… шаблонов Ρ„ΠΎΡ€ΠΌΡƒΠ», ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Ρ… Π² Π½Π°ΡƒΡ‡Π½Ρ‹Ρ… ΡΡ‚Π°Ρ‚ΡŒΡΡ…. Π’ Ρ€Π°Π±ΠΎΡ‚Π΅ [22] ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ ΠΌΠ΅Ρ‚ΠΎΠ΄ супСркомпиляции Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ антиунификация подстановок.

Как ΡƒΠΆΠ΅ Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, благодаря выполнимости Π·Π°ΠΊΠΎΠ½Π° Π»Π΅Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ подстановок ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ, Π·Π°Π΄Π°Ρ‡Π° вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Ρ€Π΅ΡˆΠ΅Π½Π° ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρ‹ вычислСния Ρ‚ΠΎΡ‡Π½Ρ‹Ρ… Π½ΠΈΠΆΠ½ΠΈΡ… Π³Ρ€Π°Π½Π΅ΠΉ Π² Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ΅ подстановок (вычислСния Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ΠΎΠ² подстановок). К ΡΠΎΠΆΠ°Π»Π΅Π½ΠΈΡŽ, ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊ Π²Ρ‹Ρ‡ΠΈΡΠ»Π΅Π½ΠΈΡŽ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства сталкиваСтся со Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ трудностями Π² Ρ‚ΠΎΠΌ случаС, ΠΊΠΎΠ³Π΄Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° состоит ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ (ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€) ΠΈ ΡΠΎΠ΄Π΅Ρ€ΠΆΠΈΡ‚ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Π²Ρ‹Π·ΠΎΠ²Π° этих ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ. Π­Ρ‚ΠΎ связано с Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎ Π² Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ΅ подстановок Π½Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΠ΅Ρ‚ся Π·Π°ΠΊΠΎΠ½ ΠΏΡ€Π°Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ подстановок ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°, получСнная Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΉ подстановки Π΄Ρ€ΡƒΠ³ Π² Π΄Ρ€ΡƒΠ³Π° Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, вычислСнных ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ, Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ равСнства, Π½ΠΎ ΡΡ‚ΠΎΡ‚ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚, Π²ΠΎΠΎΠ±Ρ‰Π΅ говоря, Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΡΠ²Π»ΡΡ‚ΡŒΡΡ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΌ. Π’ Π³Π»Π°Π²Π΅ 2 ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ΠΎ ΠΎΠ±ΠΎΠ±Ρ‰Π°ΡŽΡ‰Π΅Π΅ ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΡŽ подстановки понятиС рСгулярной мСтпаподстановки, для ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ выполняСтся Π·Π°ΠΊΠΎΠ½ ΠΏΡ€Π°Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ (ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ мСтаподстановок). Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ этого Π·Π°ΠΊΠΎΠ½Π°, наряду с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ свойствами, позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ мСтаподстановок для вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π’Π΅Ρ€ΠΌΠΈΠ½ «ΠΌΠ΅Ρ‚Π°-подстановка» Π±Ρ‹Π» Π²Ρ‹Π±Ρ€Π°Π½ для обозначСния Π²Π²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ Π½Π°ΠΌΠΈ понятия ΠΏΠΎΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΎ СстСствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΠ±ΠΎΠ±Ρ‰Π°Π΅Ρ‚ понятиС подстановки. Π•Π³ΠΎ Π½Π΅ ΡΠ»Π΅Π΄ΡƒΠ΅Ρ‚ ΠΏΡƒΡ‚Π°Ρ‚ΡŒ с ΠΏΠΎΠ½ΡΡ‚ΠΈΠ΅ΠΌ «Ρ‚Π΅Π», Π°Π·Ρ‡Π¬Π·ΠΏΠ¬ΠΈ (Π»ΠΎΠΏ», ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹ΠΌ Π² Ρ‚Π΅ΠΎΡ€ΠΈΠΈ пСрСписывания для обозначСния подстановок Π²Ρ‹ΡΡˆΠ΅Π³ΠΎ порядка (см. Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, [6]).

Π‘Π°Π·ΠΎΠ²Ρ‹ΠΌ понятиСм, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹ΠΌ для опрСдСлСния мСтаподстановки, являСтся понятиС контСкста. Как ΡƒΠΆΠ΅ Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, Π»ΡŽΠ±ΡƒΡŽ подстановку ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ Π½Π°Π±ΠΎΡ€Π° ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Ρ… ΠΊΠΎΡ€Π½Π΅Π²Ρ‹Ρ… ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… упорядочСнных Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π². Π’ΠΎΠ³Π΄Π° контСкстом Π±ΡƒΠ΄Π΅Ρ‚ любая Π²Π΅Ρ‚Π²ΡŒ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ· Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π² этого Π½Π°Π±ΠΎΡ€Π°, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Ρ†Π΅ΠΏΡŒ, Π½Π°Ρ‡ΠΈΠ½Π°ΡŽΡ‰Π°ΡΡΡ ΠΊΠΎΡ€Π½Π΅ΠΌ ΠΈ Π·Π°ΠΊΠ°Π½Ρ‡ΠΈΠ²Π°ΡŽΡ‰Π°ΡΡΡ Π»ΡŽΠ±Ρ‹ΠΌ ΠΈΠ· Π»ΠΈΡΡ‚ΡŒΠ΅Π². РСгулярной мСтаподстановкой Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ любоС (ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ ΠΈΠ»ΠΈ бСсконСчноС) мноТСство контСкстов, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰Π΅Π΅ свойствам линСйности, согласованности, ΠΏΠΎΠ»Π½ΠΎΡ‚Ρ‹ ΠΈ Ρ€Π΅Π³ΡƒΠ»ΡΡ€Π½ΠΎΡΡ‚ΠΈ. ΠžΡΡ‚Π°Π½ΠΎΠ²ΠΈΠΌΡΡ ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½Π΅Π΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· ΡΡ‚ΠΈΡ… свойств, удСляя особоС Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Ρ‚ΠΎΠΉ Ρ€ΠΎΠ»ΠΈ, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΎΠ½ΠΈ ΠΈΠ³Ρ€Π°ΡŽΡ‚ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства.

ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ контСкстов К Π½Π°Π·Ρ‹Π²Π°Π΅Ρ‚ΡΡ Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌ ΠΏΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡƒ ΠΌΠ½ΠΎ-ΠΎΡŽΠ΅Π΅Ρ‚Π΅Ρƒ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Ссли любая пСрСмСнная ΠΈΠ· ΡΡ‚ΠΎΠ³ΠΎ мноТСства встрСчаСтся Π½Π° Π»ΠΈΡΡ‚ΡŒΡΡ… контСкстов ΠΈΠ· Πš Π½Π΅ Π±ΠΎΠ»Π΅Π΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Ρ€Π°Π·Π°. Как ΡƒΠΆΠ΅ Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, подстановка — это ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ мноТСства ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… VI Π² ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ Ρ‚Π΅Ρ€ΠΌΠΎΠ², построСнных Π½Π°Π΄ мноТСством Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌ мноТСством ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… V'2. Для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚ΡŒ мноТСство ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π’Π› Π½Π° Π΄Π²Π° Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΡ…ΡΡ подмноТСсгва — ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ мноТСство 2 ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π²Ρ…ΠΎΠ΄Π° (Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² модуля) ΠΈ Π±Π΅ΡΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ мноТСство 3' Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… связанным ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ Π² ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π°Ρ… равСнства. ΠœΡ‹ Π±ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ мноТСства контСкстов, Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Π΅ ΠΏΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Ρƒ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π£. Π‘ ΠΎΠ΄Π½ΠΎΠΉ стороны, Ρ‚Π°ΠΊΠΎΠ΅ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠ΅ сущСствСнно суТаСт ΠΊΡ€ΡƒΠ³ поиска ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства. ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹ΠΉ нашим ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ равСнства Π±ΡƒΠ΄Π΅Ρ‚ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π½Π΅ Π²ΠΎ Π²ΡΠ΅ΠΌ мноТСствС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, Π° Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² Π΅Π³ΠΎ подмноТСствС Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства. Однако Π² Π³Π»Π°Π²Π΅ 3 ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρƒ Π½ΠΈΠΌΠΈ Π±ΡƒΠ΄Π΅Ρ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Ρ‚Π΅Ρ€ΠΌΠΎΠ², Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΡ…ΡΡ Π² ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π΅, Π° Π½Π΅ Π² ΡΡ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π΅ ΠΈΠ· Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов этих Ρ‚Π΅Ρ€ΠΌΠΎΠ². Π­Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ равСнства ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΈΠ· Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства отоТдСствлСниСм Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… связанных ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, свойство линСйности мноТСства контСкстов Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ для выполнимости Π·Π°ΠΊΠΎΠ½Π° ΠΏΡ€Π°Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ мСтаподстановок ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ.

Рассмотрим Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ свойство согласованности мноТСства контСкстов. ΠŸΡ€ΠΈ описании свойства линСйности Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ, Ρ‡Ρ‚ΠΎ мноТСство ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π£ΠΎ, Π½Π°Π΄ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌΠΈ строятся Ρ‚Π΅Ρ€ΠΌΡ‹, Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠ΅ΡΡ Π² Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹Ρ… для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства мстаподстановках, раздСляСтся Π½Π° Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΠ΅ΡΡ мноТСства ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π²Ρ…ΠΎΠ΄Π° Π• ΠΈ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов Н, Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΡ…ΡΡ Π² ΡΡ‚ΠΈΡ… Ρ‚Π΅Ρ€ΠΌΠ°Ρ…, Ρ‚Π°ΠΊΠΆΠ΅ распадаСтся Π½Π° Π΄Π²Π° Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΡ…ΡΡ подмноТСства — мноТСство Π’ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ (арифмСтичСских ΠΈ ΠΏΡ€.), Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΡ…ΡΡ Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅, ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ V ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½Ρ‹Ρ… символов, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… соотвСтствуСт ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΈΠ· ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹. ΠŸΡ€ΠΈ вычислСнии ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства сначала строятся мСтаподстановки для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ модуля Π² ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, Π° Π·Π°Ρ‚Π΅ΠΌ Π² ΠΌΠ΅Ρ‚аподстановкС, построСнной для исслСдуСмой Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹, всС ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½Ρ‹Π΅ символы ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ Π·Π°ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ Π½Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ мСтаподстановки. ΠΠ΅ΡΠΎΠ³Π»Π°ΡΠΎΠ²Π°Π½Π½ΠΎΡΡ‚ΡŒ Π΄Π²ΡƒΡ… контСкстов Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚ Π² Ρ‚ΠΎΠΌ случаС, ΠΊΠΎΠ³Π΄Π° ΠΏΡ€ΠΈ Π½Π°Π»ΠΎΠΆΠ΅Π½ΠΈΠΈ Π΄Ρ€ΡƒΠ³ Π½Π° Π΄Ρ€ΡƒΠ³Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΈΠΌ Π²Π΅Ρ‚Π²Π΅ΠΉ ΠΈΠ· Π½Π°Π±ΠΎΡ€Π° Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰ΠΈΡ… подстановки, обнаруТиваСтся, Ρ‡Ρ‚ΠΎ Π΄Π²Π΅ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ этих Π²Π΅Ρ‚Π²Π΅ΠΉ Π»ΠΈΠ±ΠΎ ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Ρ‹ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ (Π½Π΅ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½Ρ‹ΠΌΠΈ) символами, Π»ΠΈΠ±ΠΎ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Π°Ρ пСрСмСнная накладываСтся Π½Π° Π»ΡŽΠ±ΠΎΠΉ ΠΎΡ‚Π»ΠΈΡ‡Π½Ρ‹ΠΉ ΠΎΡ‚ Π½Π΅Π΅ символ. ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ контСкстов называСтся согласованным, Ссли всС Π΅Π³ΠΎ элСмСнты ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ согласованы. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ свойства согласованности позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½Π½ΡƒΡŽ Π² Ρ€Π°Π·Π΄Π΅Π»Π΅ 3.1 Π³Π»Π°Π²Ρ‹ 3 Ρ‚Π΅Ρ…Π½ΠΈΠΊΡƒ Π°ΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΡƒΡŽΡ‰ΠΈΡ… ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ для опрСдСлСния Ρ‚ΠΎΠ³ΠΎ ΠΌΠΎΠΌΠ΅Π½Ρ‚Π°, ΠΊΠΎΠ³Π΄Π° нСобходимая для вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ рСкурсивной ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ мСтаподстановка ΡƒΠΆΠ΅ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π°. БогласованноС мноТСство контСкстов называСтся мСтаконтСкстом. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π°Ρ… 2.1.1 ΠΈ 2.1.2 Π΄Π°Π½Ρ‹ строгиС опрСдСлСния контСкста ΠΈ ΠΌΠ΅Ρ‚аконтСкста, Π° Ρ‚Π°ΠΊΠΆΠ΅ исслСдованы ΠΈΡ… ΠΎΡΠ½ΠΎΠ²Π½Ρ‹Π΅ свойства. Π’ Ρ‡Π°ΡΡ‚ности, ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ для Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… ΠΌΠ΅-таконтСкстов Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ мноТСств контСкстов опрСдСляСтся ниТняя ΠΏΠΎΠ»ΡƒΡ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ°. ΠžΠΏΠ΅Ρ€Π°Ρ†ΠΈΡ вычислСния Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ Π² ΡΡ‚ΠΎΠΉ Ρ€Π΅ΡˆΠ΅Ρ‚ΠΊΠ΅, называСмая Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠ΅ΠΉ мСтаконтСкстов, являСтся ΠΎΡΠ½ΠΎΠ²ΠΎΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‰Π΅ΠΉ для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнств.

ΠŸΠ΅Ρ€Π΅ΠΉΠ΄Π΅ΠΌ ΠΊ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Π½ΠΈΡŽ свойства ΠΏΠΎΠ»Π½ΠΎΡ‚Ρ‹ мноТСства контСкстов. Как ΡƒΠΆΠ΅ ΠΎΡ‚ΠΌΠ΅Ρ‡Π°Π»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, контСкст прСдставляСт Π²Π΅Ρ‚Π²ΡŒ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· Π½Π°Π±ΠΎΡ€Π° Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π³ΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ подстановкС. ΠŸΠΎΠ»Π½Ρ‹ΠΌ называСтся мноТСство контСкстов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ всС Π²Π΅Ρ‚Π²ΠΈ мноТСства Π½Π°Π±ΠΎΡ€ΠΎΠ² Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π², Π·Π°Π΄Π°ΡŽΡ‰ΠΈΡ… нСпустоС мноТСство подстановок. ΠŸΠΎΠ»Π½Ρ‹ΠΉ Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ мСтаконтСкст называСтся ΠΌΠ΅Ρ‚Π°-подстановкой. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ свойства ΠΏΠΎΠ»Π½ΠΎΡ‚Ρ‹ позволяСт ΡΠΎΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ любой ΠΌΠ΅Ρ‚Π°ΠΏΠΎΠ΄-становкС Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ мноТСство подстановок. ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Π°Ρ ΠΏΡ€ΠΈ вычислСнии Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства мСтаподстановка содСрТит Π² ΡΡ‚ΠΎΠΌ мноТСствС всСго ΠΎΠ΄Π½Ρƒ подстановку (Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ являСтся ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΉ минимальной). Π­Ρ‚ΠΎΠΉ подстановкС СстСствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ сопоставляСтся Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°, которая ΠΈ ΡΠ²Π»ΡΠ΅Ρ‚ся искомым ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ. Помимо этого, свойство ΠΏΠΎΠ»Π½ΠΎΡ‚Ρ‹ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ для выполнСния ряда алгСбраичСских Π·Π°ΠΊΠΎΠ½ΠΎΠ² Π² ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Π΅ мСтаподстановок, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ Π·Π°ΠΊΠΎΠ½ ΠΏΡ€Π°Π²ΠΎΠΉ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ ΠΈ Π·Π°ΠΊΠΎΠ½ ассоциативности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ. Π‘Ρ‚Ρ€ΠΎΠ³ΠΎΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ мСтаподстановки наряду с Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²Π°ΠΌΠΈ основных свойств прСдставлСно Π² ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 2.1.3.

ΠŸΠ΅Ρ€Π΅ΠΉΠ΄Π΅ΠΌ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΠΊ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡŽ свойства рСгулярности мСтаподстановок. Π’ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ ΠΏΠΎΠ΄ΡΡ‚Π°Π½ΠΎΠ²ΠΎΠΊ, любая ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… являСтся ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΉ структурой, мСтаподстановки ΠΌΠΎΠ³ΡƒΡ‚ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ бСсконСчноС мноТСство контСкстов. Π­Ρ‚ΠΎ ΠΎΠ±ΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ оказываСтся ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ΠΌ для Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€ΠΈ локальном вычислСнии мСтаподстановки для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ модуля ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ ΠΎ ΡΠ²ΡΠ·ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ Π΄Π°Π½Π½Ρ‹ΠΌΠΈ ΠΏΠΎ Π²ΡΠ΅ΠΌ трассам этого модуля, Π½Π°Ρ‡ΠΈΠ½Π°ΡŽΡ‰ΠΈΠΌΡΡ Π² Π²Ρ…ΠΎΠ΄Π½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΈ Π·Π°ΠΊΠ°Π½Ρ‡ΠΈΠ²Π°ΡŽΡ‰ΠΈΡ…ся ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΡƒΡŽΡ‰Π΅ΠΉ нас Ρ‚ΠΎΡ‡ΠΊΠΎΠΉ. ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π° мноТСство контСкстов ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΊΠ°ΠΊΠΎΠΉ-Π»ΠΈΠ±ΠΎ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠΉ структурой Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°Π»ΠΎΠΆΠΈΡ‚ΡŒ Π΅Ρ‰Π΅ ΠΎΠ΄Π½ΠΎ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠ΅ Π½Π° ΠΌΠ΅Ρ‚аподстановки, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅, с ΠΎΠ΄Π½ΠΎΠΉ стороны, всС Π΅Ρ‰Π΅ позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΡ… Π΄Π»Ρ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства, ΠΈ, с Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, допускаСт ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ прСдставлСниС мСтаподстано-Π²ΠΎΠΊ. Как Π³ΠΎΠ²ΠΎΡ€ΠΈΠ»ΠΎΡΡŒ Π²Ρ‹ΡˆΠ΅, контСкст Π·Π°Π΄Π°Π΅Ρ‚ Π²Π΅Ρ‚Π²ΡŒ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ· Π΄Π΅Ρ€Π΅Π²ΡŒΠ΅Π² Π½Π°Π±ΠΎΡ€Π°, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅Π³ΠΎ подстановку. И ΡΡ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π΅Π³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ слова Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅ ΠΈΠ· ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… символов ΠΈ Π½ΠΎΠΌΠ΅Ρ€ΠΎΠ² Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² этих символов. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ мноТСству контСкстов ΠΌΠΎΠΆΠ½ΠΎ ΡΠΎΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ язык Π² Ρ‚Π°ΠΊΠΎΠΌ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅. ΠœΠ΅Ρ‚Π°ΠΏΠΎΠ΄ΡΡ‚Π°Π½ΠΎΠ²ΠΊΠ° называСтся рСгулярной, Ссли сопоставлСнный Π΅ΠΉ ΡΠ·Ρ‹ΠΊ являСтся рСгулярным. И Ρ‚ΠΎΠ³Π΄Π° ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Ρ€Π΅Π³ΡƒΠ»ΡΡ€Π½ΡƒΡŽ мСтаиодстановку ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ³ΠΎ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°, ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‰Π΅Π³ΠΎ сопоставлСнный Π΅ΠΉ ΡΠ·Ρ‹ΠΊ. Π’Π°ΠΊΠΎΠ΅ прСдставлСниС позволяСт Ρ€Π°Π·Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ с ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ рСгулярных мСтаподстановок. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 2.2.1 Π΄Π°Π½ΠΎ строгоС ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ рСгулярной мСтаподстановки, ΠΈ ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½ΠΎ рассмотрСно Π΅Π΅ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π½ΠΎΠ΅ прСдставлСниС. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 2.2.2 прСдставлСн Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ, Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‰ΠΈΠΉ Ρ‚ΠΎΡ‡Π½ΡƒΡŽ ниТнюю Π³Ρ€Π°Π½ΡŒ рСгулярных мСтаподстановок, прСдставлСнных ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΌΠΈ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°ΠΌΠΈ. Π­Ρ‚ΠΎΡ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΡˆΠΈΡ€ΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ с Ρ€Π΅ΠΊΡƒΡ€ΡΠΈΠ²Π½Ρ‹ΠΌΠΈ Π²Ρ‹Π·ΠΎΠ²Π°ΠΌΠΈ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€.

Π“Π»Π°Π²Π° 3 посвящСна Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства для ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ с Π²Ρ‹Π·ΠΎΠ²Π°ΠΌΠΈ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 3.1.1 строго Π²Π²Π΅Π΄Π΅Π½Π° модСль ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ Π½Π΅Π΄Π΅Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠΉ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹. Π’ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ содСрТатся ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Π΄Π²ΡƒΡ… Π²ΠΈΠ΄ΠΎΠ² — ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ присваивания ΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Π²Ρ‹Π·ΠΎΠ²Π° ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρ‹. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 3.1.2 Π΄Π°Π½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΈ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Π½ ΠΌΠ΅Ρ‚ΠΎΠ΄ свСдСния Π·Π°Π΄Π°Ρ‡ΠΈ построСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° равСнства ΠΊ Π·Π°Π΄Π°Ρ‡Π΅ вычислСния мСтаподстановки ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π°. ΠŸΠ°Ρ€Π°Π³Ρ€Π°Ρ„ 3.1.3 посвящСн исслСдованию свойств Ρ‚Π°ΠΊΠΎΠΉ мСтаподстановки. Π’ Ρ‡Π°ΡΡ‚ности, ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π΅Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π°ΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΡƒΡŽΡ‰ΠΈΡ… ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ ΠΈΠ· ΠΌΠ΅-таподстановок, сопоставлСнных ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 3.2.1 говорится ΠΎ Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π½Ρ‹Π΅ прСдставлСния послСдних Π»Π΅Π³ΠΊΠΎ строятся нСпосрСдствСнно ΠΏΠΎ ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° поиска Π½Π΅ΠΏΠΎΠ΄Π²ΠΈΠΆΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΈ. Π’ ΠΏΠ°Ρ€Π°Π³Ρ€Π°Ρ„Π΅ 3.2.2 ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ вычислСния Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Ρ… ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства для ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ с Π²Ρ‹Π·ΠΎΠ²Π°ΠΌΠΈ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€.

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ этой Ρ€Π°Π±ΠΎΡ‚Ρ‹ Ρ‚Π°ΠΊΠΎΠ²Ρ‹.

1. Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΏΠΎ ΠΏΠΎΡ€ΡΠ΄ΠΊΡƒ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок, прСдставлСнных Π² Π²ΠΈΠ΄Π΅ ацикличСских ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π³Ρ€Π°Ρ„ΠΎΠ², ΠΈ Π½Π° Π΅Π³ΠΎ основС ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ Π½ΠΎΠ²Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства Π² ΠΌΠΎΠ΄Π΅Π»ΡΡ… ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ.

2. УстановлСна вСрхняя ΠΎΡ†Π΅Π½ΠΊΠ° слоТности Π² ΠΊΠ»Π°ΡΡΠ΅ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок, прСдставлСнных Π² Π²ΠΈΠ΄Π΅ ацикличСских ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π³Ρ€Π°Ρ„ΠΎΠ².

3. ΠŸΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π° концСпция мСтаподстановки, ΠΎΠ±ΠΎΠ±Ρ‰Π°ΡŽΡ‰Π°Ρ понятиС подстановки, ΠΈ ΡƒΡΡ‚Π°Π½ΠΎΠ²Π»Π΅Π½Ρ‹ основныС алгСбраичСскиС свойства мСтаподстановок.

4. Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π² ΠΊΠ»Π°ΡΡΠ΅ рСгулярных мСтаподстановок, прСдставлСнных ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΌΠΈ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°ΠΌΠΈ, ΠΈ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ этого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ ΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹ΠΉ (Π΄Π²ΡƒΡ…ΡƒΡ€ΠΎΠ²Π½Π΅Π²Ρ‹ΠΉ) ΠΌΠ΅Ρ‚ΠΎΠ΄ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства Π² ΠΌΠΎΠ΄Π΅Π»ΡΡ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ с Ρ€Π΅ΠΊΡƒΡ€ΡΠΈΠ²Π½Ρ‹ΠΌ Π²Ρ‹Π·ΠΎΠ²ΠΎΠΌ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€.

Π—Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

Π’ Π΄ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ исслСдована Π·Π°Π΄Π°Ρ‡Π° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ Π΅Π΅ ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ для вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ.

Для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… подстановок, прСдставлСнных ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ ацикличСскими Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, Π±Ρ‹Π»ΠΈ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Ρ‹ Π½ΠΎΠ²Ρ‹Π΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΈ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок ΠΈ ΠΎΡ†Π΅Π½Π΅Π½Π° ΠΈΡ… ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ. Показано, Ρ‡Ρ‚ΠΎ Π² ΠΊΠ»Π°ΡΡΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Π² Ρ€Π°Π±ΠΎΡ‚Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок являСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΏΠΎ ΠΏΠΎΡ€ΡΠ΄ΠΊΡƒ. Π’ΠΏΠ΅Ρ€Π²Ρ‹Π΅ Π±Ρ‹Π»Π° установлСна ΠΎΡ†Π΅Π½ΠΊΠ° слоТности Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок Π² ΠΊΠ»Π°ΡΡΠ΅ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ². На ΠΎΡΠ½ΠΎΠ²Π΅ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π±Ρ‹Π» Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ Π½ΠΎΠ²Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства для простых ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΡ… Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π° Π²Ρ‹Π·ΠΎΠ²Π° ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€ (ΠΎΠ΄Π½ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ).

ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ состоят ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€ (ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ), Π΄ΠΎΠΏΡƒΡΠΊΠ°ΡŽΡ‰ΠΈΡ… Π²Ρ‹Π·ΠΎΠ² Π΄Ρ€ΡƒΠ³ Π΄Ρ€ΡƒΠ³Π°, Π² Π΄ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ Π±Ρ‹Π»Π° исслСдована Ρ‚Π°ΠΊΠΆΠ΅ Π·Π°Π΄Π°Ρ‡Π° вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства для ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Π·ΠΎΠ²Π°ΠΌΠΈ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€, Π² Ρ‚ΠΎΠΌ числС рСкурсивными. Π‘Ρ‹Π»ΠΎ установлСно, Ρ‡Ρ‚ΠΎ вычислСниС ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹Ρ… подстановок сущСствСнно ослоТняСтся Π½Π΅Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒΡŽ Π² ΡΡ‚ΠΎΠΌ классС подстановок Π·Π°ΠΊΠΎΠ½Π° ΠΏΡ€Π°Π²ΠΎΠΉ дистибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ. Для прСодолСния ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠ³ΠΎ нСдостатка Π±Ρ‹Π»ΠΎ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π° ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Π°Ρ концСпция мСтаподстановки, ΠΎΠ±ΠΎΡ‰Π°ΡŽΡ‰Π°Ρ Ρ‚Ρ€Π°Π΄ΠΈΡ†ΠΈΠΎΠ½Π½ΠΎΠ΅ понятиС подстановки. Π’ Π΄ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ ΠΏΡ€ΠΎΠ²Π΅Π΄Π΅Π½ΠΎ исслСдованиС основных алгСбраичСских свойств мСтаподстановок ΠΈ, Π² Ρ‡Π°ΡΡ‚ности, ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π² ΠΊΠ»Π°ΡΡΠ΅ мСтаподстановок Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ ΠΊΠ°ΠΊ Π»Π΅Π²Ρ‹ΠΉ, Ρ‚Π°ΠΊ ΠΈ ΠΏΡ€Π°Π²Ρ‹ΠΉ Π·Π°ΠΊΠΎΠ½Ρ‹ дистрибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ, Ρ‡Ρ‚ΠΎ Π²Ρ‹Π³ΠΎΠ΄Π½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Π΅Ρ‚ Π°Π»Π³Π΅Π±Ρ€Ρƒ мСтаподстановк ΠΎΡ‚ Π°Π»Π³Π΅Π±Ρ€Ρ‹ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹Ρ… ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… подстановок. Π’Π°ΠΊΠΆΠ΅ Π² Π΄ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ Π²Ρ‹Π΄Π΅Π»Π΅Π½ ΠΎΠ΄ΠΈΠ½ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π²Π°ΠΆΠ½Ρ‹ΠΉ для прилоТСния класс мСтаподстановок (класс рСгулярных мСтаподстановок), Π΄ΠΎΠΏΡƒΡΠΊΠ°ΡŽΡ‰ΠΈΡ… прСдставлСниС ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΎΠ². Для рСгулярных мСтаподстановок прСдставлСнных Π² Π²ΠΈΠ΄Π΅ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΎΠ² Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ.

Алгоритмы Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ Π² Π°Π»Π³Π΅Π±Ρ€Π΅ рСгулярных мСтаподстановок Π±Ρ‹Π»ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½Ρ‹ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ Π·Π°ΠΊΠΎΠ½Π° ΠΏΡ€Π°Π²ΠΎΠΉ днстибутивности ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ взятия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ»Π° Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ простой Π΄Π²ΡƒΡ…ΡƒΡ€ΠΎΠ²Π½Π΅Π²Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства — Π½Π° ΠΏΠ΅Ρ€Π²ΠΎΠΌ этапС ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ мСтаподстановок для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ модуля вычисляСтся рСгулярная мСтаподстановка ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π²ΠΈΠ΄Π°, Π° Π·Π°Ρ‚Π΅ΠΌ ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Ρ‚ΠΎΠ³ΠΎ ΠΆΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° строится конСчная Π°ΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΡƒΡŽΡ‰Π°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ, послСдний Ρ‡Π»Π΅Π½ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ прСдставляСт ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π² Π·Π°Π΄Π°Π½Π½ΠΎΠΉ Π΅Π΅ Ρ‚ΠΎΡ‡ΠΊΠ΅.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π² Π΄ΠΈΡΡΠ΅Ρ€Ρ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅

1. Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½Ρ‹ Π½ΠΎΠ²Ρ‹Π΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΈ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок;

2. ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Ρ‹ Π½ΠΎΠ²Ρ‹Π΅, Π±ΠΎΠ»Π΅Π΅ Ρ‚ΠΎΡ‡Π½Ρ‹Π΅ ΠΎΡ†Π΅Π½ΠΊΠΈ слоТности Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок;

3. ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½ΠΎ Π½ΠΎΠ²ΠΎΠ΅ ΠΎΠ±ΠΎΠ±Ρ‰Π΅Π½ΠΈΠ΅ понятия подстановки — мСтаподстановка, — для ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ установлСна Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΡΡ‚ΡŒ основных алгСбраичСских Π·Π°ΠΊΠΎΠ½ΠΎΠ² Π°ΡΡΠΎΡ†ΠΈΠ°Ρ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ ΠΈ Π΄ΠΈΡΡ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ ΠΈ Π²Π·ΡΡ‚ия Ρ‚ΠΎΡ‡Π½ΠΎΠΉ Π½ΠΈΠΆΠ½Π΅ΠΉ Π³Ρ€Π°Π½ΠΈ), Π° Ρ‚Π°ΠΊΠΆΠ΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ;

4. Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ подстановок ΠΈ ΠΌΠ΅Ρ‚аподстановок ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Ρ‹ Π½ΠΎΠ²Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² равСнства для ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, Π²ΠΊΠ»ΡŽΡ‡Π°Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠΎΠ΄ΡƒΠ»ΡŒΠ½Ρ‹Π΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ с Ρ€Π΅ΠΊΡƒΡ€ΡΠΈΠ²Π½Ρ‹ΠΌ Π²Ρ‹Π·ΠΎΠ²ΠΎΠΌ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€.

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст

Бписок Π»ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΡƒΡ€Ρ‹

  1. Apt K.R., Olderog E.-R. Verification of Sequential and Concurrent Programs. Springer, 1997, 364 p.
  2. Baxter L.D. An efficient unification algorithm. Technical Report CS-73−23, Dep. of Analysis and Comp. Sci., University of Waterloo, Ontario, Canada, 1973.
  3. Bulychev P., Minea M. Duplicate code detection using anti-unification. Proceedings of the First Spring Young Researchers Colloquium on Software Engineering, 2008, pp. 51−54.
  4. Coppersmith D., Winograd S. On the asymptotic complexity of matrix multiplication. SIAM J. Comput., v 11, 1982, pp. 472−492.
  5. Delcher A.L., Kasif S. Efficient parallel term matching and anti-unification. Journal of Automated Reasoning, v. 9, N 3, 1992, pp. 391−406.
  6. Dershowitz N., Jouannaud J.-P. Handbook of Theoretical Computer Science, v. B: Models and Sematics, chapter 6: Rewrite Systems, 1990, pp. 243−320.
  7. Dwork C., Kanellakis P.C., and Mitchel D.C. On the Sequental Nature of Unification. Journal of Logic Programming, v. 1, 1984, pp. 35−50.
  8. Dwork C., Kanellakis P.C., and Stockmeyer L. Parallel Algorithms for Term Matching. SIAM J. Comput., v. 17, n. 4, 1988, pp. 711−731.
  9. Eder E. Properties of substitutions and unifications. Journal of Symbolic Computations, v. 1, 1985, pp. 31−46.
  10. Kuper G. M., McAloon K. W., Palem K. V., Perry K. J. A note on the parallel complexity of anti-unification. Journal of Automated Reasoning, v. 9, N 3, 1992, pp. 381−389.
  11. Lassez J.I., Maher M.J., Marriot K. Unification revisited. In Foundations of Deductive Databases and Logic Programming, ed. J. Minker, Morgan Kaufmann, Los Altos, 1988.
  12. Martelli A., Montanari U. An efficient unification algorithm. ACM Transactions on Program, Languages and Systems, v. 4, N 2, 1982, pp. 258−282.
  13. Nielson F., Nielson H.R., Hankin C. Principles of Program Analysis. Springer, 1999, 446 p.
  14. Oancea C.E., So C., Watt S.M. Generalization in Maple, Maple Conference, 2005, pp. 277−382.
  15. Palamidessi C. Algebraic properties of idempotent substitutions. Lecture Notes in Computer Science, v. 443, 1990, pp. 386−399.
  16. Pan V., Reif J. Efficient parallel solutions of linear systems. Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, pp.143−152.
  17. Paterson M.S., Wegman M.N. Linear unification. The Journal of Computer and System Science, v. 16, N 2, 1978, pp. 158−167.
  18. Plotkin G.D. A note on inductive generalization. Machine Intelligence, 1970, v. 5, N 1, 1970, pp. 153−163.
  19. Rabin M.O., Scott D. Finite automata and their decision problems. IBM J. Research and Development, v. 3, N 2, 1959, pp. 115−125.
  20. Reynolds J.Π‘. Transformational systems and the algebraic structure of atomic formulas. Machine Intelligence, v.5, N 1, 1970, pp. 135—151.
  21. Robinson J.A. A machine-oriented logic based on the resolution princple. Journal of the ACM, v. 12, N 1, 1965, pp. 23−41.
  22. Sorensen M.H., Gluck. R. An algorithm of generalization in positive supercompilation, Logic Programming: Proceedings of the 1995 International Symposium, MIT Press, 1995, pp. 465−479.
  23. Tarjan R.E., Vishkin U. An Efficient Parallel Biconnectivity Algorithm. SIAM J. Comput., v. 14, n. 4, 1985, pp. 862−874.
  24. Watt S.M. Algebraic generalization. ACM SIGSAM Bulletin, v. 39, N 3, 2005, pp. 93−94.
  25. Zakharov V.A. On the refinement of logic programs by means of anti-unification. Proceedings of the 2-nd Panhellenic Logic Symposium, Delphi, Greece, 1999, pp. 219−224.
  26. Ахо А., Ульман Π”. ВСория синтаксичСского Π°Π½Π°Π»ΠΈΠ·Π°, ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Π° ΠΈ ΠΊΠΎΠΌΠΏΠΈΠ»ΡΡ†ΠΈΠΈ. Москва, ΠœΠΈΡ€, 1978.
  27. А.Π’., ΠšΡ€ΠΈΠ²ΠΎΠΉ C.JI. О ΠΏΡ€ΠΎΠ΅ΠΊΡ‚ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ эффСктивных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² привСдСния Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΎΠ² для Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠΉ эквивалСнтности. ΠšΠΈΠ±Π΅Ρ€Π½Π΅Ρ‚ΠΈΠΊΠ°, N 6, 1989, с. 54−61.
  28. А.И. Об ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠΈ аксиом Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎΠΉ рСфлСксивности Π² (Π  & R) ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π΅ опровСрТСния. ΠŸΡ€Π΅ΠΏΡ€ΠΈΠ½Ρ‚ Ин-Ρ‚Π° ΠšΠΈΠ±Π΅Ρ€Π½Π΅Ρ‚ΠΈΠΊΠΈ АН Π£Π‘Π‘Π , N 75−28, 1975, 28 с.
  29. Π”. Π˜ΡΠΊΡƒΡΡΡ‚Π²ΠΎ программирования, Ρ‚ΠΎΠΌ 3. Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΈ ΠΏΠΎΠΈΡΠΊ. Москва, ΠœΠΈΡ€, 1977.
  30. Π•.Π’., Π—Π°Ρ…Π°Ρ€ΠΎΠ² Π’. А. Об ΠΎΠ΄Π½ΠΎΠΌ ΠΎΠ±ΠΎΠ±Ρ‰Π΅Π½ΠΈΠΈ подстановок ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΊ Π·Π°Π΄Π°Ρ‡Π΅ синтСза ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. ΠœΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ VIII-Π³ΠΎ ΠœΠ΅ΠΆΠ΄ΡƒΠ½Π°Ρ€ΠΎΠ΄Π½ΠΎΠ³ΠΎ сСминара «Π”ΠΈΡΠΊΡ€Π΅Ρ‚Π½Π°Ρ ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ° ΠΈ Π΅Π΅ ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ», Москва, 2004, с.134−136.
  31. Π•.Π’. ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ вычислСния ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. Π’Ρ€ΡƒΠ΄Ρ‹ всСроссийской ΠΊΠΎΠ½Ρ„Π΅Ρ€Π΅Π½Ρ†ΠΈΠΈ студСнтов, аспирантов ΠΈ ΠΌΠΎΠ»ΠΎΠ΄Ρ‹Ρ… ΡƒΡ‡Π΅Π½Ρ‹Ρ… «Π’Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ Microsoft Π² Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΈ ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ программирования», Москва, 2005, с. 130.
  32. Π•.Π’. О Π²Ρ‹Ρ‡ΠΈΡΠ»Π΅Π½ΠΈΠΈ ΠΈΠ½Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. ВСзисы Π΄ΠΎΠΊΠ»Π°Π΄ΠΎΠ² XIV ΠΌΠ΅ΠΆΠ΄ΡƒΠ½Π°Ρ€ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠΎΠ½Ρ„Π΅Ρ€Π΅Π½Ρ†ΠΈΠΈ «ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ тСорСтичСской ΠΊΠΈΠ±Π΅Ρ€Π½Π΅Ρ‚ΠΈΠΊΠΈ», Москва, 2005, с. 73.
  33. Π•.Π’., Π—Π°Ρ…Π°Ρ€ΠΎΠ² Π’. А. Об ΠΎΠ΄Π½ΠΎΠΌ ΠΎΠ±ΠΎΠ±Ρ‰Π΅Π½ΠΈΠΈ подстановки ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΊ Π·Π°Π΄Π°Ρ‡Π΅ статичСского Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. ВСстник Московского УнивСрситСта, 2005, сСр.15, Π’Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ° ΠΈ ΠšΠΈΠ±Π΅Ρ€Π½Π΅Ρ‚ΠΈΠΊΠ°, № 4, с.39−45.
  34. Π•.Π’., Π—Π°Ρ…Π°Ρ€ΠΎΠ² Π’. А. О ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΠΈ Π·Π°Π΄Π°Ρ‡ΠΈ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ. ДискрСтная ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ°, 2008, Ρ‚.20, Π²Ρ‹ΠΏ.1, с.131−144.
  35. Π’.К. Полиномиальная ΠΎΡ†Π΅Π½ΠΊΠ° слоТности распознавания Π»ΠΎΠ³ΠΈΠΊΠΎ-Ρ‚Π΅Ρ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ эквивалСнтности. Π”ΠΎΠΊΠ»Π°Π΄Ρ‹ АН Π‘Π‘Π‘Π , 1979, Ρ‚. 249, N 4, с. 793−796.
  36. Π’.А., ΠšΠΎΡΡ‚Ρ‹Π»Π΅Π² Π•. Π’. БыстрыС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π°Π½Ρ‚ΠΈΡƒΠ½ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΏΡ€ΠΈ Π°Π½Π°Π»ΠΈΠ·Π΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ. ΠœΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ XIII-ΠΉ ΠœΠ΅ΠΆΠ΄ΡƒΠ½Π°Ρ€ΠΎΠ΄Π½ΠΎΠΉ ΡˆΠΊΠΎΠ»Ρ‹-сСминара «Π‘ΠΈΠ½Ρ‚Π΅Π· ΠΈ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΡƒΠΏΡ€Π°Π²Π»ΡΡŽΡ‰ΠΈΡ… систСм», ПСнза, 2002, Π§Π°ΡΡ‚ΡŒ 1, с. 76−81.
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ