Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Program schemes, queues, the recursive spectrum and zero-one laws.

Stewart, I. A. (2009) 'Program schemes, queues, the recursive spectrum and zero-one laws.', Fundamenta Informaticae., 91 (2). pp. 411-435.

Abstract

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.

Item Type:Article
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:PDF - Accepted Version (346Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.3233/FI-2009-0050
Record Created:29 Jun 2009 16:05
Last Modified:10 Nov 2011 11:16

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library