Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-24T21:40:39.816Z Has data issue: false hasContentIssue false
  • English
  • Français

Yet another hierarchy theorem

Published online by Cambridge University Press:  12 March 2014

Max Kubierschky
Max Kubierschky*
Affiliation:
Abteilung für Mathematische Logik, Albert-Ludwigs-Universität, Eckerstr 1, 79104 Freiburg, Germany
Get access Rights & Permissions [Opens in a new window]

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
The Journal of Symbolic Logic , Volume 65 , Issue 2 , June 2000 , pp. 627 - 640
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Bra98]Bradfield, J. C., The modal mu-calculus alternation hierarchy is strict, Theoretical Computer Science, vol. 195 (1998), pp. 133–153.CrossRefGoogle Scholar
[EF95]Ebbinghaus, H.-D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[FG97]Flum, J. and Grohe, M., Personal communication.Google Scholar
[GM96]Grädel, E. and McColm, G. L., Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Annals of Pure and Applied Logic, vol. 77 (1996), pp. 169–199.CrossRefGoogle Scholar
[Gro96]Grohe, M., Arity hierarchies, Annals of Pure and Applied Logic, vol. 82 (1996), pp. 103–163.CrossRefGoogle Scholar
[MT97]Matz, O. and Thomas, W., The monadic quantifier alternation hierarchy over graphs is infinite, Proceedings of the 12th annual symposium on logic in computer science (LICS '97), pp. 236–244.Google Scholar