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

Gault, R.L.; Stewart, I.A.

Abstract

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.

Citation

Gault, R., & Stewart, I. (2006). An infinite hierarchy in a class of polynomial-time program schemes. Theory of Computing Systems, 39(5), 753-783. https://doi.org/10.1007/s00224-005-1230-6

• Journal Article Type: Article
• Publication Date: Apr 1, 2006
• Deposit Date: Jun 29, 2009
• Publicly Available Date: Jul 1, 2009
• Journal: Theory of Computing Systems
• Print ISSN: 1432-4350
• Electronic ISSN: 1433-0490
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 39
• Issue: 5
• Pages: 753-783
• DOI: https://doi.org/10.1007/s00224-005-1230-6
• Keywords: Finite model theory, Descriptive complexity, Least-fixed point logic, Logics for P, Program schemes.
• Public URL: https://durham-repository.worktribe.com/output/1567728
• Publisher URL: http://www.dur.ac.uk/i.a.stewart/Papers/infhier.ps