Yet Another Hierarchy Theorem

Kubierschky, Max

J. Symbolic Logic, Tome 65 (2000) no. 1, p. 627-640 / Harvested from Project Euclid

Résumé

n + 1 nested k-ary fixed point operators are more expressive than n. This holds on finite structures for all sublogics of partial fixed point logic PFP that can express conjunction, existential quantification and deterministic transitive closure of binary relations using at most k-ary fixed point operators and that are closed against subformulas. Among those are a lot of popular fixed point logics.

Publié le : 2000-06-14
Classification:

@article{1183746066,
     author = {Kubierschky, Max},
     title = {Yet Another Hierarchy Theorem},
     journal = {J. Symbolic Logic},
     volume = {65},
     number = {1},
     year = {2000},
     pages = { 627-640},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746066}
}

Kubierschky, Max. Yet Another Hierarchy Theorem. J. Symbolic Logic, Tome 65 (2000) no. 1, pp.  627-640. http://gdmltest.u-ga.fr/item/1183746066/