Article contents
Yet another hierarchy theorem
Published online by Cambridge University Press: 12 March 2014
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2000
References
REFERENCES
- 2
- Cited by