Concerning average-case analysis, experimental tests based on random generated data are a precious tool but, in general, the combinatorial nature of the objects limits the range of those tests to small sizes.

The use of analytic combinatorics methods allows to obtain good approximations for nontrivial sizes, as well as exact asymptotic values. However, both methods rely on inductive definitions of the objects under study, which can be difficult to obtain. Moreover, as already mentioned, we need to deal with not just one combinatorial class, but with an infinite family of combinatorial classes indexed by the alphabetic size. This raises problems that are not studied in classical combinatorial classes, such as graphs or trees.

For regular languages, the most studied measure has been the state complexity (SC) , i.e. the size of its minimal DFA. Operational state complexity heavily depends on the conversion from NFAs to DFAs (determinisation). For instance, the worst-case state complexity of concatenation is \(m2^n -2^{n-1}\), where operands have SC \(n\) and \(m\), respectively. Thus, fine-grained analysis of determinisation is crucial for a better understanding of the state complexity of language operations.

We note that several experimental results [MMR15] suggested that, on average, the operational state complexity should be much smaller than the known worst-case results. We propose to identify subclasses for which determinisation is, on average, polynomial, as well as to find possible complexity cores in which all instances are exponential. As an example, recently, a class of NFAs for which determinisation is polynomial in the worst-case were studied -- Wheeler Languages [AAPP21]. However is still unknown how often in practice these languages are. Unambiguous nondeterministic models studied in [RSSR09,KMM23,GM17] ensure that for each word only one accepting computation exists. We plan to study their average complexity and their practical feasibility with regard to equivalence and membership.

Related to nondeterministic computations on a given input, several measures (branching, tree width, etc.) were also proposed to study the amount of nondeterminism of a model [HSS17]. It is known that, for finite automata, arbitrarily small amounts of finite nondeterminism still cause significant (but not necessarily exponential) blow-ups. This means that for those cases a simulation by parallel DFAs would be realistic. Empirical studies of these measures will help towards a better understanding of nondeterminism in practical applications.  These empirical studies can be based in approximated and randomised algorithms that in the case of determinisation may pro