7
$\begingroup$

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?

$\endgroup$
2
  • $\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$ – Huck Bennett Feb 4 at 18:52
10
$\begingroup$

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).

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

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?

$\endgroup$
3
  • $\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.