Unambiguous Functions in Logarithmic Space

• Autorzy: Herman G. , Soltys M.
• Języki publikacji: EN

Abstrakty

EN

We investigate different variants of unambiguity in the context of computingmulti-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.

Słowa kluczowe

EN

Logarithmic Space; nondeterminism; reduction; unambiguity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 2
• Strony: 129--147
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Herman G.

autor

Soltys M.

• Department of Computing and Software McMaster University 1280 Main Street West, Hamilton, ON, Canada,

Bibliografia

• [1] Alvarez, C., Jenner, B.: A Very Hard Log Space Counting Class, In: 5th Annual Conference on Structure in Complexity Theory, pp. 154-168 (1990).
• [2] Buntrock, G., Jenner, B., Lange, K., Rossmanith, P.: Unambiguity and Fewness for Logarithmic Space, In: 8th International Conference on Fundamentals of Computation Theory, Volume 529 of Lecture Notes in Computer Science, pp. 168-179 (1991).
• [3] Buntrock, G., Hemachandra, L., Siefkes, D.: Using Inductive Counting to Simulate Nondeterministic Computation, Information and Computation 102 (1), pp. 102-117 (1993).
• [4] Allender, E., Lange, K.: StUSPACE(log n) is Contained in DSPACE(log2 n/ log log n), In: Electronic Colloquium on Computational Complexity (ECCC), Volume 3 (1996).
• [5] Herman, G.: Unambiguous functions in logarithmic space. PhD thesis, McMaster University (2009).
• [6] Herman, G., Soltys, M.: Unambiguous functions in logarithmic space. In: Wolfgang Merkle Klaus Ambos-Spies, Benedikt Löwe, editor, Mathematical Theory and Computational Practice. 5th Conference on Computability in Europe, CiE'09, University of Heidelberg, pp. 162-175 (2009).
• [7] Lange, K.: Nondeterministic Logspace Reductions, In: 11th Symposium on Mathematical Foundations of Computer Science, Volume 176 of Lecture Notes in Computer Science, pp. 378-388 (1984).
• [8] Lange, K.: An Unambiguous Class Possessing a Complete Set, In: 14th Annual Symposium on Theoretical Aspects of Computer Science, Volume 1200 of Lecture Notes in Computer Science, pp. 339-350 (1997)
• [9] Reinhardt, K., Allender, E.: Making Nondeterminism Unambiguous, In: 38th Annual Symposium on Foundations of Computer Science, pp. 244-253 (1997).
• [10] Allender, E., Reinhardt, K., Zhou, S.: Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds, Journal of Computer and System Sciences 59 (2), pp. 164-181 (1999)
• [11] Jenner, B., Kirsig, B.: Alternierung und Logarithmischer Platz, Dissertation, Universität Hamburg (1989).
• [12] Immerman, N.: Nondeterministic space is closed under complementation, In: 3rd Annual Conference on Structure in Complexity Theory, pp. 112-115 (1988)
• [13] Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata, Acta Informatica 26 (3), pp. 279-284 (1988).
• [14] Ladner, R., Lynch, N.: Relativization of Questions About Log Space Computability, Theory of Computing Systems 10 (1), pp. 19-32 (1976).
• [15] Litow, B., Sudborough, I.: On non-erasing oracle tapes in space bounded reducibility, SIGACT News 10 (2), pp. 53-57 (1978).
• [16] Lynch, N.: Log Space machines with Multiple Oracle Tapes, Theoretical Computer Science 6, pp. 25-39 (1978).
• [17] Ruzzo, W., Simon, J., Tompa, M.: Space-bounded hierarchies and probabilistic computations, In: 14th Annual ACM Symposium on Theory of Computing, pp. 215-223 (1982).
• [18] Stearns, R.E., Hartmanis, J., Lewis, P.M.: Hierarchies of memory limited computations, In: 6th Annual IEEE Symposium on Switching Circuit Theory and Logical Design (1965).