Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is σp-2--complete
Abstract This paper deals with the complexity of context-free grammars with 1-letter terminal alphabet. We study the complexity of the membership problem and the inequivalence problem. We show that the first problem is NP-complete and the second one is Σ P 2 -complete with respect to log-space reduction. The second result also implies that the inequivalence problem is in P space , solving an open problem stated by Hunt, Rosenkrantz and Szymanski (1976).
We describe some connections, via composition, between two functional spaces: the space of (sub)critical branching mechanisms and the space of Bernstein functions. The functions ${\bf e}_\alpha: x\to x^{\alpha}$ where $x\geq0$ and $0<\alpha\leq 1/2$, and in particular the critical parameter $\alpha=1/2$, play a distinguished role.