| Autor: |
de Oliveira Oliveira, Mateus, Wehar, Michael |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Developments in Language Theory |
| Popis: |
We study the fine grained complexity of the DFA non-emptiness of intersection problem parameterized by the number k of input automata (k -DFA-NEI). More specifically, we are given a list \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \mathcal {A}_1,...,\mathcal {A}_k\rangle $$\end{document} of DFA’s over a common alphabet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varSigma $$\end{document}, and the goal is to determine whether \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcap _{i=1}^{k}{\mathcal {L}}(\mathcal {A}_i)\ne \emptyset $$\end{document}. This problem can be solved in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^k)$$\end{document} by applying the classic Rabin-Scott product construction. In this work, we show that the existence of algorithms solving k -DFA-NEI in time slightly faster than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^k)$$\end{document} would imply the existence of deterministic sub-exponential time algorithms for the simulation of nondeterministic linear space bounded computations. This consequence strengthens the existing conditional lower bounds for k-DFA-NEI and implies new non-uniform circuit lower bounds. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
