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 (8)

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

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