dc.contributor
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor
Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor
Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
dc.contributor.author
Álvarez Faura, M. del Carme
dc.contributor.author
Balcázar Navarro, José Luis
dc.contributor.author
Jenner Núñez, Birgit
dc.identifier
Alvarez, C.; Balcazar, J.L.; Jenner, B. Functional oracle queries as a measure of parallel time. 1990.
dc.identifier
https://hdl.handle.net/2117/327984
dc.description.abstract
We discuss two notions of functional oracle for logarithmic space-bounded machines, which differ in whether there is only one oracle tape for both the query and the answer or a separate tape for the answer, which can still be read on while the following query is already being constructed.
The first notion turns out to be basically non-adaptive, behaving like access to an oracle set. The second notion, on the other hand, is adaptive. By imposing appropriate bounds on the number of functional oracle queries made in this computation model, we obtain new characterizations of the NC and AC hierarchies; thus the number of oracle queries can be considered as a measure of parallel time. Using this characterization of parallel classes, we solve open questions of Wilson.
dc.description.abstract
Postprint (published version)
dc.format
application/pdf
dc.rights
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.rights
Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.subject
Àrees temàtiques de la UPC::Informàtica
dc.title
Functional oracle queries as a measure of parallel time
dc.type
External research report
