The Kolmogorov expressive power of Boolean query languages

DOI10.1016/S0304-3975(97)00094-7zbMath0893.68055OpenAlexW2114438303MaRDI QIDQ1389450

Jerzy Tyszkiewicz

Publication date: 30 June 1998

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00094-7

zbMATH Keywords

Kolmogorov complexityfirst order logicleast fixpoint logicpartial fixpoint logicaverage case complexity of query evaluationKolmogorov expressive power

Mathematics Subject Classification ID

Database theory (68P15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (1)

A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computable queries for relational data bases
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Infinitary logics and 0-1 laws
• Infinitary logic and inductive definability over finite structures
• A zero-one law for logic with a fixed-point operator
• Languages that Capture Complexity Classes
• Probabilities on finite models
• On Moschovakis closure ordinals
• Deux ou trois choses que je sais de L_n

This page was built for publication: The Kolmogorov expressive power of Boolean query languages