Tameness in least fixed-point logic and mccolm’s conjecture

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Tameness in least fixed-point logic and mccolm’s conjecture. / Bhaskar, Siddharth; Kruckman, Alex.

In: Logical Methods in Computer Science, Vol. 17, No. 1, 2, 2021, p. 2:1-2:16.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Bhaskar, S & Kruckman, A 2021, 'Tameness in least fixed-point logic and mccolm’s conjecture', Logical Methods in Computer Science, vol. 17, no. 1, 2, pp. 2:1-2:16. https://doi.org/10.23638/LMCS-17(1:2)2021

APA

Bhaskar, S., & Kruckman, A. (2021). Tameness in least fixed-point logic and mccolm’s conjecture. Logical Methods in Computer Science, 17(1), 2:1-2:16. [2]. https://doi.org/10.23638/LMCS-17(1:2)2021

Vancouver

Bhaskar S, Kruckman A. Tameness in least fixed-point logic and mccolm’s conjecture. Logical Methods in Computer Science. 2021;17(1):2:1-2:16. 2. https://doi.org/10.23638/LMCS-17(1:2)2021

Author

Bhaskar, Siddharth ; Kruckman, Alex. / Tameness in least fixed-point logic and mccolm’s conjecture. In: Logical Methods in Computer Science. 2021 ; Vol. 17, No. 1. pp. 2:1-2:16.

Bibtex

@article{4ede7ac6b2274008863fb523519499b2,
title = "Tameness in least fixed-point logic and mccolm{\textquoteright}s conjecture",
abstract = "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{\textquoteright}s conjecture is known to be false in general. However, we show that McColm{\textquoteright}s conjecture is true for any family of finite structures whose limit theory is model-theoretically tame.",
keywords = "Finite model theory, Inductive definability, Least fixed-point logic, Model-theoretic dividing lines",
author = "Siddharth Bhaskar and Alex Kruckman",
note = "Publisher Copyright: {\textcopyright} Siddharth Bhaskar and Alex Kruckman.",
year = "2021",
doi = "10.23638/LMCS-17(1:2)2021",
language = "English",
volume = "17",
pages = "2:1--2:16",
journal = "Logical Methods in Computer Science",
issn = "1860-5974",
publisher = "International Federation for Computational Logic",
number = "1",

}

RIS

TY - JOUR

T1 - Tameness in least fixed-point logic and mccolm’s conjecture

AU - Bhaskar, Siddharth

AU - Kruckman, Alex

N1 - Publisher Copyright: © Siddharth Bhaskar and Alex Kruckman.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Finite model theory

KW - Inductive definability

KW - Least fixed-point logic

KW - Model-theoretic dividing lines

UR - http://www.scopus.com/inward/record.url?scp=85101617873&partnerID=8YFLogxK

U2 - 10.23638/LMCS-17(1:2)2021

DO - 10.23638/LMCS-17(1:2)2021

M3 - Journal article

AN - SCOPUS:85101617873

VL - 17

SP - 2:1-2:16

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 1

M1 - 2

ER -

ID: 269503322