Skip to main content

Research Repository

Advanced Search

Using program schemes to capture polynomial-time logically on certain classes of structures

Stewart, I.A.

Using program schemes to capture polynomial-time logically on certain classes of structures Thumbnail


Authors



Abstract

We continue the study of the expressive power of certain classes of program schemes on finite structures, in relation to more mainstream logics studied in finite model theory and to computational complexity. We show that there exists a program scheme, whose constructs are assignments and while-loops with quantifier-free tests and which has access to a stack, that can accept a P-complete problem, the deterministic path system problem, even in the absence of non-determinism so long as problem instances are presented in a functional style. (Our proof leans heavily on Cook's proof that the classes of formal languages accepted by deterministic and non-deterministic logspace auxiliary pushdown machines coincide). However, whilst our result is of independent interest, as it leads to a deterministic model of computation capturing P whose non-deterministic variant also captures P, we then show how our constructed program scheme can be used to build a successor relation in certain classes of structures, namely: the class of strongly-connected locally-ordered digraphs; the class of connected planar embeddings; and the class of triangulations, with the consequence that on these classes of graphs, (a fragment of) path system logic (with no built-in relations) captures exactly the polynomial-time solvable problems.

Citation

Stewart, I. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures. LMS journal of computation and mathematics, 6, 40-67

Journal Article Type Article
Publication Date Mar 1, 2003
Deposit Date Jun 29, 2009
Publicly Available Date Aug 25, 2009
Journal LMS Journal of Computation and Mathematics
Electronic ISSN 1461-1570
Publisher Cambridge University Press
Peer Reviewed Peer Reviewed
Volume 6
Pages 40-67
Keywords Computational complexity. Descriptive complexity. Finite model theory.
Public URL https://durham-repository.worktribe.com/output/1627817
Publisher URL http://www.lms.ac.uk/jcm/6/lms2002-004/

Files






You might also like



Downloadable Citations