Average time of computing Boolean operators

DOI10.1016/S0166-218X(02)00293-7MaRDI QIDQ4242300zbMATH OpenOpenAlexFDO

Authors A. V. Chashkin

Publication date 10 May 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(02)00293-7

zbMATH Keywords

Boolean functioncomplexitynon-branching programShannon's functionstraight-line program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analytic circuit theory (94C05)

Recommendations

• scientific article; zbMATH DE number 1037955
• Mean computing time of Boolean operators by programs with restricted memory
• Average case complexity for finite Boolean functions
• On the realization of linear Boolean operators by straight-line programs with a conditional stop

Cites work

• Average case complexity for finite Boolean functions
• scientific article; zbMATH DE number 3205680 (Why is no real title available?)

Cited in

(11)

• Time-optimal short-circuit evaluation of Boolean expressions
• On the average-case complexity of underdetermined functions
• Bounds for the average-case complexity of monotone Boolean functions
• Generalization of cardinality estimates for plane circuits realizing partial Boolean operators
• Time of computations on linear binary graphs
• Iteration of Boolean \((n,n)\)-operators
• Mean computing time of Boolean operators by programs with restricted memory
• scientific article; zbMATH DE number 1037955 (Why is no real title available?)
• On the realization of linear Boolean operators by straight-line programs with a conditional stop
• Average case complexity for finite Boolean functions
• An upper bound of unreliability of non-branching programs in an arbitrary complete finite basis for one-type constant faults at the outputs of computational operators

This page was built for publication: Average time of computing Boolean operators

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