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

CC BY-SA 4.0
2021-02-04T15:30:56.590Z
Right -- for example, Lipschitz-continuous. Good question!
Aryeh
CC BY-SA 4.0
2021-02-04T18:56:43.197Z
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.
Shaull
CC BY-SA 4.0
2021-02-04T19:13:14.220Z
Yes, but he did specify a highly restricted transition function.
Aryeh
CC BY-SA 4.0
2021-02-04T14:54:23.760Z
2021-02-04T14:54:23.760Z
Ronen Brafman
<p>Automata over infinite alphabets have been studied in many contexts (see e.g., <a href="https://www.iitgoa.ac.in/%7Eamal/papers/iiscvolume.pdf" rel="noreferrer">this paper</a> as a starting point).</p>
<p>Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason:</p>
<p>Given an automaton with <span class="math-container">$n$</span> states, there are only <span class="math-container">$2^{n^2}$</span> transition matrices. Thus, if your alphabet has more than <span class="math-container">$2^{n^2}$</span> letters, then some letters will induce the same transitions. That is, you can partition them to classes of equivalent symbols.</p>
<p>This essentially reduces the model back to finitely many letters.</p>
<p>Note that the final weights do make a difference, but this has more to do with the standard model of weighted automata.</p>
<p>Typically, we're interested in infinite alphabets in the context of <em>data words</em>: these are words over a finite domain <span class="math-container">$D$</span>, that represents variables whose range is an infinite domain. Then, a common model is that of <em>variable automata</em>, which have been studied a lot (e.g., <a href="https://www.cs.huji.ac.il/%7Eornak/publications/lata10.pdf" rel="noreferrer">this paper</a> and references therein).</p>

CC BY-SA 4.0
2021-02-04T14:02:49.570Z
Great answer, thanks!
Aryeh
CC BY-SA 4.0
2021-02-04T14:01:26.927Z
2021-02-04T14:01:26.927Z
Shaull
<p>Consider a finite state set <span class="math-container">$Q$</span>, with a distinguished start state <span class="math-container">$s\in Q$</span>, as well as two functions: a transition function <span class="math-container">$\delta:Q\times\mathbb{R}\to Q$</span> and a final output function <span class="math-container">$F:Q\to\mathbb{R}$</span>. The tuple <span class="math-container">$(Q,s,\delta,F)$</span> defines a mapping <span class="math-container">$f:\mathbb{R}^*\to\mathbb{R}$</span> --- that is, from finite sequences of reals to reals --- in exactly the same way as a classic DFA over a finite alphabet <span class="math-container">$\Sigma$</span> defines a mapping
<span class="math-container">$\Sigma^*\mapsto\{0,1\}$</span>.</p>
<p>Have such DFA analogs over the real alphabet been considered before?</p>

CC BY-SA 4.0
2021-02-04T17:20:03.127Z
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.
mrp
CC BY-SA 4.0
2021-02-04T18:52:20.493Z
I asked a somewhat similar question (about infinite alphabet automata more generally) awhile ago: https://cstheory.stackexchange.com/questions/8758/survey-on-infinite-alphabet-automata.
Huck Bennett
<automata-theory>
Finite-State Automata over a real-valued alphabet
Aryeh
# Finite-State Automata over a real-valued alphabet

(Asked by: username_0 on 2021-02-04)

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?

**Tags:** automata-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: I asked a somewhat similar question (about infinite alphabet automata more generally) awhile ago: https://cstheory.stackexchange.com/questions/8758/survey-on-infinite-alphabet-automata.  

---

## 2 answers

### Answer by username_4 on 2021-02-04. Score: 10 | Accepted answer

Automata over infinite alphabets have been studied in many contexts (see e.g., [this paper](https://www.iitgoa.ac.in/%7Eamal/papers/iiscvolume.pdf) 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](https://www.cs.huji.ac.il/%7Eornak/publications/lata10.pdf) and references therein).

> **Comments:**
> **username_0**: Great answer, thanks!  

---

### Answer by username_3 on 2021-02-04. Score: 4

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?

> **Comments:**
> **username_0**: Right -- for example, Lipschitz-continuous. Good question!  
> **username_4**: 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.  
> **username_0**: Yes, but he did specify a highly restricted transition function.  

---

