Some results on decision trees with relations to computational trees

Jerzy W. Jaromczyk

doi:10.1007/3-540-16066-3_11

Some results on decision trees with relations to computational trees

Jerzy W. Jaromczyk

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 R_d[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 language	English
Title of host publication	Computation Theory - 5th Symposium, Proceedings
Editors	Andrzej Skowron
Pages	111-117
Number of pages	7
DOIs	https://doi.org/10.1007/3-540-16066-3_11
State	Published - 1985
Event	5th Symposium on Computation Theory, SCT 1984 - Zaborow, Poland Duration: Dec 3 1984 → Dec 8 1984

Publication series

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

Conference

Conference	5th Symposium on Computation Theory, SCT 1984
Country/Territory	Poland
City	Zaborow
Period	12/3/84 → 12/8/84

Bibliographical note

Publisher Copyright:
© 1985, Springer-Verlag.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-16066-3_11

Cite this

Jaromczyk, J. W. (1985). Some results on decision trees with relations to computational trees. In A. Skowron (Ed.), Computation Theory - 5th Symposium, Proceedings (pp. 111-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 208 LNCS). https://doi.org/10.1007/3-540-16066-3_11

@inproceedings{25e718102a934cb38b6714882cbf5f8e,

title = "Some results on decision trees with relations to computational trees",

abstract = "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.",

author = "Jaromczyk, {Jerzy W.}",

note = "Publisher Copyright: {\textcopyright} 1985, Springer-Verlag.; 5th Symposium on Computation Theory, SCT 1984 ; Conference date: 03-12-1984 Through 08-12-1984",

year = "1985",

doi = "10.1007/3-540-16066-3_11",

language = "English",

isbn = "9783540160663",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "111--117",

editor = "Andrzej Skowron",

booktitle = "Computation Theory - 5th Symposium, Proceedings",

}

Jaromczyk, JW 1985, Some results on decision trees with relations to computational trees. in A Skowron (ed.), Computation Theory - 5th Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 208 LNCS, pp. 111-117, 5th Symposium on Computation Theory, SCT 1984, Zaborow, Poland, 12/3/84. https://doi.org/10.1007/3-540-16066-3_11

Some results on decision trees with relations to computational trees. / Jaromczyk, Jerzy W.
Computation Theory - 5th Symposium, Proceedings. ed. / Andrzej Skowron. 1985. p. 111-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 208 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Some results on decision trees with relations to computational trees

AU - Jaromczyk, Jerzy W.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85034739666&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034739666&partnerID=8YFLogxK

U2 - 10.1007/3-540-16066-3_11

DO - 10.1007/3-540-16066-3_11

M3 - Conference contribution

AN - SCOPUS:85034739666

SN - 9783540160663

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 111

EP - 117

BT - Computation Theory - 5th Symposium, Proceedings

A2 - Skowron, Andrzej

T2 - 5th Symposium on Computation Theory, SCT 1984

Y2 - 3 December 1984 through 8 December 1984

ER -

Some results on decision trees with relations to computational trees

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this