Tell me more ×
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.
up vote 2 down vote favorite

Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.g. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost derivations?

Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?

share|improve this question
What do you mean by "regular tree grammar"? – vonbrand Feb 13 at 16:44
1  
@vonbrand, this – Karolis Juodelė Feb 13 at 16:48
A cursory look makes this expressible by a LISP-like language (use () to enclose each tree), so the corresponding context free language is LR(0). My answer would be that the flattened grammar is LR(0) exactly when the tree grammar is unambiguous. But I might be overlooking something... – vonbrand Feb 13 at 17:15
@vonbrand nice idea. what exactly do you mean by enclosing each tree with brackets? Each root node of a right hand side of each production? Each node which is not a leave? – mruether Feb 13 at 19:03

1 Answer

up vote 2 down vote

Start by considering regular string grammars. We can determine whether one such grammar $G$ is ambiguous by constructing the intersection of the grammar with itself, with a direct product construction. The nonterminals are pairs $(A,B)$ of nonterminals from the original string grammar $G$. The new grammar of course also derives the original language $L(G)$, but the new grammar has a nonterminal $(A,B)$ with $A\neq B$ in a succesful derivation, iff $G$ is ambiguous. It is decidable whether any given nonterminal occurs in a succesful derivation, so ambiguity is decidable for regular grammars.

The same is true, mutatis mutandis, for regular tree grammars.

share|improve this answer
The grammar $S \to aS \mid aaS \mid a$ is ambiguous, yet I doubt you'll find the pair you are looking for in the product. I think the basic idea can work; you need to find disagreeing pairs of productions, though. – Raphael♦ Feb 14 at 6:43
Thanks @Raphael. Indeed, it is about finding disagreeing pairs of productions, while the letters generated match. However, I was not thinking of grammars, but based my intuition on finite state automata. Because regular tree grammars are somewhat like automata, except the "control" moves to parallel branches. I will rephrase this later. – Hendrik Jan Feb 14 at 11:10
@HendrikJan please keep in mind, that the letters do have an arity, where only nullary letters are used as leaves, all others with a higher arity are inner nodes of a tree. – mruether Feb 14 at 14:35

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.