Complexity of automata computing values of functions given in the prefix form

MaRDI QIDQ5936690zbMATH OpenFDO

Authors A. A. Kudrin

Publication date 4 July 2001

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

zbMATH Keywords

complexity of devicesvalues of functions

Mathematics Subject Classification ID

Boolean functions (06E30)

Review text

The note deals with the problem of estimating the complexity of devices of automata for computing the values of formulas. The formulas are taken over the set of all Boolean functions of two-variables which do not contain imaginary variables and the negation function of one variable. All functions are assumed to be written in the prefix form.

Recommendations

• Complexity of automata evaluating formulas
• Statistical estimation of the structure of a finite population
• On the automata functional systems
• On the complexity of realization of Boolean functions by formulas
• Size-time complexity of Boolean networks for prefix computations

Cited in

(2)

• Complexity of automata evaluating formulas
• Computing the prefix of an automaton

This page was built for publication: Complexity of automata computing values of functions given in the prefix form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936690)