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