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, 2021 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, 2021 at 18:52

2 Answers 2

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, 2021 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, 2021 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, 2021 at 18:56
  • 1
    $\begingroup$ Yes, but he did specify a highly restricted transition function. $\endgroup$
    – Aryeh
    Feb 4, 2021 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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