@inproceedings{10.1007/978-3-662-47666-6_33,
    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.},
    Address = {Berlin, Heidelberg},
    Author = {Swernofsky, Joseph and Wehar, Michael},
    BookTitle = {Automata, Languages, and Programming},
    Editor = {Halld{\'o}rsson, Magn{\'u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina},
    File = {On the Complexity of Intersecting Regular, Context-Free, and Tree Languages - Swernofsky-Wehar2015\_Chapter\_OnTheComplexityOfIntersectingR.pdf},
    ISBN = {978-3-662-47666-6},
    Pages = {414--426},
    Publisher = {Springer Berlin Heidelberg},
    Title = {On the Complexity of Intersecting Regular, Context-Free, and Tree Languages},
    Year = {2015},
    date-added = {2022-06-24 16:23:52 +0200},
    date-modified = {2022-06-24 16:23:52 +0200},
    doi = {10.1007/978-3-662-47666-6_33}
}

@inproceedings{10.1007/978-3-662-47666-6_33, 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.}, Address = {Berlin, Heidelberg}, Author = {Swernofsky, Joseph and Wehar, Michael}, BookTitle = {Automata, Languages, and Programming}, Editor = {Halld{\'o}rsson, Magn{\'u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}, File = {On the Complexity of Intersecting Regular, Context-Free, and Tree Languages - Swernofsky-Wehar2015_Chapter_OnTheComplexityOfIntersectingR.pdf}, ISBN = {978-3-662-47666-6}, Pages = {414--426}, Publisher = {Springer Berlin Heidelberg}, Title = {On the Complexity of Intersecting Regular, Context-Free, and Tree Languages}, Year = {2015}, date-added = {2022-06-24 16:23:52 +0200}, date-modified = {2022-06-24 16:23:52 +0200}, doi = {10.1007/978-3-662-47666-6_33} }