Fixpoint logics, relational machines, and computational complexity
From MaRDI portal
Publication:4371697
DOI10.1145/256292.256295zbMath0883.68070OpenAlexW2069462712MaRDI QIDQ4371697
Moshe Y. Vardi, Victor Vianu, Serge Abiteboul
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/
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Finite Variable Logics in Descriptive Complexity Theory, Semantic Restrictions over Second-Order Logic, A query language for NC, On the structural simplicity of machines and languages, Domain-independent queries on databases with external functions, A query language for NC (extended abstract), The Descriptive Complexity of Parity Games, Computing on structures, Computing with infinitary logic, The descriptive complexity of decision problems through logics with relational fixed-point and capturing results, Implicit definability and infinitary logic in finite model theory, A restricted second order logic for finite structures, Computable Queries for Object Oriented Databases, 2003 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquim '03, Comparison of expressive power of some query languages for databases, Infinitary logic for computer science, Reflective relational machines, A restricted second order logic for finite structures, The Relational Polynomial-Time Hierarchy and Second-Order Logic, Computation on structures. Behavioural theory, logic, complexity
