All Questions
Tagged with context-free circuit-complexity
4 questions
8
votes
0
answers
103
views
Does ${\bf CFLPAD}={\bf PPAD}$?
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem?
I asked a similar ...
- 14.2k
15
votes
2
answers
2k
views
Is SAT a context-free language?
I am considering the language of all satisfiable propositional logic formulae, SAT (to ensure that this has a finite alphabet, we would encode propositional letters in some suitable way [edit: the ...
- 514
10
votes
0
answers
274
views
Complexity of a problem over acyclic context-free grammars
Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
- 500
12
votes
2
answers
458
views
Reference for Dyck languages being $\mathsf{TC}_0$-complete
Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon
$$
over the set of symbols $\{(_1,\ldots,(_k,)_1,\...
- 7,668