The power of the depth of iteration in dening relations by induction /
قوة عمق التكرار فى تعريف العلاقات بالاستقراء
Amena Assem Abdalqader Mahmoud ; Supervised Ford Georgy , Wak Boulos Lotfallah
- Cairo : Amena Assem Abdalqader Mahmoud , 2014
- 84 P. ; 25cm
Thesis (M.Sc.) - Cairo University - Faculty of Science - Department of Mathematics
The thesis consists of three chapters. In the rst chapter we introduce preliminary denitions and facts we need from logic and complexity. The last section is on complexity, and the rst section is for extra notations that are not established within the denitions of the thesis. The middle three sections are about nite structures, rst-order logic and its 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 rst-order logic, and then, in the fourth section, we present xed-point extensions of 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 nite structures, especially, graphs and binary strings. We deal here with nite structures only because objects computers have and hold are always nite. Inputs, databases, programs are all nite objects that can be conveniently modeled as nite logical structures. Binary strings are important because every 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.