Weighted first-order model counting in the two-variable fragment with counting quantifiers

被引：0

作者：

Kuželka O. ^{[1
]}

机构：

[1] Faculty of Electrical Engineering, Czech Technical University in Prague, Prague

来源：

Journal of Artificial Intelligence Research | 2021年 / 70卷

关键词：

21;

D O I：

10.1613/JAIR.1.12320

中图分类号：

学科分类号：

摘要：

It is known due to the work of Van den Broeck, Meert and Darwiche that weighted first-order model counting (WFOMC) in the two-variable fragment of first-order logic can be solved in time polynomial in the number of domain elements. In this paper we extend this result to the two-variable fragment with counting quantifiers. © 2021 AI Access Foundation. All rights reserved.

引用

页码：1281 / 1307

页数：26

共 50 条

[1] Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers
Kuzelka, Ondrej
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2021, 70 : 1281 - 1307
[2] Complexity of the Two-Variable Fragment with Counting Quantifiers
Ian Pratt-Hartmann
Journal of Logic, Language and Information, 2005, 14 (3) : 369 - 395
[3] Complexity of the guarded two-variable fragment with counting quantifiers
Pratt-Hartmann, Ian
JOURNAL OF LOGIC AND COMPUTATION, 2007, 17 (01) : 133 - 155
[4] Two-Variable First Order Logic with Counting Quantifiers: Complexity Results
Lodaya, Kamal
Sreejith, A. V.
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017, 2017, 10396 : 260 - 271
[5] Data-complexity of the two-variable fragment with counting quantifiers
Pratt-Hartmann, Ian
INFORMATION AND COMPUTATION, 2009, 207 (08) : 867 - 888
[6] Complexity results for first-order two-variable logic with counting
Pacholski, L
Szwast, W
Tendera, L
SIAM JOURNAL ON COMPUTING, 2000, 29 (04) : 1083 - 1117
[7] A Combinatorial Approach to Weighted Model Counting in the Two-Variable Fragment with Cardinality Constraints
Malhotra, Sagar
Serafini, Luciano
AIXIA 2021 - ADVANCES IN ARTIFICIAL INTELLIGENCE, 2022, 13196 : 137 - 152
[8] The two-variable fragment with counting and equivalence
Pratt-Hartmann, Ian
MATHEMATICAL LOGIC QUARTERLY, 2015, 61 (06) : 474 - 515
[9] The Two-Variable Fragment with Counting Revisited
Pratt-Hartmann, Ian
LOGIC, LANGUAGE, INFORMATION AND COMPUTATION, 2010, 6188 : 42 - 54
[10] Weighted model counting beyond two-variable logic
Kuusisto, Antti
Lutz, Carsten
LICS'18: PROCEEDINGS OF THE 33RD ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, 2018, : 619 - 628

← 1 2 3 4 5 →