Questions tagged [tree-grammars]
The tree-grammars tag has no usage guidance.
5
questions with no upvoted or accepted answers
5
votes
0
answers
180
views
Weak equivalent tree grammar for Context-sensitive word grammar?
Consider arbitrary context-sensitive grammar on strings $G_s$.
Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which ...
- 345
3
votes
0
answers
56
views
Tree Languages are Word Languages on an Infinite Alphabet of Contexts
I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand.
In the beginning of Chapter 2, ...
- 1,861
2
votes
0
answers
174
views
Unranked trees grammars?
Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{...
- 345
1
vote
0
answers
20
views
Extending minimal top-down tree automata
I'm trying to find an algorithm to update minimal top-down tree automata/hypergraphs.
Regular tree grammars can be seen as definitions for recursive data structures:
...
- 111
0
votes
0
answers
169
views
How to count number of parse trees for a specific grammar
The task:
You are standing in front of a gigantic forest of syntax trees. One tree looks more fascinating than the other. In front of the forest is a sign:
"Every tree in this forest arises from ...
- 1