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: | (AM) Accepted Manuscript Download PDF (154Kb) |
Status: | Peer-reviewed |
Publisher Web site: | http://dx.doi.org/10.1016/S0304-3975(01)00183-9 |
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
Export: | |
Look up in GoogleScholar |