×

A reducibility for the dot-depth hierarchy. (English) Zbl 1079.03028

Summary: Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to Brzozowski’s dot-depth hierarchy and some of its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach).

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03D30 Other degrees and reducibilities in computability and recursion theory
03D55 Hierarchies of computability and definability
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.L. Balcázar, J. Díaz, J. Gabarró, Structural complexity I, EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer, Berlin, 1988.; J.L. Balcázar, J. Díaz, J. Gabarró, Structural complexity I, EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer, Berlin, 1988.
[2] J.L. Balcázar, J. Díaz, J. Gabarró, Structural complexity II, EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer, Berlin, 1990.; J.L. Balcázar, J. Díaz, J. Gabarró, Structural complexity II, EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer, Berlin, 1990.
[3] Borchert, B.; Kuske, D.; Stephan, F., On existentially first-order definable languages and their relation to NP, Theoret. Inform. Appl., 33, 259-269 (1999) · Zbl 0949.03035
[4] Bovet, D. P.; Crescenzi, P.; Silvestri, R., A uniform approach to define complexity classes, Theoret. Comput. Sci., 104, 263-283 (1992) · Zbl 0754.68049
[5] Brzozowski, J. A.; Knast, R., The dot-depth hierarchy of star-free languages is infinite, J. Comput. System Sci., 16, 37-55 (1978) · Zbl 0368.68074
[6] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logic Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705
[7] Burtschick, H.-J.; Vollmer, H., Lindström quatifiers and leaf language definability, Internat. J. of Found. Comput. Sci., 9, 277-294 (1998) · Zbl 1319.68104
[8] Cohen, R. S.; Brzozowski, J. A., Dot-depth of star-free events, J. Comput. System Sci., 5, 1-16 (1971) · Zbl 0217.29602
[9] Cronauer, K.; Hertrampf, U.; Vollmer, H.; Wagner, K. W., The chain method to separate counting classes, Theory Comput. Systems, 31, 93-108 (1998) · Zbl 0893.68070
[10] Ebbinghaus, H.-D.; Flum, J., Finite Model Theory (1999), Springer: Springer Berlin
[11] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc., 98, 21-52 (1961) · Zbl 0111.01102
[12] Glaßer, C.; Schmitz, H., The Boolean structure of dot-depth one, J. Automat, Languages Combin., 6, 437-452 (2001) · Zbl 1013.68112
[13] Gundermann, T.; Nasser, N. A.; Wechsung, G., A survey on counting classes, Proc. of Structures in Complexity Theory, 140-153 (1990)
[14] Gundermann, T.; Wechsung, G., Counting classes of finite accepting types, Computers and Artificial Intelligence, 6, 395-409 (1987) · Zbl 0638.68027
[15] U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K.W. Wagner, On the power of polynomial time bit-reductions, in: Proc. of 8th Structure in Complexity Theory (1993) 200-207.; U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K.W. Wagner, On the power of polynomial time bit-reductions, in: Proc. of 8th Structure in Complexity Theory (1993) 200-207.
[16] U. Hertrampf, H. Vollmer, K. W. Wagner, On the power of number-theoretic operations with respect to counting, in: Proc. of 10th Structure in Complexity Theory (1995) 299-314.; U. Hertrampf, H. Vollmer, K. W. Wagner, On the power of number-theoretic operations with respect to counting, in: Proc. of 10th Structure in Complexity Theory (1995) 299-314.
[17] Hertrampf, U.; Vollmer, H.; Wagner, K. W., On balanced vs. unbalanced computation trees, Math. Systems Theory, 29, 411-421 (1996) · Zbl 0853.68097
[18] Immermann, N., Descriptive Complexity (1999), Springer: Springer Berlin
[19] Jenner, B.; McKenzie, P.; Therien, D., Logspace and logtime leaf languages, Inform. and Computa., 129, 21-33 (1996) · Zbl 0864.68057
[20] McNaughton, R.; Papert, S., Counter-free automata (1971), MIT Press: MIT Press Cambridge, MA · Zbl 0232.94024
[21] Pin, J.-E.; Weil, P., Polynomial closure and unambiguous product, Theory Comput. Systems, 30, 383-422 (1997) · Zbl 0872.68119
[22] H. Schmitz, K.W. Wagner, The Boolean hierarchy over level 1/2 of the Sraubing-Therien hierarchy, Technical Report 201, Institute für Informatik, University of Würzburg, http://www.informatik.uni-wuerzburg.de; H. Schmitz, K.W. Wagner, The Boolean hierarchy over level 1/2 of the Sraubing-Therien hierarchy, Technical Report 201, Institute für Informatik, University of Würzburg, http://www.informatik.uni-wuerzburg.de
[23] Selivanov, V. L., Hierarchies of the hyperarithmetical sets and functions, Algebra and Logic, 22, N6, 666-692 (1983), (Russian, there is an English translation) · Zbl 0536.03025
[24] V.L. Selivanov, Two refinements of the polynomial hierarchy, in: Proc. 11th Symp. on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, Vol. 775, Springer, Berlin 1994, pp. 439-448.; V.L. Selivanov, Two refinements of the polynomial hierarchy, in: Proc. 11th Symp. on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, Vol. 775, Springer, Berlin 1994, pp. 439-448. · Zbl 0941.03544
[25] Selivanov, V. L., Fine hierarchies and Boolean terms, J. Symbolic Logic, 60, 289-317 (1995) · Zbl 0824.03022
[26] V.L. Selivanov. A logical approach to decidability of hierarchies of regular star-free languages. in: Proc. 18th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 2010, Springer, Berlin, 2001, pp. 539-550.; V.L. Selivanov. A logical approach to decidability of hierarchies of regular star-free languages. in: Proc. 18th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 2010, Springer, Berlin, 2001, pp. 539-550. · Zbl 0976.03042
[27] Selivanov, V. L., Relating automata-theoretic hierarchies to complexity-theoretic hierarchies, Theoret. Inform. Appl., 36, 29-42 (2002) · Zbl 1029.03027
[28] V.L. Selivanov, A.G. Shukin, On hierarchies of regular star-free languages, Preprint 69, A.P. Ershov Institute of Informatics Systems, 2000, 28p, (in Russian).; V.L. Selivanov, A.G. Shukin, On hierarchies of regular star-free languages, Preprint 69, A.P. Ershov Institute of Informatics Systems, 2000, 28p, (in Russian).
[29] V.L. Selivanov, K.W. Wagner, A reducibility for the dot-depth hierarchy, Lecture Notes in Computer Science, Vol. 3153, 2004, pp. 783-793.; V.L. Selivanov, K.W. Wagner, A reducibility for the dot-depth hierarchy, Lecture Notes in Computer Science, Vol. 3153, 2004, pp. 783-793. · Zbl 1097.03035
[30] Shoenfield, J., Mathematical Logic (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0155.01102
[31] Shukin, A. G., Difference hierarchies of regular languages, Comput. Systems, Novosibirsk, 161, 141-155 (1998), (in Russian) · Zbl 0932.03053
[32] Thomas, W., Classifying regular events in symbolic logic, J. Comput. System Sci., 25, 360-376 (1982) · Zbl 0503.68055
[33] W. Thomas, A concatenation game and the dot-depth hierarchy. Lecture Notes in Computer Science, Vol. 270, 1987, pp. 415-426.; W. Thomas, A concatenation game and the dot-depth hierarchy. Lecture Notes in Computer Science, Vol. 270, 1987, pp. 415-426.
[34] Vereshchagin, N. K., Relativizable and non-relativizable theorems in the polynomial theory of algorithms, Izv. Rossiiskoi Akad Nauk, 57, 51-90 (1993), (in Russian) · Zbl 0822.68035
[35] Wagner, K. W., A note on parallel queries and the symmetric-difference hierarchy, Inform. Process. Lett., 66, 13-20 (1998) · Zbl 1078.68636
[36] G. Wechsung, K.W. Wagner, On the Boolean closure of NP, in: Proc. of the 1985 Int. Conf. on Fundamentals of Computation theory, Lecture Notes in Computer Science, Vol. 199, Springer-Verlag, 1985, p. 485-493.; G. Wechsung, K.W. Wagner, On the Boolean closure of NP, in: Proc. of the 1985 Int. Conf. on Fundamentals of Computation theory, Lecture Notes in Computer Science, Vol. 199, Springer-Verlag, 1985, p. 485-493.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.