This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/86941
Description
Title
Count and Tree in Uniform NC(1)
Author(s)
Lee, Jui-Lin
Issue Date
1997
Doctoral Committee Chair(s)
Takeuti, Gaisi
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
