Two variable logic with ultimately periodic counting

DOI10.1137/22M1504792MaRDI QIDQ6573777FDOQ6573777

Authors: Michael Benedikt, Egor V. Kostylev, Tony Tan 

Publication date: 17 July 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Presburger arithmetictwo-variable logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Carathéodory bounds for integer cones
• Semigroups, Presburger formulas, and languages
• On the Decision Problem for Two-Variable First-Order Logic
• Two-variable first-order logic with equivalence closure
• On languages with two variables
• Regular graphs and the spectra of two-variable logic with counting
• Complexity of the two-variable fragment with counting quantifiers
• Fifty years of the spectrum problem: survey and new results
• On the complexity of integer programming
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Undecidability results on two-variable logics
• A Simple Proof of the Gale-Ryser Theorem
• Fragments of First-Order Logic
• Complexity Results for First-Order Two-Variable Logic with Counting
• A new description logic with set constraints and cardinality constraints on role successors
• Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic
• Complexity of modal logics with Presburger constraints
• The two-variable fragment with counting and equivalence
• One-variable logic meets Presburger arithmetic
• Complexity of the Guarded Two-variable Fragment with Counting Quantifiers
• Data-complexity of the two-variable fragment with counting quantifiers
• Two-variable logic with counting and a linear order
• The two-variable fragment with counting revisited
• Satisfiability and query answering in description logics with global and local cardinality constraints
• Two-variable logic with counting and trees
• Title not available (Why is that?)

This page was built for publication: Two variable logic with ultimately periodic counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6573777)