So which algorithms for optimizing its NFA (Nondeterministic Finite Automaton) grammars (to fit in the cache hierarchy) would suit a computer that can perform concurrent graph traversals?
First off: Garbage-collecting dead states would be cheap!
As would "determinizing" an NFA, that is merging states reached from the same edges so the machine needs.
Building upon that Brzozowski's Algorithm suggests determinizing an NFA & its inverse then un-inverting it to optimize a NFA.
2/3!
But even when optimal, a cacheline for this hypothetical architecture might need to be split. Ideally we'd split it into "strongly-connected components", where we wouldn't require back-edges.
Fleischer, et al. suggests removing an arbitrary edge & performing graph traversals from both nodes that edge connected to find all nodes reachable from both, from just one, & from neither. Recurse into the subgraphs reachable by just one.
3/3 Fin!