<p>I believe that there are no reasonable model where the number of machines grow subexponentially, in the sense that either such a model would be remarkably not expressive, or would require huge machines to recognize very simple languages.</p>
<p>One reason to think so is the following: let <span class="math-container">$s\colon \mathbb{N} \to \mathbb{N}$</span> be a subexponential function (in the sense that <span class="math-container">$\log s \in o(n)$</span>) such that for every <span class="math-container">$k \in \mathbb{N}$</span>, there are at most <span class="math-container">$s(k)$</span> machines with <span class="math-container">$k$</span> states.
Then for any <span class="math-container">$n\in\mathbb{N}$</span>, if all languages <span class="math-container">$L \subseteq \{0,1\}^n$</span> are recognizable, let <span class="math-container">$f(n)$</span> be the maximal number of states of a machine recognizing some <span class="math-container">$L \subseteq \{0,1\}^n$</span>. Since there are <span class="math-container">$2^{2^n}$</span> such languages, we have <span class="math-container">$2^{2^n} \leq s(f(n))$</span> and hence <span class="math-container">$2^n \in o(f(n))$</span>. In other words, the machines recognizing <span class="math-container">$L$</span>'s must be superexponential.</p>
<p>Even under a much weaker assumption, say that there are at least <span class="math-container">$2^n$</span> languages <span class="math-container">$L \subseteq \{0,1\}^n$</span> that are recognizable, then you get <span class="math-container">$n \in o(f(n))$</span>. Note that this bound of <span class="math-container">$2^n$</span> is reached if you recognize exactly all singleton languages of the form <span class="math-container">$\{w\}$</span> for <span class="math-container">$w\in \{0,1\}^n$</span>. So either this machine model does not recognize all singletons <span class="math-container">$\{w\}$</span>, or needs much more states than the length of <span class="math-container">$w$</span>.</p>

CC BY-SA 4.0
2023-12-29T23:04:59.757Z
I believe you mean $s(n)$ be the *minimal* number of states for recognizing the language? Furthermore, you did not define $f(n)$, so I could not follow your argument in full detail. However, I agree that there would necessarily be a loss of generality, since some problems could only be solved by using an exponential or super-exponential number of states. But this is not necessarily an issue. If the model class is efficient at expressing solutions for some specific class of problems with some practical motivation, then this would certainly be an acceptable restriction.
stateMachineOperator
CC BY-SA 4.0
2023-12-30T10:21:52.637Z
It was a typo: I wrote $f(n)$ instead of $s(n)$ at some point, I edited my answer.
Rémi
CC BY-SA 4.0
2023-12-29T22:38:44.747Z
2023-12-30T10:19:39.937Z
2023-12-30T10:19:39.937Z
Rémi
<p>The question is not completeley formal, but let me give at least an example of such machines: DFAs on unary alphabet, with a bound <span class="math-container">$k$</span> on the number of accepting (or rejecting) states. These machines are not trivial, they can talk about properties of the length of the input word: basically a disjunction of at most <span class="math-container">$k$</span> properties of the form &quot;length is exactly <span class="math-container">$l$</span>&quot;, or &quot;length is more than <span class="math-container">$l$</span> and <span class="math-container">$i$</span> modulo <span class="math-container">$j$</span>&quot;.</p>
<p>Agreed it is a bit artificial, if we don't put this bound <span class="math-container">$k$</span> then you have exponentially many machines, but in order to give a yes/no answer to your question you would have to be more precise about what constitutes an acceptable model.</p>

CC BY-SA 4.0
2023-12-31T12:35:48.727Z
Well, my question wasn't completely formal, because I don't have a specific application in mind. I'm interested in model checking and related formal methods. I've been thinking that it might be interesting to investigate unconventional model classes. Maybe the expressive flexibility of model classes such as Mealy machines isn't always an advantage. I'm wondering if there are real-world applications (like network protocols for example), where a more constrained model class would be sufficient for capturing the behavior, while reducing room for errors during design and simplifying verification.
stateMachineOperator
CC BY-SA 4.0
2023-12-30T16:45:09.853Z
2023-12-30T16:45:09.853Z
Denis
<p>State machines are useful tools for system modelling. They allow for a compact visual notation of discrete systems and provide a formal model of them. However, reasoning about the correctness of an implementation isn't easy due to the large model spaces. Let's take Mealy machines as an example and assume we have some fixed numbers <span class="math-container">$N$</span> of states, <span class="math-container">$I$</span> of inputs and <span class="math-container">$O$</span> of outputs. Then, we have <span class="math-container">$IN$</span> transitions in the state machine, each of which can target one of <span class="math-container">$N$</span> states and output one of <span class="math-container">$O$</span> symbols. So there are <span class="math-container">$IN^{ON}$</span> possible Mealy machines to construct with these parameters.</p>
<p>But this expressiveness comes at a cost, as the capacity of the model space greatly complicates the testing of a given state machine implementation. And it is not obvious to me whether the exponentiality of the model space is a necessary property for the usefulness of the model class. Thus, I'm wondering: Are there any model classes for discrete-state systems whose model space does not scale exponentially with their model parameters? I've searched for literature on this topic, but didn't find anything that fits my question. I would be grateful for any pointers.</p>

<cc.complexity-theory><co.combinatorics><model-checking><formal-methods><formal-modeling>
State machine classes with sub-exponentially growing model spaces
stateMachineOperator
# State machine classes with sub-exponentially growing model spaces

(Asked by: username_0 on 2023-12-29)

State machines are useful tools for system modelling. They allow for a compact visual notation of discrete systems and provide a formal model of them. However, reasoning about the correctness of an implementation isn't easy due to the large model spaces. Let's take Mealy machines as an example and assume we have some fixed numbers $N$ of states, $I$ of inputs and $O$ of outputs. Then, we have $IN$ transitions in the state machine, each of which can target one of $N$ states and output one of $O$ symbols. So there are $IN^{ON}$ possible Mealy machines to construct with these parameters.

But this expressiveness comes at a cost, as the capacity of the model space greatly complicates the testing of a given state machine implementation. And it is not obvious to me whether the exponentiality of the model space is a necessary property for the usefulness of the model class. Thus, I'm wondering: Are there any model classes for discrete-state systems whose model space does not scale exponentially with their model parameters? I've searched for literature on this topic, but didn't find anything that fits my question. I would be grateful for any pointers.

**Tags:** cc.complexity-theory, co.combinatorics, model-checking, formal-methods, formal-modeling

---

## 2 answers

### Answer by username_1 on 2023-12-29. Score: 2

I believe that there are no reasonable model where the number of machines grow subexponentially, in the sense that either such a model would be remarkably not expressive, or would require huge machines to recognize very simple languages.

One reason to think so is the following: let $s\colon \mathbb{N} \to \mathbb{N}$ be a subexponential function (in the sense that $\log s \in o(n)$) such that for every $k \in \mathbb{N}$, there are at most $s(k)$ machines with $k$ states.
Then for any $n\in\mathbb{N}$, if all languages $L \subseteq \{0,1\}^n$ are recognizable, let $f(n)$ be the maximal number of states of a machine recognizing some $L \subseteq \{0,1\}^n$. Since there are $2^{2^n}$ such languages, we have $2^{2^n} \leq s(f(n))$ and hence $2^n \in o(f(n))$. In other words, the machines recognizing $L$'s must be superexponential.

Even under a much weaker assumption, say that there are at least $2^n$ languages $L \subseteq \{0,1\}^n$ that are recognizable, then you get $n \in o(f(n))$. Note that this bound of $2^n$ is reached if you recognize exactly all singleton languages of the form $\{w\}$ for $w\in \{0,1\}^n$. So either this machine model does not recognize all singletons $\{w\}$, or needs much more states than the length of $w$.

> **Comments:**
> **username_0**: I believe you mean $s(n)$ be the *minimal* number of states for recognizing the language? Furthermore, you did not define $f(n)$, so I could not follow your argument in full detail. However, I agree that there would necessarily be a loss of generality, since some problems could only be solved by using an exponential or super-exponential number of states. But this is not necessarily an issue. If the model class is efficient at expressing solutions for some specific class of problems with some practical motivation, then this would certainly be an acceptable restriction.  
> **username_1**: It was a typo: I wrote $f(n)$ instead of $s(n)$ at some point, I edited my answer.  

---

### Answer by username_2 on 2023-12-30. Score: 0

The question is not completeley formal, but let me give at least an example of such machines: DFAs on unary alphabet, with a bound $k$ on the number of accepting (or rejecting) states. These machines are not trivial, they can talk about properties of the length of the input word: basically a disjunction of at most $k$ properties of the form "length is exactly $l$", or "length is more than $l$ and $i$ modulo $j$".

Agreed it is a bit artificial, if we don't put this bound $k$ then you have exponentially many machines, but in order to give a yes/no answer to your question you would have to be more precise about what constitutes an acceptable model.

> **Comments:**
> **username_0**: Well, my question wasn't completely formal, because I don't have a specific application in mind. I'm interested in model checking and related formal methods. I've been thinking that it might be interesting to investigate unconventional model classes. Maybe the expressive flexibility of model classes such as Mealy machines isn't always an advantage. I'm wondering if there are real-world applications (like network protocols for example), where a more constrained model class would be sufficient for capturing the behavior, while reducing room for errors during design and simplifying verification.  

---

