39 citations · 102 across the 36 of their papers we have counts for
40 papers
Accepting-Path Counting at the One-Tape Threshold
Ondřej Kuželka
We observe that the classical time threshold for one-tape Turing machines is also a threshold for their accepting-path counts. Below it, every nondeterministic one-tape m…
Unary Functions, Automorphisms, and Unlabeled First-Order Model Counting
Ondřej Kuželka
Every fixed first-order sentence determines an enumerative sequence , counting its models on the labeled domain . We study the complexity of th…
Weighted First-Order Model Counting over Ordered Domains
Jan Tóth, Qipeng Kuang, Kuncheng Zou +4
The Weighted First-Order Model Counting Problem (WFOMC) asks for the weighted sum of models of a first-order logical sentence over a domain. It is a fundamental problem in statisti…
Parallel Noising in Neural Markov Logic Networks
Peter Jung, Giuseppe Marra, Ondrej Kuzelka
Neural Markov Logic Networks (NMLNs) are a flexible neurosymbolic relational model. Previous work has shown that, although NMLNs achieve strong performance as generative models for…
CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models
Yuxu Zhou, Ondřej Kuželka, Yuyi Wang +2
We present CombEval, a dynamic benchmark for evaluating combinatorial counting in large language models. CombEval represents each problem as a typed Cofola specification over entit…
Solving Combinatorial Counting Problems with Weighted First-Order Model Counting
Yuanhong Wang, Juhua Pu, Yuxu Zhou +2
Combinatorial counting problems pervade artificial intelligence, statistics, and discrete mathematics. Whether the task is enumerating subsets, multisets, permutations, partitions,…
On Knowledge Compilation For Two-Variable First-Order Logic
Qiaolan Meng, Juhua Pu, Hongting Niu +3
Knowledge compilation transforms logical theories into circuit representations that support efficient reasoning. We study this problem for propositional groundings of FO2, the two-…
A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers
Shixin Sun, Astrid Klipfel, Ondřej Kuželka +2
Weighted first-order model counting (WFOMC) is a central task in lifted probabilistic inference: It asks for the weighted sum of all models of a first-order sentence over a finite…
Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
Václav Kůla, Qipeng Kuang, Yuyi Wang +2
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on…
Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
Qipeng Kuang, Václav Kůla, Ondřej Kuželka +2
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. The boundary between f…
Faster Lifting for Ordered Domains with Predecessor Relations
Kuncheng Zou, Jiahao Mai, Yonggang Zhang +4
We investigate lifted inference on ordered domains with predecessor relations, where the elements of the domain respect a total (cyclic) order, and every element has a distinct (cl…
Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity
Qiaolan Meng, Juhua Pu, Hongting Niu +3
We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables (). Specifically, given an sentence and…
Bridging Weighted First Order Model Counting and Graph Polynomials
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang +1
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in ti…
Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat
Jan Tóth, Ondřej Kuželka
We study the time complexity of the weighted first-order model counting (WFOMC) over the logical language with two variables and counting quantifiers. The problem is known to be so…
Lifted Algorithms for Symmetric Weighted First-Order Model Sampling
Yuanhong Wang, Juhua Pu, Yuyi Wang +1
Weighted model counting (WMC) is the task of computing the weighted sum of all satisfying assignments (i.e., models) of a propositional formula. Similarly, weighted model sampling…
On Discovering Interesting Combinatorial Integer Sequences
Martin Svatoš, Peter Jung, Jan Tóth +2
We study the problem of generating interesting integer sequences with a combinatorial interpretation. For this we introduce a two-step approach. In the first step, we generate firs…
On Exact Sampling in the Two-Variable Fragment of First-Order Logic
Yuanhong Wang, Juhua Pu, Yuyi Wang +1
In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al. -- how to efficiently sample a model of a given first-order sentence on a finite…
Lifted Inference with Linear Order Axiom
Jan Tóth, Ondřej Kuželka
We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula , domain siz…
First-Order Context-Specific Likelihood Weighting in Hybrid Probabilistic Logic Programs
Nitesh Kumar, Ondrej Kuzelka, Luc De Raedt
Statistical relational AI and probabilistic logic programming have so far mostly focused on discrete probabilistic models. The reasons for this is that one needs to provide constru…
Context-Specific Likelihood Weighting
Nitesh Kumar, Ondřej Kuželka
Sampling is a popular method for approximate inference when exact inference is impractical. Generally, sampling algorithms do not exploit context-specific independence (CSI) proper…
Learning with Molecules beyond Graph Neural Networks
Gustav Sourek, Filip Zelezny, Ondrej Kuzelka
We demonstrate a deep learning framework which is inherently based in the highly expressive language of relational logic, enabling to, among other things, capture arbitrarily compl…
Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers
Ondrej Kuzelka
It is known due to the work of Van den Broeck et al [KR, 2014] that weighted first-order model counting (WFOMC) in the two-variable fragment of first-order logic can be solved in t…
Lifted Inference in 2-Variable Markov Logic Networks with Function and Cardinality Constraints Using Discrete Fourier Transform
Ondrej Kuzelka
In this paper we show that inference in 2-variable Markov logic networks (MLNs) with cardinality and function constraints is domain-liftable. To obtain this result we use existing…
Beyond Graph Neural Networks with Lifted Relational Neural Networks
Gustav Sourek, Filip Zelezny, Ondrej Kuzelka
We demonstrate a declarative differentiable programming framework based on the language of Lifted Relational Neural Networks, where small parameterized logic programs are used to e…