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

Stewart, I.A.

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.

Citation

Stewart, I. (2002). Program schemes, arrays, Lindström quantifiers and zero-one laws. Theoretical Computer Science, 275(1-2), 283-310. https://doi.org/10.1016/s0304-3975%2801%2900183-9

• Journal Article Type: Article
• Publication Date: 2002-03
• Deposit Date: Oct 10, 2008
• Publicly Available Date: Oct 10, 2008
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 275
• Issue: 1-2
• Pages: 283-310
• DOI: https://doi.org/10.1016/s0304-3975%2801%2900183-9
• Keywords: Finite model theory, Descriptive complexity.
• Public URL: https://durham-repository.worktribe.com/output/1627786