## Files in this item

FilesDescriptionFormat

application/pdf

9717298.pdf (4MB)
(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
﻿