The expressiveness of a family of finite set languages

DOI10.1016/0304-3975(94)00287-8zbMath0874.68093OpenAlexW2006429500MaRDI QIDQ672126

Neil Immerman, David Stemple, Sushant Patnaik

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00287-8

zbMATH Keywords

database query languagesMachiavelli languageset-based database language

Mathematics Subject Classification ID

Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Query languages for bags and aggregate functions ⋮ A query language for NC ⋮ \(\Delta\)-languages for sets and LOGSPACE computable graph transformers ⋮ A query language for NC (extended abstract) ⋮ An analysis of the Core-ML language: Expressive power and type reconstruction ⋮ Structural recursion as a query language on lists and ordered trees ⋮ Verifiable properties of database transactions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computable queries for relational data bases
• Upper and lower bounds for first order expressibility
• The expressive power of the bounded-iteration construct
• Algorithms for parallel memory. II: Hierarchical multilevel memories
• The complexity of iterated multiplication
• Structure and complexity of relational queries
• On uniformity within \(NC^ 1\)
• Object identity as a query language primitive
• Constant Depth Reducibility
• A taxonomy of problems with fast parallel algorithms
• Languages that Capture Complexity Classes
• Problems complete for deterministic logarithmic space
• Nondeterministic Space is Closed under Complementation

This page was built for publication: The expressiveness of a family of finite set languages