Abstract
We apply a construction of Cook (1971) to show that the intersection non-emptiness problem for one PDA (pushdown automaton) and a finite list of DFA’s (deterministic finite automata) characterizes the complexity class P. In particular, we show that there exist constants \(c_1\) and \(c_2\) such that for every k, intersection non-emptiness for one PDA and k DFA’s is solvable in \(O(n^{c_1 k})\) time, but is not solvable in \(O(n^{c_2 k})\) time. Then, for every k, we reduce intersection non-emptiness for one PDA and \(2^k\) DFA’s to non-emptiness for multi-stack pushdown automata with k-phase switches to obtain a tight time complexity lower bound. Further, we revisit a construction of Veanes (1997) to show that the intersection non-emptiness problem for tree automata also characterizes the complexity class P. We show that there exist constants \(c_1\) and \(c_2\) such that for every k, intersection non-emptiness for k tree automata is solvable in \(O(n^{c_1 k})\) time, but is not solvable in \(O(n^{c_2 k})\) time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Atig, M.F., Bollig, B., Habermehl, P.: Emptiness of multi-pushdown automata is 2ETIME-complete. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 121–133. Springer, Heidelberg (2008)
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114–133 (1981)
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications, October 2007
Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18(1), 4–18 (1971)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York Inc., Secaucus (2006)
Karakostas, G., Lipton, R.J., Viglas, A.: On the complexity of intersecting finite state automata and NL versus NP. TCS 302, 257–274 (2003)
Kozen, D.: Lower bounds for natural proof systems. In: Proc. 18th Symp. on the Foundations of Computer Science, pp. 254–266 (1977)
La Torre, S., Madhusudan, P., Parlato, G.: An infinite automaton characterization of double exponential time. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol. 5213, pp. 33–48. Springer, Heidelberg (2008)
Lange, K.-J., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Havel, Ivan M., Koubek, Václav (eds.) MFCS 1992. LNCS, vol. 629, pp. 346–354. Springer, Heidelberg (1992)
Limaye, N., Mahajan, M.: Membership testing: removing extra stacks from multi-stack pushdown automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 493–504. Springer, Heidelberg (2009)
Lipton, R.J.: On the intersection of finite automata. Gödel’s Lost Letter and P=NP, August 2009
Madhusudan, P., Parlato, G.: The tree width of automata with auxiliary storage. POPL 2011 (2011)
Martens, W., Vansummeren, S.: Automata and logic on trees: Algorithms. ESSLLI 2007 (2007)
La Torre, S., Madhusudan, P., Parlato, G.: A robust class of context-sensitive languages. In: LICS 2007, pp. 161–170 (2007)
Valiant, L.G.: Decision Procedures for Families of Deterministic Pushdown Automata. Ph.D thesis, University of Warwick, August 1973
Veanes, M.: On computational complexity of basic decision problems of finite tree automata. UPMAIL Technical Report 133 (1997)
Wehar, M.: Intersection emptiness for finite automata. Honors thesis, Carnegie Mellon University (2012)
Wehar, M.: Hardness results for intersection non-emptiness. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 354–362. Springer, Heidelberg (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Swernofsky, J., Wehar, M. (2015). On the Complexity of Intersecting Regular, Context-Free, and Tree Languages. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_33
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)