The size of a formula as a measure of complexity

Lauri Hella, Jouko Väänänen

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKapitelVetenskapligPeer review

Sammanfattning

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.
Originalspråkengelska
Titel på gästpublikationLogic Without Borders : Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics
RedaktörerÅsa Hirvonen, Juha Kontinen, Roman Kossak, Andrés Villaveces
Antal sidor22
Förlagde Gruyter
Utgivningsdatum2015
Sidor193-214
ISBN (tryckt)978-1-61451-772-6
ISBN (elektroniskt)978-1-61451-687-3, 978-1-61451-932-4
StatusPublicerad - 2015
MoE-publikationstypA3 Del av bok eller annan forskningsbok

Publikationsserier

NamnOntos Mathematical Logic
FörlagWalter de Gruyter
Volym5
ISSN (elektroniskt)2198-235X

Vetenskapsgrenar

  • 111 Matematik

Citera det här

Hella, L., & Väänänen, J. (2015). The size of a formula as a measure of complexity. I Å. Hirvonen, J. Kontinen, R. Kossak, & A. Villaveces (Red.), Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics (s. 193-214). (Ontos Mathematical Logic; Vol. 5). de Gruyter.