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