ANDREI-60: Papers with Abstracts

Abstract. Simple counting quantifiers that can be used to compare the number of role successors of an individual or the cardinality of a concept with a fixed natural number have been employed in Description Logics (DLs) for more than two decades under the respective names of number restrictions and cardinality restriction on concepts. Recently, we have considerably extended the expressivity of such quantifiers by allowing to impose set and cardinality constraints formulated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA) on sets of role successors and concepts, respectively. We were able to prove that this extension does not increase the complexity of reasoning.

In the present paper, we investigate the expressive power of the DLs obtained this way, using appropriate bisimulation characterizations and 0--1 laws as tools for distinguishing the expressiveness of different logics. In particular, we show that, in contrast to most classical DLs, these logics are no longer expressible in first-order predicate logic (FOL), and we characterize their first-order fragments. In most of our previous work on DLs with QFBAPA-based set and cardinality constraints we have employed finiteness restrictions on interpretations to ensure that the obtained sets are finite. Here we dispense with these restrictions to make the comparison with classical DLs, where one usually considers arbitrary models rather than finite ones, easier. It turns out that doing so does not change the complexity of reasoning.

Abstract. In mathematical applications, category theory remains a contentious issue, with enthusiastic fans and a skeptical
majority. In a muted form this split applies to the authors of
this note. When we learned that the only mathematically sound
foundation of topological quantum computing in the literature is
based on category theory, the skeptical author suggested to "decategorize" the foundation. But we discovered, to our surprise, that
category theory (or something like it) is necessary for the purpose,
for computational reasons. The goal of this note is to give a high-
level explanation of that necessity, which avoids details and which
suggests that the case of topological quantum computing is far
from unique.

Abstract. It is a long-standing problem in graph theory to prove or disprove the \emph{reconstruction conjecture}, also known as the Kelly-Ulam conjecture. This conjecture states that every simple graph on at least three vertices is \emph{reconstructible}, which means that the isomorphism class of such a graph is uniquely determined by the isomorphism classes of its vertex-deleted subgraphs. In this talk, the notion of reconstructing is extended from graphs to instances of the constraint satisfaction problem (CSP): an instance is \emph{reconstructible} if its isomorphism class is uniquely determined by the isomorphism classes of its constraint-deleted subinstances. Questions of interest include not only questions about reconstructible CSP instances but also about CSP instances with reconstructible properties and parameters such as the existence of solutions or the number of solutions. As shown in the talk, such questions can be answered using techniques borrowed and adapted from graph reconstruction. In particular, Lov\'{a}sz's method of counting graph homomorphisms \cite{Lov72} is adapted to characterize CSP instances for which the number of solutions is reconstructible.