000			02757cam a2200337 a 4500
003			EG-GiCUC
005			20250223031230.0
008			150521s2014 ua f m 000 0 eng d
040			_aEG-GiCUC _beng _cEG-GiCUC
041	0		_aeng
049			_aDeposite
097			_aM.Sc
099			_aCai01.12.17.M.Sc.2014.ِAm.P
100	0		_aAmena Assem Abdalqader Mahmoud
245	1	4	_aThe power of the depth of iteration in de{uFB01}ning relations by induction / _cAmena Assem Abdalqader Mahmoud ; Supervised Ford Georgy , Wa{uFB01}k Boulos Lotfallah
246	1	5	_aقوة عمق التكرار فى تعريف العلاقات بالاستقراء
260			_aCairo : _bAmena Assem Abdalqader Mahmoud , _c2014
300			_a84 P. ; _c25cm
502			_aThesis (M.Sc.) - Cairo University - Faculty of Science - Department of Mathematics
520			_aThe 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.
530			_aIssued also as CD
653		4	_aDepth
653		4	_aFinite Variable Logics
653		4	_aFixed-Point
700	0		_aFord Georgy , _eSupervisor
700	0		_aWa{uFB01}k Boulos Lotfallah , _eSupervisor
856			_uhttp://172.23.153.220/th.pdf
905			_aNazla _eRevisor
905			_aSoheir _eCataloger
942			_2ddc _cTH
999			_c50989 _d50989