Computational Inductive Definability

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2014
Accession Number
AD1000910

Entities

People

  • Dexter Kozen

Organizations

  • Cornell University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Automata
  • Computations
  • Computer Programming
  • Computer Science
  • Construction
  • Dictionaries
  • Electronic Mail
  • Fish
  • Language
  • Lists (Data Structures)
  • Programming Languages
  • Semantics
  • Set Theory
  • Theorems
  • Trees (Data Structures)
  • Two Dimensional

Readers

  • Image Processing and Computer Vision.
  • Mathematical Modeling and Probability Theory.
  • Quantum Chemistry