This article surveys various complexity and expressiveness results on different forms of logic
programming. The main focus is on decidable forms of logic programming, in particular …

Recent studies have discovered that Chain-of-Thought prompting (CoT) can dramatically
improve the performance of Large Language Models (LLMs), particularly when dealing with …

An historical overview of computational complexity is presented. Emphasis is on the
fundamental issues of defining the intrinsic computational complexity of a problem and …

Despite their omnipresence in modern NLP, characterizing the computational power of
transformer neural nets remains an interesting open question. We prove that transformers …

The problem of identifying an unknown regular set from examples of its members and
nonmembers is addressed. It is assumed that the regular set is presented by a minimally …

The problem of deciding whether a given propositional formula in conjunctive normal form is
satisfiable has been widely studied. I t is known that, when restricted to formulas having only …

Alternation is a generalization of nondeterminism in which existential and universal
quantitiers can alternate during the course of a computation, whereas in a nondeterministic …

Two complexity measures for query languages are proposed. Data complexity is the
complexity of evaluating a query in the language as a function of the size of the database …

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 …

New algorithms for deciding whether a (propositional) Horn formula is satisfiable are
presented. If the Horn formula A contains K distinct propositional letters and if it is assumed …