User sam jones - MathOverflow

Answer by Sam Jones for Which Turing machines accept the language of trivial words in a finitely presented group?

2011-07-28T11:52:56Z

Further to Derek Holt's answer, the negative answer would appear to still apply to the conditions stated in his answer. In fact, you can't even decide if a PDA (let alone a TM) accepts the word problem of a group, as stated in the introduction to:

Stephen R. Laken and Richard M. Thomas, Space Complexity and Word Problems of Groups, Groups-Complexity-Cryptology Volume 1 (2009), No. 2, 261-273

The proof is simple and relies on the well known fact that one can't decide whether the language a PDA accepts over an alphabet $\Sigma$ is equal to $\Sigma^{*}$

Answer by Sam Jones for Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

2011-06-13T18:28:21Z

Undecidable, see here: http://cstheory.stackexchange.com/questions/6947/given-a-pda-m-such-that-lm-is-in-dcfl-construct-a-dpda-n-such-that-ln-lm

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

2011-06-06T16:38:26Z

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free language and outputs a deterministic pushdown automaton $N$ which accepts precisely the language accepted by $M$?

An equivalent problem would be to construct an algorithm which takes as input a pushdown automata $M$ (such that $L(M)$ is deterministic, as in the above) and a deterministic pushdown automata $N$. The output would be yes if $L(M) = L(N)$ and no if $L(M)\neq L(N)$

I believe that an algorithm solving the first would give an algorithm solving the second by the decidability of equivalence of deterministic pushdown automata. I think a solution to the second would imply a solution to the first as we enumerate all deterministic pushdown automata and run the algorithm on them one by one, once we get a yes instance we output that automaton.

I wonder if anyone knows anything about this? Maybe it's a known problem and/or has a known solution? As an aside, I believe it is decidable if you introduce the restriction which says that the language generated by the PDA is the word problem of a group.

Comment by Sam Jones

2011-06-13T18:27:27Z

You're right. I asked the question there and got an answer, it is undecidable: cstheory.stackexchange.com/questions/6947/…