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.