Stewart, I. A. (2009) 'Program schemes, queues, the recursive spectrum and zero-one laws.', Fundamenta Informaticae., 91 (2). pp. 411-435.
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.
|Additional Information:||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.|
|Keywords:||Finite model theory, Descriptive complexity, Program schemes.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (346Kb)
|Publisher Web site:||http://dx.doi.org/10.3233/FI-2009-0050|
|Date accepted:||No date available|
|Date deposited:||29 June 2009|
|Date of first online publication:||2009|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|