The Kolmogorov expressive power of Boolean query languages
type: Item
instance of: scholarly article
title: The Kolmogorov expressive power of Boolean query languages
zbMATH Open document ID: 0893.68055
DOI: 10.1016/S0304-3975(97)00094-7
author: Jerzy Tyszkiewicz
published in: Theoretical Computer Science
publication date: 1998-06-30T00:00:00Z
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1170170
zbMATH Keywords: Kolmogorov expressive power
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: first order logic
zbMATH Keywords: least fixpoint logic
zbMATH Keywords: partial fixpoint logic
zbMATH Keywords: average case complexity of query evaluation
MaRDI profile type: Publication
cites work: Q4864249
cites work: Datalog extensions for database queries and updates
cites work: On Moschovakis closure ordinals
cites work: A zero-one law for logic with a fixed-point operator
cites work: Computable queries for relational data bases
cites work: Infinitary logic and inductive definability over finite structures
cites work: Probabilities on finite models
cites work: Upper and lower bounds for first order expressibility
cites work: Languages that Capture Complexity Classes
cites work: Q3204447
cites work: Infinitary logics and 0-1 laws
cites work: Q4385509
cites work: Q4023358
cites work: Deux ou trois choses que je sais de Ln
full work available at URL: s0304-3975(97)00094-7
OpenAlex ID: W2114438303
description: scientific article; zbMATH DE number 1170170