Siddharth Bhaskar ; Alex Kruckman - Tameness in least fixed-point logic and McColm's conjecture

lmcs:4419 - Logical Methods in Computer Science, January 22, 2021, Volume 17, Issue 1 - https://doi.org/10.23638/LMCS-17(1:2)2021
Tameness in least fixed-point logic and McColm's conjecture

Authors: Siddharth Bhaskar ; Alex Kruckman

We investigate four model-theoretic tameness properties in the context of least fixed-point logic over a family of finite structures. We find that each of these properties depends only on the elementary (i.e., first-order) limit theory, and we completely determine the valid entailments among them. In contrast to the context of first-order logic on arbitrary structures, the order property and independence property are equivalent in this setting. McColm conjectured that least fixed-point definability collapses to first-order definability exactly when proficiency fails. McColm's conjecture is known to be false in general. However, we show that McColm's conjecture is true for any family of finite structures whose limit theory is model-theoretically tame.


Volume: Volume 17, Issue 1
Published on: January 22, 2021
Accepted on: November 11, 2020
Submitted on: April 2, 2018
Keywords: Mathematics - Logic,Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 223 times.
This article's PDF has been downloaded 165 times.