Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

R.L. Gault



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 Mar 28, 2024
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.
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/infhier.ps

Files





You might also like



Downloadable Citations