Cancellation laws for polynomial-time p-isolated sets

Annals of Pure and Applied Logic 56 (1-3):147-172 (1992)

Abstract

A universal Horn sentence in the language of polynomial-time computable combinatorial functions of natural numbers is true for the natural numbers if, and only if, it is true for PETs of p-time p-isolated sets with functions induced by fully p-time combinatorial operators

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,879

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2014-01-16

Downloads
5 (#1,212,705)

6 months
1 (#386,001)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Combinatorial Functors.J. N. Crossley & Anil Nerode - 1977 - Journal of Symbolic Logic 42 (4):586-587.
Recursive Equivalence Types and Combinatorial Functions.John Myhill - 1966 - Journal of Symbolic Logic 31 (3):510-511.
Extensions to Isols.Anil Nerode - 1960 - Journal of Symbolic Logic 25 (4):359-361.

Add more references

Citations of this work

No citations found.

Add more citations

Similar books and articles

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.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Polynomial Time Uniform Word Problems.Stanley Burris - 1995 - Mathematical Logic Quarterly 41 (2):173-182.