Cover Image

Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tóth, Jan, Kuželka, Ondřej
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers
by: Sun, Shixin, et al.
Published: (2026)

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
by: Kuang, Qipeng, et al.
Published: (2025)

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

Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
by: Kůla, Václav, et al.
Published: (2025)

Bridging Weighted First Order Model Counting and Graph Polynomials
by: Kuang, Qipeng, et al.
Published: (2024)

On Knowledge Compilation For Two-Variable First-Order Logic
by: Meng, Qiaolan, et al.
Published: (2026)

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

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

Lifted Algorithms for Symmetric Weighted First-Order Model Sampling
by: Wang, Yuanhong, et al.
Published: (2023)

Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity
by: Meng, Qiaolan, et al.
Published: (2025)

Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
by: Kuijer, Louwe, et al.
Published: (2025)

Towards Practical First-Order Model Counting
by: Kidambi, Ananth K., et al.
Published: (2025)

On Lower Bounding Minimal Model Count
by: Kabir, Mohimenul, et al.
Published: (2024)

Putting Perspective into OWL [sic]: Complexity-Neutral Standpoint Reasoning for Ontology Languages via Monodic S5 over Counting Two-Variable First-Order Logic (Extended Version with Appendix)
by: Álvarez, Lucía Gómez, et al.
Published: (2025)

Model Counting for Dependency Quantified Boolean Formulas
by: Fung, Long-Hin, et al.
Published: (2025)

Learning Aggregate Queries Defined by First-Order Logic with Counting
by: van Bergerem, Steffen, et al.
Published: (2024)

Craig Interpolation for Decidable First-Order Fragments
by: Cate, Balder ten, et al.
Published: (2023)

Learning Concepts Definable in First-Order Logic with Counting
by: van Bergerem, Steffen
Published: (2019)

The Complexity of Fragments of Second-Order HyperLTL
by: Regaud, Gaëtan, et al.
Published: (2025)

Finite Variable Counting Logics with Restricted Requantification
by: Raßmann, Simon, et al.
Published: (2024)

Termination of Graph Transformation Systems Using Weighted Subgraph Counting
by: Overbeek, Roy, et al.
Published: (2023)

About the Expressive Power and Complexity of Order-Invariance with Two Variables
by: Bednarczyk, Bartosz, et al.
Published: (2023)

A Game for Counting Logic Formula Size and an Application to Linear Orders
by: Fournier, Gregoire, et al.
Published: (2025)

Numerical Considerations in Weighted Model Counting
by: Bryant, Randal E.
Published: (2025)

Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
by: Lutz, Carsten, et al.
Published: (2024)

Alternating Quantifiers in Uniform One-Dimensional Fragments with an Excursion into Three-Variable Logic
by: Fiuk, Oskar, et al.
Published: (2024)

A Decidable Bundled Fragment of First-Order Modal Logic Without Finite Model Property
by: Joshi, Varad, et al.
Published: (2025)

Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property
by: Elad, Neta, et al.
Published: (2026)

On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
by: Nakamura, Yoshiki
Published: (2023)

On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
by: Haase, Christoph, et al.
Published: (2024)

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
by: Lichter, Moritz
Published: (2022)

Minimal Model Counting via Knowledge Compilation
by: Kabir, Mohimenul
Published: (2024)

On Top-Down Pseudo-Boolean Model Counting
by: Yang, Suwei, et al.
Published: (2025)

Model Counting in the Wild
by: Shaw, Arijit, et al.
Published: (2024)

The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
by: Pratt-Hartmann, Ian
Published: (2017)

Efficient Implementation of an Abstract Domain of Quantified First-Order Formulas
by: Frenkel, Eden, et al.
Published: (2024)

When Do You Start Counting? Revisiting Counting and Pnueli Modalities in Timed Logics
by: Ho, Hsi-Ming, et al.
Published: (2024)

Solving Combinatorial Counting Problems with Weighted First-Order Model Counting
by: Wang, Yuanhong, et al.
Published: (2026)

Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
by: Kieronski, Emanuel, et al.
Published: (2016)

Prime Factorization in Models of PV$_1$
by: Ježil, Ondřej
Published: (2025)