On equivalence in unification

Speaker(s)

Aleksy Schubert

Affiliation

MIMUW

Language of the talk

English

Date

June 6, 2025, 12:15 p.m.

Room

room 5450

Title in Polish

O równoważności w unifikacji

Seminar

Seminar Semantics, Logic, Verification and its Applications

---

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.

---