Consider a finite state set $Q$, with a distinguished start state $s\in Q$, as well as two functions: a transition function $\delta:Q\times\mathbb{R}\to Q$ and a final output function $F:Q\to\mathbb{R}$. The tuple $(Q,s,\delta,F)$ defines a mapping $f:\mathbb{R}^*\to\mathbb{R}$ --- that is, from finite sequences of reals to reals --- in exactly the same way as a classic DFA over a finite alphabet $\Sigma$ defines a mapping $\Sigma^*\mapsto\{0,1\}$.

Have such DFA analogs over the real alphabet been considered before?

  • $\begingroup$ This seems very similar to weighted automata. Not exactly the same, but I have a feeling that your set up can be seen as a special case of weighted automata. $\endgroup$
    – mrp
    Feb 4 at 17:20
  • 1
    $\begingroup$ I asked a somewhat similar question (about infinite alphabet automata more generally) awhile ago: cstheory.stackexchange.com/questions/8758/…. $\endgroup$ Feb 4 at 18:52

Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point).

Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason:

Given an automaton with $n$ states, there are only $2^{n^2}$ transition matrices. Thus, if your alphabet has more than $2^{n^2}$ letters, then some letters will induce the same transitions. That is, you can partition them to classes of equivalent symbols.

This essentially reduces the model back to finitely many letters.

Note that the final weights do make a difference, but this has more to do with the standard model of weighted automata.

Typically, we're interested in infinite alphabets in the context of data words: these are words over a finite domain $D$, that represents variables whose range is an infinite domain. Then, a common model is that of variable automata, which have been studied a lot (e.g., this paper and references therein).

  • 1
    $\begingroup$ Great answer, thanks! $\endgroup$
    – Aryeh
    Feb 4 at 14:02

What if you don't assume a finite state space, but rather allow the set Q to be R, yet require delta to be "nice", e.g., smooth and easily computable? Then this presumably defines a restricted class of functions over sequences of reals. Has this question been studied?

  • $\begingroup$ Right -- for example, Lipschitz-continuous. Good question! $\endgroup$
    – Aryeh
    Feb 4 at 15:30
  • $\begingroup$ As soon as your state space becomes countable, you can essentially encode the entire history of the run within the states (i.e., just take an infinite tree as your state space). This makes the "automaton" aspect somewhat redundant. $\endgroup$
    – Shaull
    Feb 4 at 18:56
  • 1
    $\begingroup$ Yes, but he did specify a highly restricted transition function. $\endgroup$
    – Aryeh
    Feb 4 at 19:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.