arXiv:1208.4803 Abstract | arXiv Analytics

arXiv:1208.4803 [math.LO]Abstract References Reviews Resources

The size of a formula as a measure of complexity

Published 2012-08-23Version 1

We introduce a refinement of the usual Ehrenfeucht-Fra\"{\i}ss\'e 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.

Comments: 25 pages

Categories: math.LO, cs.LO

Subjects: 03C07

Keywords: complexity, first-order predicate logic, second version works, first version characterizes, propositional logic

Related articles: Most relevant | Search more

arXiv:0905.2880 [math.LO] (Published 2009-05-18)

Counting proofs in propositional logic

René David, Marek Zaionc

arXiv:1412.7998 [math.LO] (Published 2014-12-26)

Propositional Logics of Dependence and Independence, Part I

Fan Yang, Jouko Väänänen

arXiv:2303.14022 [math.LO] (Published 2023-03-24)