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.
|Keywords:||Finite model theory, Descriptive complexity.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (154Kb)
|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
|Look up in GoogleScholar|