Back to search

McMaster University

Unambiguous Functions in Logarithmic Space

Abstract

dc:description.abstract

<p> The notion of nondeterminism is one of the most fundamental concepts in many areas of computer science. Unambiguity, requiring that there be at most one correct sequence of nondeterministic choices, has proved to be one of the most meaningful restrictions of nondeterminism. In the context of space-bounded Turing Machines, several variants of unambiguity have been proposed and studied, and some interesting results have been established, narrowing slightly the gap between deterministic and nondeterministic logarithmic-space computation.</p> <p> We study the different variants of unambiguity in the context of computing multi-valued functions (as opposed to the usual yes/no decision problems). We propose a modification to the standard computation models of Turing Machines and configuration graphs, which allows for unambiguity-preserving composition. We introduce a unified notation, capturing the different flavors of ambiguity. Furthermore, we define a notion of reductions (based on function composition), which allows non-determinism but controls its level of ambiguity. In the light of this framework we establish some reductions between different variants of path counting problems. We also investigate more carefully the technique of inductive counting, and obtain improvement of some existing results.</p>

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Herman, Grzegorz
Advisor dc:contributor.advisor
  • Soltys, Michael

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Herman, Grzegorz. Unambiguous Functions in Logarithmic Space. 2009. http://hdl.handle.net/11375/17309