pith. sign in

arxiv: 1208.4803 · v1 · pith:WB6YB4NWnew · submitted 2012-08-23 · 🧮 math.LO · cs.LO

The size of a formula as a measure of complexity

classification 🧮 math.LO cs.LO
keywords gamesizeformulaslogicmeasureversionwillcharacterizes
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.