We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

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.


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:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:No date available
Date deposited:10 October 2008
Date of first online publication:March 2002
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar