1
$\begingroup$

Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists a closed-form formula)?

An Example:

Let the language consist of a binary predicate $T$ and variables $\{x,y,z\}$, and a domain $\mathcal{D}$ consisting of $n$ elements. Are there ways to write formulas in this language such that counting the number of models for these formulas is computationally easy? A trivial example would be $\forall x, y,z T(x,x)\land T(y,y) \land T(z,z)$, for which the number of models would be $2^{n^2 - n}$, are there more intricate ways to generate such formulas?

Additional Information:


Counting the number of models for a language with only two variables is known to be in complexity class P, whereas for more than two variables, it is known to be in #P, these results have been proven in the link below.

https://arxiv.org/abs/1412.1505

Closed forms formulas for counting any formula in FOL with 2 variables exist as well.

https://arxiv.org/abs/1804.10185

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.