An upper estimate of the finite-state complexity for a~class of generating schemes containing complements and intersections

Z. R. Dang ; G. S. Tseitin

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VI, Tome 40 (1974), pp. 14-23

Résumé

Generating schemes (GS) are a method for generating regular sets of words that generalizes usual relular expressions on two lines: (1) the operations of set-theoretic complement and intersection are allowed, (2) oriented graphs with sets of words attached to their arcs are used in place of operations of union, concatenation and iteration of sets. The minimal number of states of a finite automaton that accepts the set represented by a GS is estimated in terms of the complexity of that GS. This function, as shown in [1], grows very rapidly for the class of all GS but is bounded by a $2^{2^n}$-like function for a class of GS specified in terms of admissible positions of intersections and complements. In this paper the estimate is improved, viz., $2^{2^n}$ is replaced by $\psi(n)$, the number of monotonous boolean functions of $n$ variables. The proof is based on a special relationship involving sets of words and sets of vertices and arcs of the GS.