@inproceedings{10.1007/978-3-319-98654-8_23,
    Abstract = {We establish strong connections between the non-emptiness of intersection problem for two and three DFA's over a binary alphabet and the triangle finding and 3sum problems. In particular, we introduce efficient reductions from triangle finding to non-emptiness of intersection for two DFA's over a binary alphabet and from 3sum to non-emptiness of intersection for three DFA's over a binary alphabet. Additionally, in our main result, we show that for every {\$}{\$}{\backslash}alpha {\backslash}ge 2{\$}{\$}, non-emptiness of intersection for three DFA's over a unary alphabet can be solved in {\$}{\$}O(n^{\{}{\backslash}frac{\{}{\backslash}alpha {\}}{\{}2{\}}{\}}){\$}{\$}time if and only if triangle finding can be solved in {\$}{\$}O(n^{\{}{\backslash}alpha {\}}){\$}{\$}time.},
    Address = {Cham},
    Author = {de Oliveira Oliveira, Mateus and Wehar, Michael},
    BookTitle = {Developments in Language Theory},
    Editor = {Hoshi, Mizuho and Seki, Shinnosuke},
    File = {DLT2018RevisedNoClick (0) - a - a - o.pdf},
    ISBN = {978-3-319-98654-8},
    Pages = {282--290},
    Publisher = {Springer International Publishing},
    Title = {Intersection Non-emptiness and Hardness Within Polynomial Time},
    Year = {2018},
    date-added = {2018-10-05 07:42:40 +0000},
    date-modified = {2018-10-05 07:42:40 +0000},
    doi = {10.1007/978-3-319-98654-8_23}
}

@inproceedings{10.1007/978-3-319-98654-8_23, Abstract = {We establish strong connections between the non-emptiness of intersection problem for two and three DFA's over a binary alphabet and the triangle finding and 3sum problems. In particular, we introduce efficient reductions from triangle finding to non-emptiness of intersection for two DFA's over a binary alphabet and from 3sum to non-emptiness of intersection for three DFA's over a binary alphabet. Additionally, in our main result, we show that for every {\$}{\$}{\backslash}alpha {\backslash}ge 2{\$}{\$}, non-emptiness of intersection for three DFA's over a unary alphabet can be solved in {\$}{\$}O(n^{{}{\backslash}frac{{}{\backslash}alpha {}}{{}2{}}{}}){\$}{\$}time if and only if triangle finding can be solved in {\$}{\$}O(n^{{}{\backslash}alpha {}}){\$}{\$}time.}, Address = {Cham}, Author = {de Oliveira Oliveira, Mateus and Wehar, Michael}, BookTitle = {Developments in Language Theory}, Editor = {Hoshi, Mizuho and Seki, Shinnosuke}, File = {DLT2018RevisedNoClick (0) - a - a - o.pdf}, ISBN = {978-3-319-98654-8}, Pages = {282--290}, Publisher = {Springer International Publishing}, Title = {Intersection Non-emptiness and Hardness Within Polynomial Time}, Year = {2018}, date-added = {2018-10-05 07:42:40 +0000}, date-modified = {2018-10-05 07:42:40 +0000}, doi = {10.1007/978-3-319-98654-8_23} }