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:
List -> cons(Bool, List) | nil()
Bool -> true() | false()
By minimal I mean that distinct nodes should generate distinct term languages. Intuitively this deduplicates nodes similar to hash-consing.
The following grammar would minimize to the first example, because X and Y generate the same terms:
X -> cons(Bool, Y) | nil()
Y -> cons(Bool, X) | nil()
Bool -> true() | false()
Incremental updates
Now imagine we have a minimal regular tree grammar and want to extend it. We have some new rules, and want to match each rule to an existing one or extend the grammar.
This is similar to subgraph-isomorphisms, but each node can match at most one node in the existing grammar. My approach so far is to match each strongly connected component separately, and to index scc's by their size and which constructors occur in them. For deterministic tree grammars, graph-isomorphism between scc's is O(n) in the common case and worst case O(n^2) - take the pattern node with the rarest rule-head, and check if it unifies with the possible graph nodes in turn.
So this isn't terrible, but worst case O(n^2) is still a bit scary. I couldn't find anything in the literature, though. Is there any prior work on this?
Background, tree grammar minimization:
I didn't manage to find much on tree grammar minimization in general, so here is my current approach for non-incremental minimization. I give this for context because incremental updates should be equivalent to naive updates+minimization.
Initially, we map each node to a single node A. Then we can
- Canonicalize the rhs. So
X -> cons(A,A) | nil(),Y -> cons(A,A) | nil()etc - Use a hashmap to map each canonicalized rhs to some node id
- Update the mappings with these new ids
Repeat this until a fixpoint is reached, easy enough with a worklist algorithm. But even small updates force us to redo all this work
