We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

An infinite hierarchy in a class of polynomial-time program schemes.

Gault, R. L. and Stewart, I. A. (2006) 'An infinite hierarchy in a class of polynomial-time program schemes.', Theory of computing systems., 39 (5). pp. 753-783.


We define a class of program schemes RFDPS constructed around notions of forall-loops, repeat-loops, arrays and if-then-else instructions, and which take finite structures as inputs, and we examine the class of problems, denoted RFDPS also, accepted by such program schemes. The class of program schemes RFDPS is a logic, in Gurevich's sense, in that: every program scheme accepts an isomorphism-closed class of finite structures; we can recursively check whether a given finite structure is accepted by a given program scheme; and we can recursively enumerate the program schemes of RFDPS. We show that the class of problems RFDPS properly contains the class of problems definable in inductive fixed-point logic (for example, the well-known problem Parity is in RFDPS) and that there is a strict, infinite hierarchy of classes of problems within RFDPS (the union of which is RFDPS) parameterized by the depth of nesting of forall-loops in our program schemes. This is the first strict, infinite hierarchy in any polynomial-time logic properly extending inductive fixed-point logic (with the property that the union of the classes in the hierarchy consists of all problems definable in the logic). The fact that there are problems (like Parity) in RFDPS which cannot be defined in many of the more traditional logics of finite model theory (which often have zero-one laws) essentially means that existing tools, techniques and logical hierarchy results are of limited use to us.

Item Type:Article
Keywords:Finite model theory, Descriptive complexity, Least-fixed point logic, Logics for P, Program schemes.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:No date available
Date deposited:01 July 2009
Date of first online publication:April 2006
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar