Abstract
We investigate the power of regular leaf languages with respect to three different tree shapes: the first one is the case of arbitrary (and thus potentially non-regular) computation trees; the second one is the case of balanced computation trees (these trees are initial segments of full binary trees); and the third one is the case of fall binary computation trees.
Preview
Unable to display preview. Download preview PDF.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
References
D.A. Barrington, R. Beigel, S. Rudich: Representing boolean functions as polynomials modulo composite numbers. Proceedings of the 24th Annual ACM Symposium on Theory of Computing (1992), pp. 455–461.
B. Borchert: On the acceptance power of regular languages. Proceedings of the 11th Symp. on Theoretical Aspects of Computer Science (1994), LNCS 775, pp. 533–542.
R. Beigel, J. Gill, U. Hertrampf: Counting classes: thresholds, parity, mods, and fewness. Proceedings of the 7th Symp. on Theoretical Aspects of Computer Science (1990), LNCS 415, pp. 49–57.
D. P. Bovet, P. Crescenzi, R. Silvestri: A uniform approach to define complexity classes. Theoretical Computer Science 104 (1992), pp. 263–283.
J. Cai, L. Hemachandra: On the power of parity polynomial time. Proceedings of the 6th Symp. on Theoretical Aspects of Computer Science(1989), LNCS 349, pp. 229–239.
U. Hertrampf: Locally definable acceptance types for polynomial time machines. Proceedings of the 9th Symp. on Theoretical Aspects of Computer Science(1992), LNCS 577, pp. 199–207.
U. Hertrampf: Über Komplexitätsklassen, die mit Hilfe k-wertiger Funktionen definiert werden (On complexity classes, which can be defined using k-valued functions). Habililtationsschrift, Universität Würzburg (1994).
U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K.W. Wagner: On the power of polynomial time bit-reductions. Proceedings of the 8th Structure in Complexity Theory Conference (1993), pp. 200–207.
U. Hertrampf, H. Vollmer, K.W. Wagner: On balanced vs. unbalanced computation trees. Mathematical Systems Theory 29 (1996), pp. 411–421.
B. Jenner, P. McKenzie, D. Thérien: Logspace and logtime leaf languages. Proceedings of the 9th Structure in Complexity Theory Conference (1994), pp. 242–254.
N.K. Vereshchagin: Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestija Rossijskoj Akademii Nauk 57 (1993), pp. 51–90. In Russian.
Author information
Authors and Affiliations
Editor information
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hertrampf, U. (1997). The shapes of trees. In: Jiang, T., Lee, D.T. (eds) Computing and Combinatorics. COCOON 1997. Lecture Notes in Computer Science, vol 1276. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0045108
Download citation
DOI: https://doi.org/10.1007/BFb0045108
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63357-0
Online ISBN: 978-3-540-69522-6
eBook Packages: Springer Book Archive