width 1. They can be used to characterize programs expressing NC queries. In
fact Ullman and Van Gelder [1986] show something far more interesting re-
lated to the stage function.
Given such a parallelizable program H (Ullman and Van Gelder [1986])
provides a simple syntactic transformation of H into an equivalent program Η'.
The transformation is such that the naive evaluation of Η' takes, at most,
Chapter 14: Logic Programming and Parallel Complexit ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.