The Size of a Formula as a Measure of Complexity

Open Access
Authors
Publication date 2015
Host editors
  • Å. Hirvonen
  • J. Kontinen
  • R. Kossak
  • A. Villaveces
Book title Logic without borders: essays on set theory, model theory, philosophical logic, and philosophy of mathematics
ISBN
  • 9781614517726
Series Ontos Mathematical Logic, 5
Pages (from-to) 193-214
Publisher Berlin: De Gruyter
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
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.
Document type Chapter
Language English
Published at http://www.degruyter.com/viewbooktoc/product/429076
Downloads
1208.4803v1.pd (Submitted manuscript)
Permalink to this page
Back