The Size of a Formula as a Measure of Complexity

DOI10.1515/9781614516873.193MaRDI QIDQ5213568zbMATH OpenOpenAlexFDO

Authors Lauri Hella, Jouko Väänänen

Publication date 3 February 2020

Published in Logic Without Borders (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.4803

Mathematics Subject Classification ID

Classical first-order logic (03B10) Descriptive complexity and finite models (68Q19)

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.

Cited in

(7)

• On the succinctness of atoms of dependency
• The strategic balance of games in logic
• Game characterizations for the number of quantifiers
• Multi-structural games and number of quantifiers
• Multi-structural games and beyond
• On the number of quantifiers needed to define Boolean functions
• Description complexity of unary structures in first-order logic with links to entropy

This page was built for publication: The Size of a Formula as a Measure of Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5213568)