# State machine classes with sub-exponentially growing model spaces

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.

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

• 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. Commented Dec 29, 2023 at 23:04
• It was a typo: I wrote $f(n)$ instead of $s(n)$ at some point, I edited my answer.
– Rémi
Commented Dec 30, 2023 at 10:21

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.

• 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. Commented Dec 31, 2023 at 12:35