Abstract
We consider various types of unambiguity and fewness for log space bounded Turing machines and polynomial time bounded log space auxiliary pushdown automata. In particular, we introduce the notions of (general), reach, and strong unambiguity and fewness. We demonstrate that closure under complement of unambiguous classes implies equivalence of unambiguity and “unambiguous fewness”. This, as we will show, applies in the cases of reach and strong unambiguity for log space. Among the many relations we exhibit, we show that the unambiguous linear contextfree languages, which are not known to be contained in deterministic log space, nevertheless are contained in strongly unambiguous log space, and, consequently, are log space reducible to deterministic contextfree languages.
This research was supported by DFG-SFB 342, Teilprojekt A4 “KLARA”.
Part of the research was done while this author was a guest of SFB-342, A4, at the Technische Universität München, Institut für Informatik.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Àlvarez and B. Jenner. A very hard log space counting class. In Proc. of 5th Conference on Structure in Complexity Theory, pages 154–168, 1990. (To appear in a Special Issue of Theoretical Computer Science).
E. W. Allender. The complexity of sparse sets in P. In Proc. of 1st Structure in Complexity Conf., number 223 in LNCS, pages 1–11. Springer, 1986.
J. Balcácar, J. Diáz, and J. Gabárro. Structural Complexity Theory I+II. Springer, 1988/1990.
G. Buntrock, C. Damm, U. Hertrampf, and C. Meinel. Structure and importance of logspace-MOD-classes. In Proc. of 7th STACS, To appear in LNCS. 1991.
G. Buntrock, L. A. Hemachandra, and D. Siefkes. Using inductive counting to simulate nondeterministic computation. In Proc. of 15th MFCS, number 452 in LNCS, pages 187–194. Springer, 1990. (to appear in Information and Computation).
J. Cai and L. A. Hemachandra. On the power of parity polynomial time. In Proc. of 6th STACS, number 349 in LNCS, pages 229–239. Springer, 1989.
S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18:4–18, 1971.
P. Dymond and W. L. Ruzzo. Parallel RAMs with owned global memory and deterministic language recognition. In Proc. of 13th ICALP, number 226 in LNCS, pages 95–104. Springer, 1986.
J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM Journal of Computing, 17:309–335, 1988.
N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17(5):935–938, 1988.
B. Jenner and B. Kirsig. Alternierung und Logarithmischer Platz. Dissertation, Universität Hamburg, 1989.
B. Jenner, B. Kirsig, and K.-J. Lange. The logarithmic alternation hierarchy collapses. Inform. and Comp., 80:269–288, 1989.
R. Ladner and N. Lynch. Relativization of questions about log space computability. Math. Systems Theory, 10:19–32, 1976.
K.-J. Lange and P. Rossmanith. Characterizing unambiguous augmented pushdown automata by circuits. In Proc. of 15th MFCS, number 452 in LNCS, pages 399–406. Springer, 1990.
I. Niepel. Personal communication, 1991.
R. Niedermeier and P. Rossmanith. Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits. SFB-Bericht 342/31/90 A, I9054, Institut für Informatik, Technische Universität München, 1990.
P. Rossmanith. The owner concept for PRAMs. In Proc. of 8th STACS, number 480 in LNCS, pages 172–183. Springer, 1991.
W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28:216–230, 1984.
I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25:405–414, 1978.
R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279–284, 1988.
L. Valiant. The relative complexity of checking and evaluating. Inform. Proc. Letters, 5:20–23, 1976.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buntrock, G., Jenner, B., Lange, KJ., Rossmanith, P. (1991). Unambiguity and fewness for logarithmic space. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1991. Lecture Notes in Computer Science, vol 529. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54458-5_61
Download citation
DOI: https://doi.org/10.1007/3-540-54458-5_61
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54458-6
Online ISBN: 978-3-540-38391-8
eBook Packages: Springer Book Archive