The size of a formula as a measure of complexity

2012/08/23 by Lauri Hella, Hella, Lauri, Jouko Väänänen +1 · 2 citations
Computer Science · Mathematics · #03C07 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.LO #math.LO #msc:03C07

paper · pdf · doi:10.48550/arxiv.1208.4803

25 pages

arxiv created 2012/08/23 · arxiv updated 2012/08/24

Abstract

We introduce a refinement of the usual Ehrenfeucht-Fra"ıssé game. The new game will help us make finer distinctions than the traditional one. In particular, it can be used to measure the size formulas needed for expressing a given property. We will give two versions of the game: the first version characterizes the size of formulas in propositional logic, and the second version works for first-order predicate logic.

Cited by

• A Game for Counting Logic Formula Size and an Application to Linear Orders
• Formula size game and model checking for modal substitution calculus

Related

• A Game for Counting Logic Formula Size and an Application to Linear Orders
• Size and Logic
• On the Number of Quantifiers as a Complexity Measure
• The Succinctness of First-order Logic over Modal Logic via a Formula Size Game
• The ghosts of forgotten things: A study on size after forgetting