Carnegie Mellon University
Browse

Inductive definitions over finite structures

Download (653.38 kB)
journal contribution
posted on 1990-06-01, 00:00 authored by Daniel Leivant
Abstract: "We give a simple proof of a theorem of Gurevich and Shelah, that the inductive closure of an inflationary operator is equivalent, over the class of finite structures, to the inductive closure (i.e. minimal fixpoint) of a positive operator. A variant of the same proof establishes a theorem of Immerman, that the class of inductive closures of positive first order operators is closed under complementation."

History

Date

1990-06-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC