R.L. Gault
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 |
Files
Accepted Journal Article
(230 Kb)
PDF
You might also like
The stellar transformation: from interconnection networks to datacenter networks
(2016)
Journal Article
The influence of datacenter usage on symmetry in datacenter network design
(2017)
Journal Article
Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes
(2016)
Journal Article
On the computational complexity of routing in faulty k-ary n-cubes and hypercubes.
(2012)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search