Abstract
The polynomial-size hierarchy is the hierarchy of ‘minicomplexity’ classes which correspond to two-way alternating finite automata with polynomially many states and finitely many alternations. It is defined by analogy to the polynomial-time hierarchy of standard complexity theory, and it has recently been shown to be strict above its first level.
It is well-known that, apart from their definition in terms of polynomial-time alternating Turing machines, the classes of the polynomial-time hierarchy can also be characterized in terms of polynomial-time predicates, polynomial-time oracle Turing machines, and formulas of second-order logic. It is natural to ask whether analogous alternative characterizations are possible for the polynomial-size hierarchy, as well.
Here, we answer this question affirmatively for predicates. Starting with the first level of the hierarchy, we experiment with several natural ways of defining what a ‘polynomial-size predicate’ should be, so that existentially quantified predicates of this kind correspond to polynomial-size two-way nondeterministic finite automata. After reaching an appropriate definition, we generalize to every level of the hierarchy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Birget, J.-C.: Two-way automata and length-preserving homomorphisms. Mathematical Systems Theory 29, 191–226 (1996)
Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. AMS-SIAM Symposia in Applied Mathematics, vol. VII, pp. 43–73 (1974)
Geffert, V.: An alternating hierarchy for finite automata. Theoretical Computer Science 445, 1–24 (2012)
Immerman, N.: Descriptive complexity. Springer (1998)
Kapoutsis, C.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 544–555. Springer, Heidelberg (2005)
Kapoutsis, C.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 47–66. Springer, Heidelberg (2009)
Kapoutsis, C.A.: Minicomplexity. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 20–42. Springer, Heidelberg (2012)
Kapoutsis, C., Lefebvre, N.: Analogs of Fagin’s Theorem for small nondeterministic finite automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 202–213. Springer, Heidelberg (2012)
Kapoutsis, C., Mulaffer, L.: A descriptive characterization of the power of small 2NFAs (in preparation, 2014)
Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the Symposium on Switching and Automata Theory, pp. 125–129 (1972)
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275–286 (1978)
Sipser, M.: Introduction to the theory of computation, 3rd edn. Cengage Learning (2012)
Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science 3, 1–22 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Kapoutsis, C.A. (2014). Predicate Characterizations in the Polynomial-Size Hierarchy. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds) Language, Life, Limits. CiE 2014. Lecture Notes in Computer Science, vol 8493. Springer, Cham. https://doi.org/10.1007/978-3-319-08019-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-08019-2_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08018-5
Online ISBN: 978-3-319-08019-2
eBook Packages: Computer ScienceComputer Science (R0)