O rozwiązywaniu równań w półgrupie wolnej

Speaker(s)

Wojciech Plandowski

Affiliation

Uniwersytet Warszawski

Date

March 2, 2006, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Na seminarium przedstawię pierwszy algorytm rozwiązujący równania w półgrupie wolnej, który działa w DEXPTIME. Prezentowane podejście pozwala na rozwiązanie w PSPACE następujących problemów: - sprawdzenia, czy zbiór rozwiązań równania jest skończony, - sprawdzenia, czy zbiór współczynników okresowości rozwiązań jest ograniczony.

---