@inproceedings{10.1007/978-3-662-43951-7_30,
    Abstract = {We carefully reexamine a construction of Karakostas, Lipton, and Viglas (2003) to show that the intersection non-emptiness problem for DFA's (deterministic finite automata) characterizes the complexity class NL. In particular, if restricted to a binary work tape alphabet, then there exist constants c1 and c2 such that for every k intersection non-emptiness for k DFA's is solvable in c1k log(n) space, but is not solvable in c2k log(n) space. We optimize the construction to show that for an arbitrary number of DFA's intersection non-emptiness is not solvable in {\$}o({\backslash}frac{\{}n{\}}{\{}{\backslash}log(n){\backslash}log({\backslash}log(n)){\}}){\$}space. Furthermore, if there exists a function f(k){\thinspace}={\thinspace}o(k) such that for every k intersection non-emptiness for k DFA's is solvable in nf(k) time, then P ≠ NL. If there does not exist a constant c such that for every k intersection non-emptiness for k DFA's is solvable in nctime, then P does not contain any space complexity class larger than NL.},
    Address = {Berlin, Heidelberg},
    Author = {Wehar, Michael},
    BookTitle = {Automata, Languages, and Programming},
    Editor = {Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias},
    File = {mwehar\_INE\_5\_9\_14 (0) - a - a - b.pdf},
    ISBN = {978-3-662-43951-7},
    Pages = {354--362},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Hardness Results for Intersection Non-Emptiness},
    Year = {2014},
    date-added = {2018-10-05 07:36:02 +0000},
    date-modified = {2018-10-05 07:36:02 +0000},
    file-2 = {mwehar\_icalp2014 (0) - a - a - b.pdf},
    doi = {10.1007/978-3-662-43951-7_30}
}

@inproceedings{10.1007/978-3-662-43951-7_30, Abstract = {We carefully reexamine a construction of Karakostas, Lipton, and Viglas (2003) to show that the intersection non-emptiness problem for DFA's (deterministic finite automata) characterizes the complexity class NL. In particular, if restricted to a binary work tape alphabet, then there exist constants c1 and c2 such that for every k intersection non-emptiness for k DFA's is solvable in c1k log(n) space, but is not solvable in c2k log(n) space. We optimize the construction to show that for an arbitrary number of DFA's intersection non-emptiness is not solvable in {\$}o({\backslash}frac{{}n{}}{{}{\backslash}log(n){\backslash}log({\backslash}log(n)){}}){\$}space. Furthermore, if there exists a function f(k){\thinspace}={\thinspace}o(k) such that for every k intersection non-emptiness for k DFA's is solvable in nf(k) time, then P ≠ NL. If there does not exist a constant c such that for every k intersection non-emptiness for k DFA's is solvable in nctime, then P does not contain any space complexity class larger than NL.}, Address = {Berlin, Heidelberg}, Author = {Wehar, Michael}, BookTitle = {Automata, Languages, and Programming}, Editor = {Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias}, File = {mwehar_INE_5_9_14 (0) - a - a - b.pdf}, ISBN = {978-3-662-43951-7}, Pages = {354--362}, Publisher = {Springer Berlin Heidelberg}, Title = {Hardness Results for Intersection Non-Emptiness}, Year = {2014}, date-added = {2018-10-05 07:36:02 +0000}, date-modified = {2018-10-05 07:36:02 +0000}, file-2 = {mwehar_icalp2014 (0) - a - a - b.pdf}, doi = {10.1007/978-3-662-43951-7_30} }