The Succinctness of First-order Logic over Modal Logic via a Formula Size Game

zbMATH Open1400.03022arXiv1604.07225MaRDI QIDQ4636046FDOQ4636046

Authors: Lauri Hella, Miikka Vilander 

Publication date: 23 April 2018

Abstract: We propose a new version of formula size game for modal logic. The game characterizes the equivalence of pointed Kripke-models up to formulas of given numbers of modal operators and binary connectives. Our game is similar to the well-known Adler-Immerman game. However, due to a crucial difference in the definition of positions of the game, its winning condition is simpler, and the second player (duplicator) does not have a trivial optimal strategy. Thus, unlike the Adler-Immerman game, our game is a genuine two-person game. We illustrate the use of the game by proving a nonelementary succinctness gap between bisimulation invariant first-order logic FO and (basic) modal logic ML.

Full work available at URL: https://arxiv.org/abs/1604.07225

Recommendations

• Formula size games for modal logic and \(\mu\)-calculus
• Some exponential lower bounds on formula-size in modal logic
• On the succinctness of some modal logics
• The succinctness of first-order logic on linear orders
• On the proof-theory of two formalisations of modal first-order logic
• An Ehrenfeucht-Fraïssé game for inquisitive first-order logic
• scientific article; zbMATH DE number 1670490
• GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC
• On the complexity of elementary modal logics
• About effective versions of game theoretical semantics for first-order logic

zbMATH Keywords

succinctness\(n\)-bisimulationbisimulation invariant first-order logicformula size game

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Classical first-order logic (03B10)

Cited In (9)

• Formula size games for modal logic and \(\mu\)-calculus
• Title not available (Why is that?)
• On the relative succinctness of two extensions by definitions of multimodal logic
• An \(n!\) lower bound on formula size
• On the size of shortest modal descriptions
• Frame-validity games and lower bounds on the complexity of modal axioms
• Some exponential lower bounds on formula-size in modal logic
• On the succinctness of atoms of dependency
• On the succinctness of some modal logics

This page was built for publication: The Succinctness of First-order Logic over Modal Logic via a Formula Size Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636046)