The AG approach can handle structures with the kind of run-time dependencies that Graph Types structures can have. This works because these dependencies involve the different type of each node in the structure. Once the type of each node can be encoded in the path-name, we can express the appropriate properties.
The Group Fields framework [Mic95] used a presentation description that would have been difficult to work with. It would allow structures with an undecidable word problem: we could not decide that two links led to the same node. It also uses a novel declarative method of describing algorithms, based on webs and streams.
Using groups generally could require us to describe structures too strictly to be of any use, but the AG formalism can enable us to produce more vague descriptions, such as the target of a particular pointer can be any one of a set of nodes.
This idea is feasible within the AG method. As already mentioned, describing structures directly using FSAs can be unwieldy, and this could be an approach that would make it more manageable. These particular properties mentioned above can all be converted automatically to FSA descriptions.