zbMATH — the first resource for mathematics

Complexity of automata evaluating formulas. (English. Russian original) Zbl 0914.94028
Mosc. Univ. Math. Bull. 51, No. 4, 18-20 (1996); translation from Vestn. Mosk. Univ., Ser. I 1996, No. 4, 22-24 (1996).
The paper deals with formulas in an operator form over a set consisting of all two-place operations and negation. The authors investigate the problem on minimal possible number of states for an automaton evaluating. Boolean expressions of a given length in various operator bases.
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q45 Formal languages and automata
PDF BibTeX Cite