Testing logic programs for local stratification

DOI10.1016/0304-3975(92)90013-6MaRDI QIDQ1199536zbMATH OpenOpenAlexFDO

Authors Luigi Palopoli

Publication date 16 January 1993

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

Full work available at URL https://doi.org/10.1016/0304-3975(92)90013-6

zbMATH Keywords

algebra of termsanalysis of unification patternslogic programs with negation

Mathematics Subject Classification ID

Logic programming (68N17) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

Locally stratified programs are a significant class of logic programs with negation for which both declarative and fixpoint semantics are well defined. Unfortunately in most cases recognizing local stratification is so hard a task that it has been conjectured that the problem is undecidable. Indeed, a formal proof of this undecidability is presented and rather general sufficient conditions for local stratification are introduced. The sufficient conditions are based on an analysis of unification patterns based on a suitably defined algebra of terms.

Recommendations

• Verifying local stratifiability of logic programs and databases
• Decidability of logic program semantics and applications to testing
• Concolic testing in logic programming
• scientific article; zbMATH DE number 956863
• scientific article; zbMATH DE number 1096540
• Foundations of declarative testing in arbitrary logic programming
• scientific article; zbMATH DE number 1453054
• The expressive power of stratified logic programs
• The expressiveness of locally stratified programs

Cites work

• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 4199656 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• The generalized counting method for recursive logic queries

Cited in

(5)

• Verifying local stratifiability of logic programs and databases
• Temporal stratification tests for linear and branching-time deductive databases
• Using linear constraints for logic program termination analysis
• Stratified negation in temporal logic programming and the cycle-sum test
• Hypothetical answers to continuous queries over data streams

This page was built for publication: Testing logic programs for local stratification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199536)