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

    Kozen, D., & Yap, C. K. (1985). ALGEBRAIC CELL DECOMPOSITION IN NC. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 515-521). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1985.4