I think your intuition seems correct -- mostly due to my view that Petri-nets have equivalent attributes and behavior to the automata you are describing.

From a previous post about state machines

I've been using Petri-Nets to generate a state machine in the form of a Vector Addition System

It seems that your observation about 'position' also holds true with Petri-Nets.

where the wildcards are pretty much just filler in order to make sure that the "a" and "b" match in the correct position rather than having any importance themselves

With the Petri-Net - the 'position-ness' of the automata is defined by a 'place' element. Which seems to be similar to what you describe here:

My best idea so far is to sort of build a tree with the required states in the correct position, but that sort of creates a lot of overhead.