2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas S Mar 4 at 7:42
  • $\begingroup$ 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! $\endgroup$ – Will Asness Mar 5 at 15:08
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.