Basic Information
The Course Deals With The Interplay Between Definability in Various Descriptive Langauges and Computability With Various Computing Devices. Finite Structures and The Undecidability of The Tautology Problem Over Finite Structures. Logical Characterization of Complexity Classes. Ehrenfeucht Games, Mondefinability and Definability Results. Second-order Logic, Logics With Computable Quantifiers and Predicate Transformers. Lindstrom's Theorem Characterizing First-order Logic On Arbitrary Structures.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(234292 - Logic For Cs and 236343 - Theory of Computation) or (234293 - Logic and Set Theory For Cs and 236343 - Theory of Computation)