Skip to main content

Research Repository

Advanced Search

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

Stewart, I.A.

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


Authors



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 Mar 29, 2024
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.

Files





You might also like



Downloadable Citations