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

Speaker(s)

Joanna Ochremiak

Affiliation

Uniwersytet Warszawski

Date

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

Room

room 5870

Title in Polish

Turing Machines with Atoms and Constraint Satisfaction Problems

Seminar

Seminar Automata Theory

---

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.

---