Fixpoint logics, relational machines, and computational complexity

DOI10.1145/256292.256295zbMATH Open0883.68070OpenAlexW2069462712MaRDI QIDQ4371697FDOQ4371697

Authors: Serge Abiteboul, Moshe Y. Vardi, Victor Vianu 

Publication date: 22 January 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/

Recommendations

• Computing with first-order logic
• The expressive power of fixed-point logic with counting
• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• Computational model theory: an overview

zbMATH Keywords

complexityfixpoint logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (24)

• The Descriptive Complexity of Parity Games
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• A restricted second order logic for finite structures
• Computation on structures. Behavioural theory, logic, complexity
• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• Computable queries for object oriented databases
• Infinitary logic for computer science
• Computer Science Logic
• Reflective relational machines
• 2003 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquim '03
• Comparison of expressive power of some query languages for databases
• A restricted second order logic for finite structures
• Computing with first-order logic
• Choiceless polynomial time
• On the structural simplicity of machines and languages
• Relational Complexity and Higher Order Logics
• Domain-independent queries on databases with external functions
• Computing on structures
• Semantic restrictions over second-order logic
• A query language for NC (extended abstract)
• Finite Variable Logics in Descriptive Complexity Theory
• A query language for NC
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• Computing with infinitary logic

This page was built for publication: Fixpoint logics, relational machines, and computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371697)