12
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I recently read Bojanczyk et al. "Automata with Group Actions," and it cites Segoufin as the survey of this area. $\endgroup$
    – Radu GRIGore
    Oct 28 '11 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.