Cancellation laws for polynomial-time p-isolated sets

John N. Crossley; J. B. Remmel

doi:10.1016/0168-0072(92)90071-7

Cancellation laws for polynomial-time p-isolated sets

John N. Crossley
, J. B. Remmel

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (Scopus)

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 (polynomial-time equivalence types) of p-time p-isolated sets with functions induced by fully p-time combinatorial operators (which induce the original p-time computable combinatorial functions of the natural numbers).

Original language	English
Pages (from-to)	147-172
Number of pages	26
Journal	Annals of Pure and Applied Logic
Volume	56
Issue number	1-3
DOIs	https://doi.org/10.1016/0168-0072(92)90071-7
Publication status	Published - 29 Apr 1992

Access to Document

10.1016/0168-0072(92)90071-7

Cite this

@article{c3a9603e55e549f4818592631ff6a054,

title = "Cancellation laws for polynomial-time p-isolated sets",

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 (polynomial-time equivalence types) of p-time p-isolated sets with functions induced by fully p-time combinatorial operators (which induce the original p-time computable combinatorial functions of the natural numbers).",

author = "Crossley, \{John N.\} and Remmel, \{J. B.\}",

year = "1992",

month = apr,

day = "29",

doi = "10.1016/0168-0072(92)90071-7",

language = "English",

volume = "56",

pages = "147--172",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Cancellation laws for polynomial-time p-isolated sets

AU - Crossley, John N.

AU - Remmel, J. B.

PY - 1992/4/29

Y1 - 1992/4/29

N2 - 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 (polynomial-time equivalence types) of p-time p-isolated sets with functions induced by fully p-time combinatorial operators (which induce the original p-time computable combinatorial functions of the natural numbers).

AB - 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 (polynomial-time equivalence types) of p-time p-isolated sets with functions induced by fully p-time combinatorial operators (which induce the original p-time computable combinatorial functions of the natural numbers).

UR - https://www.scopus.com/pages/publications/44049119080

U2 - 10.1016/0168-0072(92)90071-7

DO - 10.1016/0168-0072(92)90071-7

M3 - Article

AN - SCOPUS:44049119080

SN - 0168-0072

VL - 56

SP - 147

EP - 172

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-3

ER -

Cancellation laws for polynomial-time p-isolated sets

Abstract

Access to Document

Other files and links

Cite this