Cover Image

Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers

Fuente: arXiv

Saved in:

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

Similar Items

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

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

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

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

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

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

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

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

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

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

Auto formalisation of Goedel's Second Incompleteness Theorem in Binary Recursive Arithmetic
by: Coquand, Thierry
Published: (2026)

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)

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

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)

Belief in Simplicial Complexes
by: Sink, Philip, et al.
Published: (2025)

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

CoLF Logic Programming as Infinitary Proof Exploration
by: Chen, Zhibo, et al.
Published: (2025)

Dependently Sorted Nominal Signatures
by: Fernández, Maribel, et al.
Published: (2025)

Satisfiability for Knowing How over Linear Plans is NP-complete
by: Areces, Carlos, et al.
Published: (2026)

A Construction of the Lie Algebra of a Lie Group in Isabelle/HOL
by: Schmoetten, Richard, et al.
Published: (2024)

The mu-calculus' Alternation Hierarchy is Strict over Non-Trivial Fusion Logics
by: Pacheco, Leonardo
Published: (2025)

Apply2Isar: Automatically Converting Isabelle/HOL Apply-Style Proofs to Structured Isar
by: Binder, Sage, et al.
Published: (2026)

Sensible Intersection Type Theories
by: Dezani-Ciancaglini, Mariangiola, et al.
Published: (2026)

Who Wins the Multi-Structural Game?
by: Fagin, Ronald, et al.
Published: (2025)

A Curiously Effective Backtracking Strategy for Connection Tableaux
by: Färber, Michael
Published: (2021)

The Limit of Recursion in State-based Systems
by: Afshari, Bahareh, et al.
Published: (2025)

Polymorphism Meets DHOL
by: Ranalter, Rhea, et al.
Published: (2026)

Efficient Normalization of Linear Temporal Logic
by: Esparza, Javier, et al.
Published: (2023)

Scroll nets
by: Donato, Pablo
Published: (2025)

Type Theory with Single Substitutions
by: Kaposi, Ambrus, et al.
Published: (2025)

Computation and Size of Interpolants for Hybrid Modal Logics
by: Jung, Jean Christoph, et al.
Published: (2026)

A Unified Gentzen-style Framework for Until-free LTL
by: Kamide, Norihiro, et al.
Published: (2024)