On equivalence in unification

Prelegent(ci)

Aleksy Schubert

Afiliacja

MIMUW

Język referatu

angielski

Termin

6 czerwca 2025 12:15

Pokój

p. 5450

Tytuł w języku polskim

O równoważności w unifikacji

Seminarium

Semantyka, Logika I Weryfikacja Oraz Wiele Ich Ciekawych Aplikacji

---

W problemie unifikacji na słowach w sposób naturalny pojawia się relacja równoważności indukowana przez zmienne i strony równania. W oparciu o tę relację możemy zdefiniować pewne pojęcie włókna, które w sposób zwięzły jednoznacznie identyfikuje pozycję w potencjalnym rozwiązaniu zadania unifikacji. Przedstawiony zostanie oparty na tym pojęciu szkic dowodu, że problem unifikacji na słowach jest w NP.

---