Annals of Pure and Applied Logic 152 (1):31-50 (2008)

Abstract
We consider Choiceless Polynomial Time , a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting from image. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank of sets used, even in image, an extension of image with counting
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2007.11.011
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,558
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Fixed-Point Extensions of First-Order Logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32 (3):265-280.
Choiceless Polynomial Time.Andreas Blass, Yuri Gurevich & Saharon Shelah - 1999 - Annals of Pure and Applied Logic 100 (1-3):141-187.
On Fixed-Point Logic with Counting.Jörg Flum & Martin Grohe - 2000 - Journal of Symbolic Logic 65 (2):777-787.

View all 7 references / Add more references

Citations of this work BETA

Symbioses Between Mathematical Logic and Computer Science.Andreas Blass - 2016 - Annals of Pure and Applied Logic 167 (10):868-878.

Add more citations

Similar books and articles

Choiceless Polynomial Time.Andreas Blass, Yuri Gurevich & Saharon Shelah - 1999 - Annals of Pure and Applied Logic 100 (1-3):141-187.
Addendum to “Choiceless Polynomial Time”.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2001 - Annals of Pure and Applied Logic 112 (1):117.
On MODkP Counting Degrees.Masamitsu Ozaki & Juichi Shinoda - 1999 - Mathematical Logic Quarterly 45 (3):327-342.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On the Complexity of the Pancake Problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.

Analytics

Added to PP index
2013-12-26

Total views
11 ( #769,430 of 2,348,458 )

Recent downloads (6 months)
1 ( #511,012 of 2,348,458 )

How can I increase my downloads?

Downloads

My notes