Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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? –  Andrej Bauer Dec 23 '12 at 14:03
    
And it looks decidable to me. –  Andrej Bauer Dec 23 '12 at 14:08
    
I'm asking generally about this type of grammars. The example language is a bit trivial. –  Karolis Juodelė Dec 23 '12 at 14:17
    
Oh, in general it is going to be undecidable, I think. Let me think. –  Andrej Bauer Dec 23 '12 at 14:20
    
@AndrejBauer, would you elaborate on that? –  Karolis Juodelė Dec 23 '12 at 14:24
show 2 more comments

1 Answer 1

up vote 1 down vote accepted

(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.

share|improve this answer
    
This seems to be what I was looking for. I'll probably accept this answer after I read that paper. I wonder if there are any hints on construction of $G'$. –  Karolis Juodelė Dec 23 '12 at 15:39
    
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 :) –  Hendrik Jan Dec 23 '12 at 17:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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