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 conjectureArticle

Authors: Siddharth Bhaskar ORCID; 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

    Consultation statistics

    This page has been seen 1581 times.
    This article's PDF has been downloaded 414 times.