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

Prelegent(ci)

Wojciech Plandowski

Afiliacja

Uniwersytet Warszawski

Termin

2 marca 2006 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---