Computing on structures

DOI10.1007/3-540-56939-1_106zbMath1418.68087OpenAlexW1572529763MaRDI QIDQ4630296

Victor Vianu, Serge Abiteboul

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_106

zbMATH Keywords

query languageexpressive powercomplexity classrelational machinegeneric machinepredicate symbol

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Descriptive complexity and finite models (68Q19)

Related Items

Categorial graphs ⋮ Computing with infinitary logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing with infinitary logic
• Procedural languages for database queries and updates
• Fixed-point extensions of first-order logic
• Some relationships between logics of programs and complexity theory
• Descriptive characterizations of computational complexity
• Computable queries for relational data bases
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• An analysis of fixed-point queries on binary trees
• Elementary induction on abstract structures
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• Computing with first-order logic
• Infinitary logic and inductive definability over finite structures
• On formalised computer programs
• On non-determinacy in simple computing devices
• Inductive definitions over finite structures
• Object identity as a query language primitive
• The Spectra of First-Order Sentences and Computational Complexity
• Universal quantifiers and time complexity of random access machines
• Relational queries computable in polynomial time
• What are logical notions?
• Languages that Capture Complexity Classes
• Alternation
• Monadic generalized spectra
• On Moschovakis closure ordinals
• Fixpoint logics, relational machines, and computational complexity
• Turing machines and the spectra of first-order formulas
• Stable networks and product graphs