## Bounded variable logics and counting: a study in finite models |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Definitions and Preliminaries | 15 |

The Games and Their Analysis | 51 |

Copyright | |

6 other sections not shown

### Other editions - View all

Bounded Variable Logics and Counting: A Study in Finite Models Martin Otto No preview available - 2016 |

### Common terms and phrases

Abiteboul and Vianu admits Ptime arity atomic types automorphism binary relation boolean query capture Ptime cardinality Lindstrom quantifiers characterized closure complete invariant complexity classes Consider Corollary corresponding counting terms Definition denote disjoint equivalence relation exactly Example fc-graph fc-th power fin[r finite graphs finite model theory finite relational finite structures first-order logic first-order variables fixed-point logic fixed-point process formalization formulae FP and PFP FP+C and PFP+C functor game tableau global relation Immerman inductive infinitary logic interpretation isomorphism Lemma lexicographic lexicographic ordering linear ordering logic with counting mapping natural nodes obtained ordered structures parameters pebble polynomial pre-ordering problem properties Proposition Pspace Ptime algorithm Ptime canonization Ptime computable Ptime inversion quantifier free quantifier Q quotient r-ary r-structures realization recursive presentation relational structures respect restriction result second sort second-order variables semantic Sketch of Proof stable colouring stan[r subset Theorem three variable trivial tuple tures two-sorted