I have a language which is made out of and has a grammar only operating on well parenthesized words or words of one symbol. I want to know if the problem of belonging to this language is decidable.

Example. Consider the following grammar: $$a \to a(aa) \\ a \to b \\a (a(a(ab))) \to b$$ I'll denote by $L(x)$ the language generated by the above grammar and rule $S \to x$.

Trivially, $b \in L(a)$, using rule 2.
Also $b \in L(a(aa))$ by the sequence of productions $a(aa) \to a(a(a(aa))) \to a(a(a(ab))) \to b$.
However $b \notin L(aa)$ because after applying rule 1 any number of times and then rule 2, symbol $a$ will be repeated $2n + 1$ times and rule 3 can only remove $4m$ of them.

Note, the grammar is actually dealing with trees. Parentheses denote a subtree and symbols denote leaves. Hopefully the notation is clear enough. The language seems much weaker than RE but stronger than context free.

  • 1
    $\begingroup$ Your question is not clear. Are you asking whether (a) the particular language in your example is decidable, or (b) any grammar which is like your example gives a decidable language? $\endgroup$ – Andrej Bauer Dec 23 '12 at 14:03
  • $\begingroup$ And it looks decidable to me. $\endgroup$ – Andrej Bauer Dec 23 '12 at 14:08
  • $\begingroup$ I'm asking generally about this type of grammars. The example language is a bit trivial. $\endgroup$ – Karolis Juodelė Dec 23 '12 at 14:17
  • $\begingroup$ Oh, in general it is going to be undecidable, I think. Let me think. $\endgroup$ – Andrej Bauer Dec 23 '12 at 14:20
  • $\begingroup$ @AndrejBauer, would you elaborate on that? $\endgroup$ – Karolis Juodelė Dec 23 '12 at 14:24

(I completely removed the previous answer, which was applicable only to this particular example).

Your grammars seem to be known as ground term rewriting systems nowadays.

They are rather old. They might be introduced by W.S. Brainard: Tree generating regular systems. Inform. and Control 14 (1969) 217-231.

Concerning your question. I googled a paper of a good old collegue. Joost Engelfriet: Derivation trees of ground term rewriting systems. If my hunch, that this is the correct model, is correct, I like to cite Theorem 4 of that paper:

For every extended ground tree grammar $G$ a regular tree grammar $G'$ with $L(G') = L(G)$ can effectively be constructed.

It is in the section called "New proofs for old results", so that must be a known result.

| cite | improve this answer | |
  • $\begingroup$ Hope it helps! The author JE is always adding full references, so perhaps there are other probably other points to start (less technical?). And, if the model is the one you are looking for, you know now what to google :) $\endgroup$ – Hendrik Jan Dec 23 '12 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.