CLASS COUNTING AUTOMATA ON DATAWORDS
In the theory of automata over infinite alphabets, a central difficulty is that of finding a suitable compromise between expressiveness and algorithmic complexity. We propose an automaton model where we count the multiplicity of data values on an input word. This is particularly useful when such languages represent behaviour of systems with unboundedly many processes, where system states carry such counts as summaries. A typical recognizable language is: "every process does at most 4 actions labelled a". We show that emptiness is elementarily decidable, by reduction to the covering problem on Petri nets.
dataword decidability automata on infinite alphabet