Unambiguous Functions in Logarithmic Space

Article type: Research Article

Authors: Herman, Grzegorz | Soltys, Michael

Affiliations: Department of Computing and Software, McMaster University, 1280 Main Street West, Hamilton, ON, Canada. gherman@tcs.uj.edu.pl, soltys@mcmaster.ca

Note: [] Address for correspondence: Department of Computing and Software, McMaster University

Abstract: We investigate different variants of unambiguity in the context of computing multi-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.

Keywords: Logarithmic Space, Nondeterminism, Reduction, Unambiguity

DOI: 10.3233/FI-2012-621

Journal: Fundamenta Informaticae, vol. 114, no. 2, pp. 129-147, 2012