Fixpoint logics, relational machines, and computational complexity

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/

zbMATH Keywords

complexity; fixpoint logic

Mathematics Subject Classification ID

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, A restricted second order logic for finite structures, A query language for NC (extended abstract), 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, Computation on structures. Behavioural theory, logic, complexity, 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