%PDF-1.4
%
3 0 obj
<< /pgfprgb [/Pattern /DeviceRGB] >>
endobj
20 0 obj
<< /S /GoTo /D (chapter*.1) >>
endobj
23 0 obj
(Summary)
endobj
24 0 obj
<< /S /GoTo /D (chapter*.2) >>
endobj
27 0 obj
(Acknowledgements)
endobj
28 0 obj
<< /S /GoTo /D (section*.3) >>
endobj
31 0 obj
(Contents)
endobj
32 0 obj
<< /S /GoTo /D (chapter.1) >>
endobj
35 0 obj
(Introduction)
endobj
36 0 obj
<< /S /GoTo /D (section.1.1) >>
endobj
39 0 obj
(Is there a logic for PTIME?)
endobj
40 0 obj
<< /S /GoTo /D (section.1.2) >>
endobj
43 0 obj
(The importance of linear algebra)
endobj
44 0 obj
<< /S /GoTo /D (section.1.3) >>
endobj
47 0 obj
(Contributions of this thesis)
endobj
48 0 obj
<< /S /GoTo /D (section.1.4) >>
endobj
51 0 obj
(Previously published work and collaborations)
endobj
52 0 obj
<< /S /GoTo /D (chapter.2) >>
endobj
55 0 obj
(Definitions and preliminaries)
endobj
56 0 obj
<< /S /GoTo /D (section.2.1) >>
endobj
59 0 obj
(Basic notation)
endobj
60 0 obj
<< /S /GoTo /D (section.2.2) >>
endobj
63 0 obj
(Logics and structures)
endobj
64 0 obj
<< /S /GoTo /D (subsection.2.2.1) >>
endobj
67 0 obj
(Structures)
endobj
68 0 obj
<< /S /GoTo /D (subsection.2.2.2) >>
endobj
71 0 obj
(Logics)
endobj
72 0 obj
<< /S /GoTo /D (subsection.2.2.3) >>
endobj
75 0 obj
(Assignments)
endobj
76 0 obj
<< /S /GoTo /D (subsection.2.2.4) >>
endobj
79 0 obj
(Definable classes and queries)
endobj
80 0 obj
<< /S /GoTo /D (subsection.2.2.5) >>
endobj
83 0 obj
(Interpretations and logical reductions)
endobj
84 0 obj
<< /S /GoTo /D (subsection.2.2.6) >>
endobj
87 0 obj
(Types and equivalences)
endobj
88 0 obj
<< /S /GoTo /D (subsection.2.2.7) >>
endobj
91 0 obj
(Lindstr\366m quantifiers and extensions)
endobj
92 0 obj
<< /S /GoTo /D (section.2.3) >>
endobj
95 0 obj
(Logics with inductive definitions)
endobj
96 0 obj
<< /S /GoTo /D (subsection.2.3.1) >>
endobj
99 0 obj
(Inflationary fixed-point logic)
endobj
100 0 obj
<< /S /GoTo /D (subsection.2.3.2) >>
endobj
103 0 obj
(Transitive closure logics)
endobj
104 0 obj
<< /S /GoTo /D (section.2.4) >>
endobj
107 0 obj
(Many-sorted logics and structures)
endobj
108 0 obj
<< /S /GoTo /D (subsection.2.4.1) >>
endobj
111 0 obj
(Many-sorted structures)
endobj
112 0 obj
<< /S /GoTo /D (subsection.2.4.2) >>
endobj
115 0 obj
(Many-sorted logics)
endobj
116 0 obj
<< /S /GoTo /D (section.2.5) >>
endobj
119 0 obj
(Logics with counting)
endobj
120 0 obj
<< /S /GoTo /D (subsection.2.5.1) >>
endobj
123 0 obj
(First-order logic with counting)
endobj
124 0 obj
<< /S /GoTo /D (subsection.2.5.2) >>
endobj
127 0 obj
(Fixed-point logic with counting)
endobj
128 0 obj
<< /S /GoTo /D (section.2.6) >>
endobj
131 0 obj
(Infinitary logics)
endobj
132 0 obj
<< /S /GoTo /D (section.2.7) >>
endobj
135 0 obj
(Algebra)
endobj
136 0 obj
<< /S /GoTo /D (subsection.2.7.1) >>
endobj
139 0 obj
(Common algebraic structures)
endobj
140 0 obj
<< /S /GoTo /D (subsection.2.7.2) >>
endobj
143 0 obj
(Finite fields)
endobj
144 0 obj
<< /S /GoTo /D (subsection.2.7.3) >>
endobj
147 0 obj
(Graphs)
endobj
148 0 obj
<< /S /GoTo /D (section.2.8) >>
endobj
151 0 obj
(Linear algebra)
endobj
152 0 obj
<< /S /GoTo /D (subsection.2.8.1) >>
endobj
155 0 obj
(Matrices and linear maps)
endobj
156 0 obj
<< /S /GoTo /D (subsection.2.8.2) >>
endobj
159 0 obj
(Matrices indexed by unordered sets)
endobj
160 0 obj
<< /S /GoTo /D (section.2.9) >>
endobj
163 0 obj
(Logics and complexity classes)
endobj
164 0 obj
<< /S /GoTo /D (subsection.2.9.1) >>
endobj
167 0 obj
(Computational complexity)
endobj
168 0 obj
<< /S /GoTo /D (subsection.2.9.2) >>
endobj
171 0 obj
(Logics capturing complexity classes)
endobj
172 0 obj
<< /S /GoTo /D (chapter.3) >>
endobj
175 0 obj
(Linear algebra in fixed-point logic with counting)
endobj
176 0 obj
<< /S /GoTo /D (section.3.1) >>
endobj
179 0 obj
(Matrices as relational structures)
endobj
180 0 obj
<< /S /GoTo /D (subsection.3.1.1) >>
endobj
183 0 obj
(Matrices over finite fields)
endobj
184 0 obj
<< /S /GoTo /D (subsection.3.1.2) >>
endobj
187 0 obj
(Integer and rational matrices)
endobj
188 0 obj
<< /S /GoTo /D (section.3.2) >>
endobj
191 0 obj
(Describing finite fields in IFPC)
endobj
192 0 obj
<< /S /GoTo /D (subsection.3.2.1) >>
endobj
195 0 obj
(Prime fields)
endobj
196 0 obj
<< /S /GoTo /D (subsection.3.2.2) >>
endobj
199 0 obj
(Prime-power fields)
endobj
200 0 obj
<< /S /GoTo /D (section.3.3) >>
endobj
203 0 obj
(Describing integer and rational matrices in IFPC)
endobj
204 0 obj
<< /S /GoTo /D (subsection.3.3.1) >>
endobj
207 0 obj
(Specifying matrices over Z and Q by formulae)
endobj
208 0 obj
<< /S /GoTo /D (subsection.3.3.2) >>
endobj
211 0 obj
(Binary arithmetic)
endobj
212 0 obj
<< /S /GoTo /D (subsection.3.3.3) >>
endobj
215 0 obj
(Product of matrices)
endobj
216 0 obj
<< /S /GoTo /D (subsection.3.3.4) >>
endobj
219 0 obj
(Exponentiation and trace of matrices)
endobj
220 0 obj
<< /S /GoTo /D (section.3.4) >>
endobj
223 0 obj
(Characteristic polynomial over Z, Q and finite fields)
endobj
224 0 obj
<< /S /GoTo /D (subsection.3.4.1) >>
endobj
227 0 obj
(Overview of Le Verrier's method)
endobj
228 0 obj
<< /S /GoTo /D (subsection.3.4.2) >>
endobj
231 0 obj
(Characteristic polynomial over Z and Q)
endobj
232 0 obj
<< /S /GoTo /D (subsection.3.4.3) >>
endobj
235 0 obj
(Characteristic polynomial over finite fields)
endobj
236 0 obj
<< /S /GoTo /D (section.3.5) >>
endobj
239 0 obj
(Rank and minimal polynomial over the rationals)
endobj
240 0 obj
<< /S /GoTo /D (subsection.3.5.1) >>
endobj
243 0 obj
(Rank over Q)
endobj
244 0 obj
<< /S /GoTo /D (subsection.3.5.2) >>
endobj
247 0 obj
(Minimal polynomial over Q)
endobj
248 0 obj
<< /S /GoTo /D (chapter.4) >>
endobj
251 0 obj
(Logics with matrix rank operators)
endobj
252 0 obj
<< /S /GoTo /D (section.4.1) >>
endobj
255 0 obj
(Rank logics)
endobj
256 0 obj
<< /S /GoTo /D (subsection.4.1.1) >>
endobj
259 0 obj
(Specifying matrices over GFp by number terms or formulae)
endobj
260 0 obj
<< /S /GoTo /D (subsection.4.1.2) >>
endobj
263 0 obj
(Logics with rank operators over prime fields)
endobj
264 0 obj
<< /S /GoTo /D (subsection.4.1.3) >>
endobj
267 0 obj
(Logics with rank operators over Q)
endobj
268 0 obj
<< /S /GoTo /D (subsection.4.1.4) >>
endobj
271 0 obj
(Infinitary logic with rank quantifiers)
endobj
272 0 obj
<< /S /GoTo /D (section.4.2) >>
endobj
275 0 obj
(Systems of linear equations)
endobj
276 0 obj
<< /S /GoTo /D (subsection.4.2.1) >>
endobj
279 0 obj
(Linear equations over prime fields)
endobj
280 0 obj
<< /S /GoTo /D (subsection.4.2.2) >>
endobj
283 0 obj
(Linear equations over prime-power fields)
endobj
284 0 obj
<< /S /GoTo /D (section.4.3) >>
endobj
287 0 obj
(Arity hieararchy of rank logics)
endobj
288 0 obj
<< /S /GoTo /D (subsection.4.3.1) >>
endobj
291 0 obj
(Hella's construction for characteristic two)
endobj
292 0 obj
<< /S /GoTo /D (subsection.4.3.2) >>
endobj
295 0 obj
(General construction for any prime characteristic)
endobj
296 0 obj
<< /S /GoTo /D (section.4.4) >>
endobj
299 0 obj
(Relationships between rank logics)
endobj
300 0 obj
<< /S /GoTo /D (chapter.5) >>
endobj
303 0 obj
(First-order logic with rank)
endobj
304 0 obj
<< /S /GoTo /D (section.5.1) >>
endobj
307 0 obj
(Expressive power of FOR)
endobj
308 0 obj
<< /S /GoTo /D (subsection.5.1.1) >>
endobj
311 0 obj
(Cai-F\374rer-Immerman graphs)
endobj
312 0 obj
<< /S /GoTo /D (subsection.5.1.2) >>
endobj
315 0 obj
(Isomorphism of multipedes)
endobj
316 0 obj
<< /S /GoTo /D (section.5.2) >>
endobj
319 0 obj
(Descriptive complexity)
endobj
320 0 obj
<< /S /GoTo /D (subsection.5.2.1) >>
endobj
323 0 obj
(Encoding ordered structures as strings)
endobj
324 0 obj
<< /S /GoTo /D (subsection.5.2.2) >>
endobj
327 0 obj
(Logspace-bounded Turing machines)
endobj
328 0 obj
<< /S /GoTo /D (subsection.5.2.3) >>
endobj
331 0 obj
(FOR p captures MODpL on ordered structures)
endobj
332 0 obj
<< /S /GoTo /D (subsection.5.2.4) >>
endobj
335 0 obj
(FORQ captures LC=L on ordered structures)
endobj
336 0 obj
<< /S /GoTo /D (chapter.6) >>
endobj
339 0 obj
(Ehrenfeucht-Fra\357ss\351 games for rank logics)
endobj
340 0 obj
<< /S /GoTo /D (section.6.1) >>
endobj
343 0 obj
(Pebble games for Lk and Ck)
endobj
344 0 obj
<< /S /GoTo /D (section.6.2) >>
endobj
347 0 obj
(Pebble game for Rkp; m)
endobj
348 0 obj
<< /S /GoTo /D (section.6.3) >>
endobj
351 0 obj
(Pebble games for generalised quantifiers)
endobj
352 0 obj
<< /S /GoTo /D (chapter.7) >>
endobj
355 0 obj
(Non-definability results for fixed-point logic with rank)
endobj
356 0 obj
<< /S /GoTo /D (section.7.1) >>
endobj
359 0 obj
(Building blocks)
endobj
360 0 obj
<< /S /GoTo /D (subsection.7.1.1) >>
endobj
363 0 obj
(Circuits over Abelian groups)
endobj
364 0 obj
<< /S /GoTo /D (subsection.7.1.2) >>
endobj
367 0 obj
(C-structures)
endobj
368 0 obj
<< /S /GoTo /D (subsection.7.1.3) >>
endobj
371 0 obj
(Isomorphisms of C-structures)
endobj
372 0 obj
<< /S /GoTo /D (section.7.2) >>
endobj
375 0 obj
(Similar matrices defined by set partitions)
endobj
376 0 obj
<< /S /GoTo /D (subsection.7.2.1) >>
endobj
379 0 obj
(Basic partitions)
endobj
380 0 obj
<< /S /GoTo /D (subsection.7.2.2) >>
endobj
383 0 obj
(Matrices defined over partitions)
endobj
384 0 obj
<< /S /GoTo /D (subsection.7.2.3) >>
endobj
387 0 obj
(Extended partitions)
endobj
388 0 obj
<< /S /GoTo /D (section.7.3) >>
endobj
391 0 obj
(Application of the game method)
endobj
392 0 obj
<< /S /GoTo /D (subsection.7.3.1) >>
endobj
395 0 obj
(Tree-width and the cops-and-robber game)
endobj
396 0 obj
<< /S /GoTo /D (subsection.7.3.2) >>
endobj
399 0 obj
(Some properties of H-redistributions)
endobj
400 0 obj
<< /S /GoTo /D (subsection.7.3.3) >>
endobj
403 0 obj
(Set partitions on C-structures)
endobj
404 0 obj
<< /S /GoTo /D (subsection.7.3.4) >>
endobj
407 0 obj
(Game strategy)
endobj
408 0 obj
<< /S /GoTo /D (subsection.7.3.5) >>
endobj
411 0 obj
(Axiomatisation of C-structures in FOR)
endobj
412 0 obj
<< /S /GoTo /D (chapter.8) >>
endobj
415 0 obj
(Conclusions and further research)
endobj
416 0 obj
<< /S /GoTo /D (section.8.1) >>
endobj
419 0 obj
(Summary of results)
endobj
420 0 obj
<< /S /GoTo /D (section.8.2) >>
endobj
423 0 obj
(Future work)
endobj
424 0 obj
<< /S /GoTo /D (section*.26) >>
endobj
427 0 obj
(Bibliography)
endobj
428 0 obj
<< /S /GoTo /D [429 0 R /Fit ] >>
endobj
431 0 obj <<
/Length 530
/Filter /FlateDecode
>>
stream
xڕTMo0W((Ƕse[e=6 %9-Rdv0l|z4w@tޝDn0mGq.#ܛړXf!YF
q1'kdCqlni)BvA"ȎC]qpN7t7G4@d? <P33/H?NAt(9m?(gSt`ƻ4l̕%1y1ٞ|))KC0+̕xr۾O6TQK0'gFx{I )Ti[/clduDjՠRqSЂ"ٞRm_d/٪XaîsI^6b3b3h|<.9RM.퓆r
ld^Xi{EBFaJL!?xSOu1Djt)M*@%ie+H[sbJLܓ,pϨu7DU*%KG_!8I`|*bQ
endstream
endobj
429 0 obj <<
/Type /Page
/Contents 431 0 R
/Resources 430 0 R
/MediaBox [0 0 595.276 841.89]
/Parent 436 0 R
>> endobj
432 0 obj <<
/D [429 0 R /XYZ 97.899 762.853 null]
>> endobj
433 0 obj <<
/D [429 0 R /XYZ 98.899 728.504 null]
>> endobj
430 0 obj <<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F26 434 0 R /F28 435 0 R >>
/ProcSet [ /PDF /Text ]
>> endobj
439 0 obj <<
/Length 124
/Filter /FlateDecode
>>
stream
x3PHW0Pp2A;p)YX*)LMBR5B4-55u,5J4-5245R!\Dkh
4*!R@C42#S8T¨"/p Y<)
endstream
endobj
438 0 obj <<
/Type /Page
/Contents 439 0 R
/Resources 437 0 R
/MediaBox [0 0 595.276 841.89]
/Parent 436 0 R
>> endobj
440 0 obj <<
/D [438 0 R /XYZ 97.899 762.853 null]
>> endobj
437 0 obj <<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F36 441 0 R >>
/ProcSet [ /PDF /Text ]
>> endobj
444 0 obj <<
/Length 653
/Filter /FlateDecode
>>
stream
xڭUKs0W踚\[,208njh)}( fDzo])Z\}vrs*̕U'묎QyWejҨopVEfV7=:m*X">tP;UYcA26d934Al=t+KfN;ic+=kh17fSNdi0PcYTh @a/O$KmI-aQeVɇm"W`#"H: @I/|_t*crXX_MQNCI3ak_9GU|Y
&DwT"/i
fA N8;$]Bt 3{0@׆UzlT#
2GxHɠ6їhڝɼ&R>հO
zN iE1O?N{1E'=
BЭdEybQvx^ +M*LR%!V(UwS\ }fQ.9fpd;:V+>h؊7|8|8tNQԹ2QQaЩ+[t
SWZb3up^)`0mCḜ0tpD{+GzkX0#;dsZOn ד#
endstream
endobj
443 0 obj <<
/Type /Page
/Contents 444 0 R
/Resources 442 0 R
/MediaBox [0 0 595.276 841.89]
/Parent 436 0 R
>> endobj
442 0 obj <<
/ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R
/Font << /F79 445 0 R /F83 446 0 R /F28 435 0 R >>
/ProcSet [ /PDF /Text ]
>> endobj
449 0 obj <<
/Length 3313
/Filter /FlateDecode
>>
stream
xڝ[KW̱д|>9Q ÆHD9fFI4+iW+>fWOv#6?=_}wFy7ol|\7>bx>ŝE9^Ie2rŗ0le_o5/!9&mos&IGj2:I`pVӦwǪa7%p,@}vw<]?Re-s9pi!G"tQ[E^G1ODG
oLJL#j}H=%_h$|dz{ %VA%";
$ (7A9xBxEDv# qbTz.( B^eYg:?F0Xv?5$+iV=|NDiPcxr8a0}Qo3jw?oi3,+uY>SQAHF~ɛݖr[AаBk̂3@/W8` tMdlLޅl6]HH tRƆA"^wqlfIW3GB3myaef\?{jmm /RY3zΚaF['G%g0R
j!9|J1xH;$ڕeɦ Qz8Ϋ}d}ʔF9jm ilk