Quantifiers Closed Under Partial Polymorphisms

Anuj Dawar, Lauri Hella

Tutkimustuotos: KonferenssiartikkeliTieteellinenvertaisarvioitu

4 Lataukset (Pure)

Abstrakti

We study Lindström quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). When the algebra of polymorphisms of a finite structure B satisfies certain equations, this gives rise to a natural closure condition on the class of structures that map homomorphically to B. The collection of quantifiers that satisfy closure conditions arising from a fixed set of equations are rather more general than those arising as CSP. For any such conditions P, we define a pebble game that delimits the distinguishing power of the infinitary logic with all quantifiers that are P-closed. We use the pebble game to show that the problem of deciding whether a system of linear equations is solvable in Z /2 Z is not expressible in the infinitary logic with all quantifiers closed under a near-unanimity condition.

AlkuperäiskieliEnglanti
Otsikko32nd EACSL Annual Conference on Computer Science Logic, CSL 2024
ToimittajatAniello Murano, Alexandra Silva
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)9783959773102
DOI - pysyväislinkit
TilaJulkaistu - helmik. 2024
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaEACSL Annual Conference on Computer Science Logic - Naples, Italia
Kesto: 19 helmik. 202423 helmik. 2024

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta288
ISSN (painettu)1868-8969

Conference

ConferenceEACSL Annual Conference on Computer Science Logic
Maa/AlueItalia
KaupunkiNaples
Ajanjakso19/02/2423/02/24

Rahoitus

Funding Anuj Dawar: funded by UK Research and Innovation (UKRI) under the UK government’s Horizon Europe funding guarantee: grant number EP/X028259/1.

RahoittajatRahoittajan numero
UK Research and Innovation
HORIZON EUROPE Framework ProgrammeEP/X028259/1

    Julkaisufoorumi-taso

    • Jufo-taso 1

    !!ASJC Scopus subject areas

    • Software

    Sormenjälki

    Sukella tutkimusaiheisiin 'Quantifiers Closed Under Partial Polymorphisms'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä