Turing Machine with Atoms and Descriptive Complexity
- Speaker(s)
- Szymon Toruńczyk
- Affiliation
- Uniwersytet Warszawski
- Date
- April 2, 2014, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
We relate Turing Machines with Atoms to a certain logic over finite structures. As an application to Descriptive Complexity Theory, within a substantial class of relational structures including Cai-Fürer-Immerman graphs, we precisely characterize those subclasses where the logic IFP+C captures order-invariant polynomial time computation.