Computing on structures
DOI10.1007/3-540-56939-1_106zbMATH Open1418.68087OpenAlexW1572529763MaRDI QIDQ4630296FDOQ4630296
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
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
- Fixed-point extensions of first-order logic
- Computable queries for relational data bases
- Elementary induction on abstract structures
- Title not available (Why is that?)
- Datalog extensions for database queries and updates
- Computing with first-order logic
- On non-determinacy in simple computing devices
- Object identity as a query language primitive
- Title not available (Why is that?)
- Alternation
- The polynomial-time hierarchy
- Title not available (Why is that?)
- Universal quantifiers and time complexity of random access machines
- Languages that Capture Complexity Classes
- Title not available (Why is that?)
- Monadic generalized spectra
- Title not available (Why is that?)
- Title not available (Why is that?)
- Turing machines and the spectra of first-order formulas
- Relational queries computable in polynomial time
- What are logical notions?
- On formalised computer programs
- Stable networks and product graphs
- Upper and lower bounds for first order expressibility
- Structure and complexity of relational queries
- The Spectra of First-Order Sentences and Computational Complexity
- Infinitary logic and inductive definability over finite structures
- On Moschovakis closure ordinals
- Fixpoint logics, relational machines, and computational complexity
- Title not available (Why is that?)
- Computing with infinitary logic
- Procedural languages for database queries and updates
- Inductive definitions over finite structures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some relationships between logics of programs and complexity theory
- Descriptive characterizations of computational complexity
- An analysis of fixed-point queries on binary trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (2)
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)
