Fixed-point extensions of first-order logic

1 January 1985

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 346-353
https://doi.org/10.1109/sfcs.1985.27

Abstract

We prove that the three extensions of first-order logic by means of positive inductions, monotone inductions, and so-called non-monotone (in our terminology, inflationary) inductions respectively, all have the same expressive power in the case of finite structures. As a by-product, the collapse of the corresponding fixed-point hierarchies can be deduced.

Keywords

CALCULUS
LOGIC PROGRAMMING
MATHEMATICS
COMPUTER SCIENCE
POWER ENGINEERING COMPUTING
TERMINOLOGY
GOLD
DATABASE LANGUAGES
BOOKS
COMPUTER LANGUAGES

This publication has 3 references indexed in Scilit:

Toward logic tailored for computational complexity
Lecture Notes in Mathematics, 1984
Structure and complexity of relational queries
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1980
Universality of data retrieval languages
Published by Association for Computing Machinery (ACM) ,1979