Turing Machine with Atoms and Descriptive Complexity
- Prelegent(ci)
- Szymon Toruńczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 2 kwietnia 2014 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
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.