Thesis (M.Sc.) - Cairo University - Faculty of Science - Department of Mathematics

The thesis consists of three chapters. In the {uFB01}rst chapter we introduce preliminary de{uFB01}nitions and facts we need from logic and complexity. The last section is on complexity, and the {uFB01}rst section is for extra notations that are not established within the de{uFB01}nitions of the thesis. The middle three sections are about {uFB01}nite structures, {uFB01}rst-order logic and its {uFB01}xed- point extensions, the Ehrenfeucht-Fraïssé game and its importance proving non-expressibility results. Particularly, at the end of the third section, we mention an exam- ple from [2] using the algebraic version of the game in proving non- expressibility of connectivity in {uFB01}rst-order logic, and then, in the fourth section, we present {uFB01}xed-point extensions of {uFB01}rst-order logic in which con- nectivity is expressible, or in fact, in which the path relation, which is transitive closure of the edge relation, in graphs, and transitive closure general, and more complicated kinds of recursion, are expressible. The second section is devoted to {uFB01}nite structures, especially, graphs and binary strings. We deal here with {uFB01}nite structures only because objects computers have and hold are always {uFB01}nite. Inputs, databases, programs are all {uFB01}nite objects that can be conveniently modeled as nite logical structures. Binary strings are important because every {uFB01}nite ordered structure can be coded as a binary string, and this is how the structure is introduced as an input to the Turing machine.

Issued also as CD