<p>As mentioned above: question answered by reference to FO(TC) games presented in <em>Finite Model Theory</em> by Ebbinghaus and Flum.</p>

CC BY-SA 4.0
2020-03-05T15:10:43.117Z
2020-03-05T15:10:43.117Z
Will Asness
<p>Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for <span class="math-container">$FO(TC)$</span> formulae? I am aware of EF games as they apply to first-order and second-order statements, but would like to be able to determine lower bounds for <span class="math-container">$FO(TC)$</span> queries on finite models. Any help in this direction would be appreciated!</p>

CC BY-SA 4.0
2020-03-04T07:42:50.110Z
I am not sure whether your 2nd sentence implies that you are aware of EF games for FO(TC). They were defined in a paper by Erichel Grädel, 1992, doi.org/10.1007/BFb0023764. A proof that uses them can be found in the book "Finite Model Theory" by Ebbinghaus and Flum.
Thomas S
CC BY-SA 4.0
2020-03-05T15:08:54.700Z
I have actually just taken the Ebbinghaus-Flum out of my school library- I believe I found the section you are referencing. Thank you very much for the help!
Will Asness
<cc.complexity-theory><lo.logic><finite-model-theory>
FO(TC) lower bounding games?
Will Asness
# FO(TC) lower bounding games?

(Asked by: username_0 on 2020-03-01)

Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for $FO(TC)$ formulae? I am aware of EF games as they apply to first-order and second-order statements, but would like to be able to determine lower bounds for $FO(TC)$ queries on finite models. Any help in this direction would be appreciated!

**Tags:** cc.complexity-theory, lo.logic, finite-model-theory

> **Comments:**
> **username_1**: I am not sure whether your 2nd sentence implies that you are aware of EF games for FO(TC). They were defined in a paper by Erichel Grädel, 1992, doi.org/10.1007/BFb0023764. A proof that uses them can be found in the book "Finite Model Theory" by Ebbinghaus and Flum.  
> **username_0**: I have actually just taken the Ebbinghaus-Flum out of my school library- I believe I found the section you are referencing. Thank you very much for the help!  

---

## 1 answers

### Answer by username_0 on 2020-03-05. Score: 2 | Accepted answer

As mentioned above: question answered by reference to FO(TC) games presented in *Finite Model Theory* by Ebbinghaus and Flum.


---

