Publication details for Professor Iain StewartGault, R.L. & Stewart, I.A. (2006). An infinite hierarchy in a class of polynomial-time program schemes. Theory of Computing Systems 39(5): 753-783.
- Publication type: Journal Article
- ISSN/ISBN: 1432-4350, 1433-0490
- DOI: 10.1007/s00224-005-1230-6
- Keywords: finite model theory, descriptive complexity, least-fixed point logic, logics for P, program schemes
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.