Cover Image

Data-Complexity of the Two-Variable Fragment with Counting Quantifiers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pratt-Hartmann, Ian
Format:	Preprint
Published:	2008
Subjects:	Logic in Computer Science Artificial Intelligence Computational Complexity F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Complexity of the Numerically Definite Syllogistic and Related Fragments
by: Pratt-Hartmann, Ian
Published: (2007)

Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2004)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

Logics for the Relational Syllogistic
by: Pratt-Hartmann, Ian, et al.
Published: (2008)

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
by: Ito, Sohei, et al.
Published: (2026)

The Fluted Fragment with Transitive Relations
by: Pratt-Hartmann, Ian, et al.
Published: (2020)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Set Theory in the Foundation of Math; Internal Classes and External Sets
by: Levin, Leonid A.
Published: (2022)

Two-Level Type Theory and Applications
by: Annenkov, Danil, et al.
Published: (2017)

The Guarded Fragment with Nested Equivalences
by: Fiuk, Oskar
Published: (2026)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

The Hamiltonian Syllogistic
by: Pratt-Hartmann, Ian
Published: (2010)

Towards Automated Readable Proofs of Ruler and Compass Constructions
by: Marinković, Vesna, et al.
Published: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

Extracting Policies from Quantified Answer Set Programs
by: Diéguez, Martín, et al.
Published: (2026)

Solving Quantified Modal Logic Problems by Translation to Classical Logics
by: Steen, Alexander, et al.
Published: (2022)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Complexity of Łukasiewicz Modal Probabilistic Logics
by: Kozhemiachenko, Daniil, et al.
Published: (2025)

On the Formal Metatheory of the Pure Type Systems using One-sorted Variable Names and Multiple Substitutions
by: Urciuoli, Sebastián
Published: (2025)

Two Remarks about Game Semantics of Classical Logic
by: Coquand, Thierry
Published: (2026)

SM-based Semantics for Answer Set Programs Containing Conditional Literals and Arithmetic
by: Hansen, Zachary, et al.
Published: (2025)

Satisfiability in Łukasiewicz logic and its unbounded relative
by: Haniková, Zuzana, et al.
Published: (2025)

Semi-Substructural Logics à la Lambek
by: Wan, Cheng-Syuan
Published: (2024)

A Non-Wellfounded and Labelled Sequent Calculus for Bimodal Provability Logic
by: Becker, Justus
Published: (2025)

A Topological Rewriting of Tarski's Mereogeometry
by: Barlatier, Patrick, et al.
Published: (2025)

Extensions of K5: Proof Theory and Uniform Lyndon Interpolation
by: van der Giessen, Iris, et al.
Published: (2023)

Logic of Sets with Atoms
by: Masters, Jake
Published: (2025)

Cardinality and Representation of Stone Relation Algebras
by: Furusawa, Hitoshi, et al.
Published: (2023)

The Lambda Calculus is Quantifiable
by: Maestracci, Valentin, et al.
Published: (2024)

Computation as a Game
by: Bilokon, Paul Alexander
Published: (2025)

Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality
by: Tsamoura, Efthymia, et al.
Published: (2024)

Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology
by: Jung, Jean Christoph, et al.
Published: (2023)

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)