Succinct representation of regular languages by Boolean automata. II (Q1068549)

Boolean automata are a generalization of finite automata in that the next state (the result of the transition function, given a state and a letter) is not just a single state (deterministic automata) or a set of states (nondeterministic automata) but a boolean function of the states. Boolean automata accept precisely the regular languages; also, they correspond in a natural way to certain language equation involving complementation as well as to sequential networks. In the first part [ibid. 13, 323-330 (1981; Zbl 0458.68017)] the author showed that for every \(n\geq 1\), there exists a boolean automaton \(B_ n\) with n states such that the smallest deterministic automaton for the same language has \(2^{2^ n}\) states. The present note continues this work by giving a precisely attainable lower bound on the succinctness of representing regular languages by boolean automata; namely, for every \(n\geq 1\), there exists a reduced automaton \(D_ n\) with n states such that the smallest boolean automaton accepting the same language has also n states.