Some results on decision trees with relations to computational trees

Jerzy W. Jaromczyk

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


In this paper we have shown some results for decision trees with tests from the essentially wider class of functions than the polynomials of bounded degree. We introduced the notion of functions r-distant to Rd[x] and have shown how starting from decision trees we can derive lower bounds in the model of computation trees. This relation suggests an uniform approach to lower bound proving in decision and computational tree models.

Original languageEnglish
Title of host publicationComputation Theory - 5th Symposium, Proceedings
EditorsAndrzej Skowron
Number of pages7
StatePublished - 1985
Event5th Symposium on Computation Theory, SCT 1984 - Zaborow, Poland
Duration: Dec 3 1984Dec 8 1984

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume208 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th Symposium on Computation Theory, SCT 1984

Bibliographical note

Publisher Copyright:
© 1985, Springer-Verlag.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Some results on decision trees with relations to computational trees'. Together they form a unique fingerprint.

Cite this