Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Program schemes, arrays, Lindström quantifiers and zero-one laws.

Stewart, I.A. (2002) 'Program schemes, arrays, Lindström quantifiers and zero-one laws.', Theoretical computer science., 275 (1-2). pp. 283-310.

Abstract

We characterize the class of problems accepted by a class of program schemes with arrays, NPSA, as the class of problems defined by the sentences of a logic formed by extending first-order logic with a particular uniform (or vectorized) sequence of Lindström quantifiers. A simple extension of a known result thus enables us to prove that our logic, and consequently our class of program schemes, has a zero-one law. However, we use another existing result to show that there are problems definable in a basic fragment of our logic, and so also accepted by basic program schemes, which are not definable in bounded-variable infinitary logic. As a consequence, the class of problems NPSA is not contained in the class of problems defined by the sentences of partial fixed-point logic even though in the presence of a built-in successor relation, both NPSA and partial fixed-point logic capture the complexity class PSPACE.

Item Type:Article
Keywords:Finite model theory, Descriptive complexity.
Full text:PDF - Accepted Version (154Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/S0304-3975(01)00183-9
Record Created:10 Oct 2008
Last Modified:14 Jun 2011 16:42

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library