Alternation and the computational complexity of logic programs

DOI10.1016/0743-1066(84)90021-9zbMath0579.68030OpenAlexW2058419440MaRDI QIDQ3702512

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

depthlengthcomplexity measureslogic programalternating Turing machinegoal-sizetree proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

First-order linear logic without modalities is NEXPTIME-hard, Communication in concurrent dynamic logic, Computational complexity and constraint logic programming languages, Parallel complexity of logical query programs, On the structural simplicity of machines and languages, Towards a mathematical theory of machine discovery from facts, European Summer Meeting of the Association for Symbolic Logic, Hull, 1986, Inductive inference of monotonic formal systems from positive data