Files in this item

FilesDescriptionFormat

application/pdf

application/pdf9717298.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Count and Tree in Uniform NC(1)
Author(s):Lee, Jui-Lin
Doctoral Committee Chair(s):Takeuti, Gaisi
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:Based on the function algebras of $AC\sp0$ and $NC\sp1$ (in (9)), we prove the following results: (1) count is in uniform $NC\sp1.$ (2) The equivalence of tree and k-BRN. (3) Multiple addition is in uniform $TC\sp0.$ (4) tree is uniform $NC\sp1$ complete under $AC\sp0$ reduction. We also discuss weak multiple product which is computable in uniform $TC\sp0.$ All proofs here are function algebraic.
Issue Date:1997
Type:Text
Language:English
Description:87 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1997.
URI:http://hdl.handle.net/2142/86941
Other Identifier(s):(MiAaPQ)AAI9717298
Date Available in IDEALS:2015-09-28
Date Deposited:1997


This item appears in the following Collection(s)

Item Statistics