patternModerate
Relationship of algorithm complexity and automata class
Viewed 0 times
automataalgorithmandclasscomplexityrelationship
Problem
I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!
Solution
Here are some known results:
-
$\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.
-
$\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.
-
$\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.
-
$\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.
-
The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.
-
Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.
-
$\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.
-
$\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.
-
$\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.
-
$\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.
-
The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.
-
Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.
Context
StackExchange Computer Science Q#52748, answer score: 11
Revisions (0)
No revisions yet.