Publication details for Professor Iain StewartStewart, I.A. (2009). Program schemes, queues, the recursive spectrum and zero-one laws. Fundamenta Informaticae 91(2): 411-435.
- Publication type: Journal Article
- ISSN/ISBN: 0169-2968 (Print), 1875-8681 (Online)
- DOI: 10.3233/FI-2009-0050
- Keywords: Finite model theory. Descriptive complexity. Program schemes.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ$_+(1)$, is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ$(1)$ where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ$(1)$ is the first class and the union of the classes of which is the class NPSQ. We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions; and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindström logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY.
Extended abstract appeared in: Proc. of 7th Ann. Int. Computing and Combinatorics Conference, COCOON 2001 (ed. J. Wang), Lecture Notes in Computer Science Vol. 2108, Springer-Verlag, Berlin (2001) 39-48.