The expressive power of stratified logic programs
type: Item
instance of: scholarly article
title: The expressive power of stratified logic programs
zbMATH Open document ID: 0727.68016
DOI: 10.1016/0890-5401(91)90059-B
author: Phokion G. Kolaitis
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
review text: Along the interface between the theory of logic programming and relational database theory a particular class of programs has been discovered which is in some sense maximal with respect to the property of having a well behaved semantics. It is the class of stratified programs, consisting of programs in a Datalog style, which combine recursion and negation, with the proviso that the collection of intensional predicates ocurring in these programs is stratified: the predicates can be ordered into strata in such a way that recursive definitions don't invoke predicates in a higher stratum than the predicate defined by this definition, and that all used predicates from the same stratum occur just positively. Aside from describing the class of stratified programs itself the theory has been looking for an independent description of its expressive power. For some time researchers believed that the expressive power of stratified programs over finite structures coincides with that of fixedpoint logic. Such an assertion was stated and proved by Chandra and Harel in 1985. The author of the present paper spotted a difficulty in the proof, and subsequently the result was found to be false by Dahlhaus in 1987. The present paper presents a proof for the correct characterization: the class of stratified programs are as powerful as the existential fragment of fixedpoint logic. Also the full fragment of fixedpoint logic is of a higher expressive power. The proof uses the game trees introduced by Chandra and Harel in a paper from 1982. The result is extended to some infinite structures as well.
Mathematics Subject Classification ID: 68N17
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 03D70
zbMATH DE Number: 4201591
zbMATH Keywords: stratified logic programs
zbMATH Keywords: database queries
zbMATH Keywords: fixedpoint logic
zbMATH Keywords: game trees
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
cites work: Contributions to the Theory of Logic Programming
cites work: Structure and complexity of relational queries
cites work: Horn clause queries and generalizations
cites work: Q3775538
cites work: Q3758820
cites work: Fixed-point extensions of first-order logic
cites work: Relational queries computable in polynomial time
cites work: Q5750390
cites work: Elementary induction on abstract structures
cites work: Q3348437
cites work: Q3348436
full work available at URL: 0890-5401(91)90059-b
OpenAlex ID: W2063545044
description: scientific article; zbMATH DE number 4201591