Yeah, that makes sense. And off the top of my head, it seems like they would indeed be regular grammars—each node in the tree would be a state in the finite state machine, and then copies of the tree would produce loops in the state transition graph. Symbols on the edges would be the argument names (or indices) for the inputs to atomic operations. Still a few i’s to dot and t’s to cross, but I think it works.
Yeah, that makes sense. And off the top of my head, it seems like they would indeed be regular grammars—each node in the tree would be a state in the finite state machine, and then copies of the tree would produce loops in the state transition graph. Symbols on the edges would be the argument names (or indices) for the inputs to atomic operations. Still a few i’s to dot and t’s to cross, but I think it works.
Elegant, too. Nice solution!
I’m actually not sure it’s a regular grammar. Consider this program:
Which gives the tree
The path from any 1 to the root contains a bunch of minuses, then at least as many pluses. That’s not regular.
So it’s probably some other kind of grammar, and I don’t know if it has decidable equivalence.