Accession Number:

AD1000910

Title:

Computational Inductive Definability

Descriptive Note:

Journal Article - Open Access

Corporate Author:

Cornell University Ithaca United States

Personal Author(s):

Report Date:

2014-01-01

Pagination or Media Count:

10.0

Abstract:

It is shown that over any countable first-order structure, IND programs with dictionaries accept exactly the pi 11 relations. This extends a result of Harel and Kozen Inform. and Control 63 12 1984 118 relating IND and pi 11 over countable structures with some coding power, and provides a computational analog of a result of Barwise et al. J. Symbolic Logic 36 1971 108 relating the pi 11 relations on a countable structure to a certain family of inductively denable relations on the hereditarily finite sets over that structure.

Descriptors:

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE