ALGEBRAIC CELL DECOMPOSITION IN NC.

Dexter Kozen, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An algorithm is given for constructing a cell decomposition of R**D, including adjacency information, defined by any given set of rational polynomials in d variables. The algorithm runs in single exponential parallel time, and in NC for fixed d. The algorithm extends a recent algorithm for deciding the theory of real closed fields.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages515-521
Number of pages7
ISBN (Print)0818606444, 9780818606441
DOIs
StatePublished - 1985

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'ALGEBRAIC CELL DECOMPOSITION IN NC.'. Together they form a unique fingerprint.

Cite this