Cancellation laws for polynomial-time p-isolated sets

John N. Crossley, J. B. Remmel

    Research output: Contribution to journalArticleResearchpeer-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 languageEnglish
    Pages (from-to)147-172
    Number of pages26
    JournalAnnals of Pure and Applied Logic
    Volume56
    Issue number1-3
    DOIs
    Publication statusPublished - 29 Apr 1992

    Cite this