A query language for NC (extended abstract)

DOI10.1007/3-540-60178-3_100MaRDI QIDQ6064297

Dan Suciu, Val Breazu-Tannen

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

query languagetransitive closurerelational algebraexpressive powercomplex object

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressiveness of a family of finite set languages
• The relational model with relation-valued attributes
• Computable queries for relational data bases
• Datalog extensions for database queries and updates
• An optimal lower bound on the number of variables for graph identification
• Elementary induction on abstract structures
• A query language for NC
• Infinitary logic and inductive definability over finite structures
• Tractable query languages for complex object databases
• An algebra and a logic for \(NC^ 1\)
• On uniformity within \(NC^ 1\)
• A taxonomy of problems with fast parallel algorithms
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Expressibility and Parallel Complexity
• Fixpoint logics, relational machines, and computational complexity

This page was built for publication: A query language for NC (extended abstract)