Alternation and the computational complexity of logic programs

DOI10.1016/0743-1066(84)90021-9MaRDI QIDQ3702512zbMATH OpenOpenAlexFDO

Authors Ehud Shapiro

Publication date 1984

Published in The Journal of Logic Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0743-1066(84)90021-9

zbMATH Keywords

alternating Turing machinecomplexity measuresdepthgoal-sizelengthlogic programtree proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Publication:3030254
• Transformations of logic programs
• scientific article; zbMATH DE number 4199606
• Logic programming and logarithmic space
• The alternating fixpoint of logic programs with negation

Cited in

(18)

• Communication in concurrent dynamic logic
• Parallel complexity of logical query programs
• First-order linear logic without modalities is NEXPTIME-hard
• Computational complexity and constraint logic programming languages
• Mind change complexity of learning logic programs
• On the structural simplicity of machines and languages
• scientific article; zbMATH DE number 1696794 (Why is no real title available?)
• Logic programming and logarithmic space
• scientific article; zbMATH DE number 4018389 (Why is no real title available?)
• European Summer Meeting of the Association for Symbolic Logic, Hull, 1986
• scientific article; zbMATH DE number 4130360 (Why is no real title available?)
• scientific article; zbMATH DE number 3868618 (Why is no real title available?)
• Unification as a complexity measure for logic programming
• The complexity of revising logic programs
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• On the Floyd–Warshall algorithm for logic programs
• Towards a mathematical theory of machine discovery from facts
• Inductive inference of monotonic formal systems from positive data

This page was built for publication: Alternation and the computational complexity of logic programs

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