Characterizing neural networks in terms of better-understood formal systems has the
potential to yield new insights into the power and limitations of these networks. Doing so for …

Finite model theory is an area of mathematical logic that grew out of computer science
applications. The main sources of motivational examples for finite model theory are found in …

In this paper we show that Ω (n) variables are needed for first-order logic with counting to
identify graphs on n vertices. The k-variable language with counting is equivalent to the (k …

A basic issue in computer science is the complexity of problems. Computational complexity
measures how much time or memory is needed as a function of the input problem size …

This handbook provides an up-to-date compendium of fundamental computer science
topics, techniques, and applications. Along with updating and revising many of the existing …

As transformers have gained prominence in natural language processing, some researchers
have investigated theoretically what problems they can and cannot solve, by treating …

In this paper we ask the question,“What must be added to first-order logic plus least-fixed
point to obtain exactly the polynomial-time properties of unordered graphs?” We consider …

Publisher Summary This chapter discusses the concepts needed for defining the complexity
classes. A complexity class is a set of problems of related resource-based complexity. A …

Pattern queries are widely used in complex event processing (CEP) systems. Existing
pattern matching techniques, however, can provide only limited performance for expensive …

One way to interpret the reasoning power of transformer-based language models is to
describe the types of logical rules they can resolve over some input text. Recently, Chiang et …