<p>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:</p>

<ul>
<li>"Automata and logics for words and trees over an infinite alphabet" by Segoufin, </li>
<li>"Finite memory automata" by Kaminski and Francez, FOCS 1990</li>
</ul>

<p>I'm wondering whether there's a good survey on different infinite alphabet automata models.</p>

CC BY-SA 3.0
2011-10-28T20:22:58.080Z
I recently read Bojanczyk et al. "Automata with Group Actions," and it cites Segoufin as *the* survey of this area.
Radu GRIGore
CC BY-SA 4.0
2022-11-03T02:04:55.037Z
More recently Bojańczyk also wrote the book "Slightly infinite sets" https://www.mimuw.edu.pl/~bojan/upload/main-10.pdf though I believe it doesn't attempt to be exhaustive.
Lê Thành Dũng 'Tito' Nguyễn
<reference-request><fl.formal-languages><automata-theory><survey>
Survey on infinite alphabet automata?
Huck Bennett
# Survey on infinite alphabet automata?

(Asked by: username_0 on 2011-10-27)

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.

**Tags:** reference-request, fl.formal-languages, automata-theory, survey
> **Comments:**
> **username_1**: I recently read Bojanczyk et al. "Automata with Group Actions," and it cites Segoufin as *the* survey of this area.  
> **username_2**: More recently Bojańczyk also wrote the book "Slightly infinite sets" https://www.mimuw.edu.pl/~bojan/upload/main-10.pdf though I believe it doesn't attempt to be exhaustive.  

---

## 0 answers

