Browsing by Subject "Ehrenfeucht-Fraïssé game"

The question of how much one logic can express compared to another can be measured with formula size, and important results have been reached with formula size games. These games can separate two classes of structures from each other within a given number of moves. Since formula size can also be expressed through extended syntax trees, we are interested in seeing what attributes or benefits games or trees have in different situations. First-order logic and its fragments are particularly interesting. This thesis discusses formula size games and analyses their use in known succinctness results between fragments of first-order logic and also between first-order logic and modal logic. While extended syntax trees may be preferred for results between fragments of first-order logic, the formula size game can be easily constructed for different languages. We find that both methods have advantages depending on the two logics that are compared to each other.