Publication details for Professor Iain StewartStewart, I.A. (2002). Program schemes, arrays, Lindstroem quantifiers and zero-one laws. Theoretical Computer Science 275(1-2): 283-310.
- Publication type: Journal Article
- ISSN/ISBN: 0304-3975
- DOI: 10.1016/S0304-3975(01)00183-9
- Keywords: Finite model theory, Descriptive complexity, Lindström quantifiers.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.