Turing Machines with Atoms and Constraint Satisfaction Problems

Prelegent(ci)

Joanna Ochremiak

Afiliacja

Uniwersytet Warszawski

Termin

5 marca 2014 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Bartek Klin, Sławomir Lasota, Szymon Toruńczyk

Seminarium

Seminarium „Teoria automatów”

---

We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization is obtained from deep results in CSP theory.

---