Cited By
View all- Mhaskar NSoltys M(2018)String shuffleJournal of Discrete Algorithms10.1016/j.jda.2015.01.00331:C(120-128)Online publication date: 19-Dec-2018
Unambiguous Functions in Logarithmic Space
Pages 129 - 147
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.
References
[1]
Àlvarez, 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).
- Unambiguous Functions in Logarithmic Space
Recommendations
Descriptional complexity of unambiguous input-driven pushdown automata
It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 ( n 2 ) states (B. von ...
Unambiguous Functions in Logarithmic Space
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 ...
Two-way unary automata versus logarithmic space
We show that if L=NL (the classical logarithmic space classes), then each unary 2nfa (a two-way nondeterministic finite automaton) can be converted into an equivalent 2dfa (a deterministic two-way automaton), keeping the number of states polynomial. (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IOS Press
Netherlands
Publication History
Published: 01 April 2012
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
Cited By
View all- Mhaskar NSoltys M(2018)String shuffleJournal of Discrete Algorithms10.1016/j.jda.2015.01.00331:C(120-128)Online publication date: 19-Dec-2018