State machine classes with sub-exponentially growing model spaces

Question

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.

Answer 1

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

Answer 2

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.