Computing on structures

DOI10.1007/3-540-56939-1_106MaRDI QIDQ4630296zbMATH OpenOpenAlexFDO

Authors Serge Abiteboul, Victor Vianu

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

expressive powerquery languagecomplexity classrelational machinegeneric machinepredicate symbol

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 4179364 (Why is no real title available?)
• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• scientific article; zbMATH DE number 3941493 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 3711948 (Why is no real title available?)
• scientific article; zbMATH DE number 176206 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• scientific article; zbMATH DE number 1142327 (Why is no real title available?)
• scientific article; zbMATH DE number 219195 (Why is no real title available?)
• scientific article; zbMATH DE number 3349780 (Why is no real title available?)
• Alternation
• An analysis of fixed-point queries on binary trees
• Computable queries for relational data bases
• Computing with first-order logic
• Computing with infinitary logic
• Datalog extensions for database queries and updates
• Descriptive characterizations of computational complexity
• Elementary induction on abstract structures
• Fixed-point extensions of first-order logic
• Fixpoint logics, relational machines, and computational complexity
• Inductive definitions over finite structures
• Infinitary logic and inductive definability over finite structures
• Languages that Capture Complexity Classes
• Monadic generalized spectra
• Object identity as a query language primitive
• On Moschovakis closure ordinals
• On formalised computer programs
• On non-determinacy in simple computing devices
• Procedural languages for database queries and updates
• Relational queries computable in polynomial time
• Some relationships between logics of programs and complexity theory
• Stable networks and product graphs
• Structure and complexity of relational queries
• The Spectra of First-Order Sentences and Computational Complexity
• The polynomial-time hierarchy
• Turing machines and the spectra of first-order formulas
• Universal quantifiers and time complexity of random access machines
• Upper and lower bounds for first order expressibility
• What are logical notions?

Cited in

(2)

• Categorial graphs
• Computing with infinitary logic

This page was built for publication: Computing on structures

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