Ronald Fagin

The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted towards favoring the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game (the game with the seemingly more favorable rules for the duplicator) to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win.

Many-valued logics, in general, and real-valued logics, in particular, usually focus on a notion of consequence based on preservation of full truth, typically represented by the value $1$ in the semantics given in the real unit interval $[0,1]$. In a recent paper [Foundations of Reasoning with Uncertainty via Real-valued Logics, Proceedings of the National Academy of Sciences 121(21): e2309905121, 2024], Ronald Fagin, Ryan Riegel, and Alexander Gray have introduced a new paradigm that allows to deal with inferences in propositional real-valued logics based on a rich class of sentences, multi-dimensional sentences, that talk about combinations of any possible truth values of real-valued formulas. They have proved a strong completeness result that allows one to derive exactly what information can be inferred about the combinations of truth values of a collection of formulas given information about the combinations of truth values of a finite number of other collections of formulas. In this paper, we extend that work to the first-order (as well as modal) logic of multi-dimensional sentences. We give a parameterized axiomatic system that covers any reasonable logic and prove a corresponding completeness theorem, first assuming that the structures are defined over a fixed domain, and later for the logics of varying domains. As a by-product, we also obtain a zero-one law for finitely-valued versions of these logics. Since several first-order real-valued logics are known not to have recursive axiomatizations but only infinitary ones, our system is by force akin to infinitary systems.

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference $(\sigma \vdash_\mathrm{v} \varphi$ if for every substitution $\tau$, the validity of $\tau \lbrack\sigma\rbrack$ entails the validity of $\tau\lbrack\varphi\rbrack)$, and truth inference $(\sigma \vdash_\mathrm{t} \varphi$ if for every substitution $\tau$, the truth of $\tau\lbrack\sigma\rbrack$ entails the truth of $\tau\lbrack\varphi\rbrack)$. In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic

We consider the issue of what an agent or a processor needs to know in order to know that its messages are true. This may be viewed as a first step to a general theory of cooperative communication in distributed systems. An honest message is one that is known to be true when it is sent (or said). If every message that is sent is honest, then of course every message that is sent is true. Various weaker considerations than honesty are investigated with the property that provided every message sent satisfies the condition, then every message sent is true

Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence.

The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted towards favoring the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win

We do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs of up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' beliefs have a countable description, or putting it another way, have a "countable amount of information". The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a "countable description".