Division in logspace-uniform NC1 | RAIRO-Theor. Inf. Appl.

Issue		RAIRO-Theor. Inf. Appl. Volume 35, Number 3, May-June 2001


Page(s)		259 - 275
DOI		10.1051/ita:2001119

DOI: 10.1051/ita:2001119

Theoret. Informatics Appl. 35, 259-275 (2001)

Division in logspace-uniform NC¹

Andrew Chiu¹, George Davida¹ and Bruce Litow²

¹ EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.; (davida@cs.uwm.edu)
² School of Information Technology, James Cook University, Townsville, Qld. 4811, Australia; (bruce@cs.jcu.edu.au)

(Received June 25, 2000. Accepted August 3, 2001.)

Abstract
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC¹ circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC¹.

AMS Subject: 68Q05, 68Q10, 68Q15, 68Q17.

Key words: Parallel complexity -- NC -- integer division -- uniformity.

© EDP Sciences 2001

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.