Abstract
We consider an alternative semantics for partial fixed-point logic (PFP). To define the fixed point of a formula in this semantics, the sequence of stages induced by the formula is considered. As soon as this sequence becomes cyclic, the set of elements contained in every stage of the cycle is taken as the fixed point. It is shown that on finite structures, this fixed-point semantics and the standard semantics for PFP as considered in finite model theory are equivalent, although arguably the formalisation of properties might even become simpler and more intuitive. Contrary to the standard PFP semantics which is only defined on finite structures the new semantics generalises easily to infinite structures and transfinite inductions. In this generality we compare - in terms of expressive power - partial with other known fixed-point logics. The main result of the paper is that on arbitrary structures, PFP is strictly more expressive than inflationary fixed-point logic (IFP). A separation of these logics on finite structures would prove Ptime different from Pspace.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43:62–124, 1991.
S. Abiteboul and V. Vianu. Generic computation and its complexity. In Proc. of the 23rd ACM Symp. on the Theory of Computing, 1991.
S. Abiteboul, M. Vardi, and V. Vianu. Fixpoint logics, relational machines, and computational complexity. Journal of the ACM, 44(1):30–56, 1997. An extended abstract appeared in the Proc. 7th IEEE Symp. on Structure in Complexity Theory, 1992.
A. Dawar. Feasible Computation Through Model Theory. PhD thesis, University of Pennsylvania, 1993.
A. Dawar and Y. Gurevich. Fixed-point logics. Bulletin of Symbolic Logic, 8(1):65–88, 2002.
A. Dawar and S. Kreutzer. Partial and Alternating Fixed Points in Modal Logic. Unpublished.
H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265–280, 1986.
N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86–104, 1986. Extended abstract in Proc. 14th ACML Symp. on Theory of Computing, pages 147–152, 1982.
S. Kreutzer. Expressive equivalence of least and inflationary fixed-point logic. Proc. of the 17th Symp. on Logic in Computer Science (LICS), 2002.
Y.N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974. ISBN 0 7204 2280 9.
M. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on the Theory of Computing, pages 137–146, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kreutzer, S. (2002). Partial Fixed-Point Logic on Infinite Structures. In: Bradfield, J. (eds) Computer Science Logic. CSL 2002. Lecture Notes in Computer Science, vol 2471. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45793-3_23
Download citation
DOI: https://doi.org/10.1007/3-540-45793-3_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44240-0
Online ISBN: 978-3-540-45793-0
eBook Packages: Springer Book Archive