Papers for

developers of logic-based ai systems

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Characterizing when certain logic theories have finite models

A characterization of the finite model property for $ω$-categorical theories

Abstract: A first-order theory $T$ has the {\em finite model property} if every first-order sentence that is implied by $T$ has a finite model. We give a characterization of when a complete $ω$-categorical theory $T$ has the finite model property. The characterization makes it possible to transfer stability theoretic results in [29] to certain classes of finite structures. This approach also gives information concerning properties that a sequence of finite ``base structures'' of ever larger size must have in order for its random expansions to a larger vocabulary to have a chance to satisfy a convergence law for first-order logic.

Mon 12 OctLogic in Computer Science
The gist
Some logical theories always have infinite examples, but others can be understood entirely through finite examples. This paper shows how to tell when a particular kind of logical theory, known for being well-behaved and unique in structure, guarantees that all its implied statements can be satisfied by finite models. By doing this, the authors provide a way to connect deep logical properties to patterns found in families of finite structures and their random expansions. This insight helps understand how larger and more complex finite structures might behave logically.
Open → 2610.16163v1