1. The Size of a Formula as a Measure of Complexity
- Author
-
Hella, Lauri, Väänänen, Jouko, Hirvonen, Åsa, Kontinen, Juha, Kossak, Roman, Villaveces, Andrés, and Department of Mathematics and Statistics
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,math.LO ,03C07 ,010201 computation theory & mathematics ,Computer Science::Logic in Computer Science ,010102 general mathematics ,111 Mathematics ,0102 computer and information sciences ,0101 mathematics ,01 natural sciences ,cs.LO - Abstract
25 pages 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.
- Published
- 2015
- Full Text
- View/download PDF