The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using predicates from any decidable theory as the alphabet. The paper also references quite a few others including:
- "Automata and logics for words and trees over an infinite alphabet" by Segoufin,
- "Finite memory automata" by Kaminski and Francez, FOCS 1990
I'm wondering whether there's a good survey on different infinite alphabet automata models.