The parallel complexity of simple chain queries

Publisher Website
Google Scholar
Abstract
This article discusses parallel complexity issues in chain queries systems and the degree to which such queries are amenable to parallel evaluation. Chain queries are a syntactically simple yet nontrivial class, containing several interesting examples with contrasting parallel complexity. The article reviews the results by Ullman and Van Gelder and proves the Polynomial Stack Theorem for chain rules. Also the article gives a prove of a sequence of P-completeness results which finally carve out all simple chain rules not shown to be in NC by the polynomial stack theorem

This publication has 0 references indexed in Scilit: