Personal tools
You are here: Home Research Annual of Sofia University Tomes archive Tome 96 Maximal depths of Boolean functions

Maximal depths of Boolean functions

Author: Dimiter Skordev

Given any Boolean function, there is an upper bound of its depths with respect to arbitrary complete sets of such functions. We prove the algorithmic computability of the largest of these depths.

Annotation in PDF format: (PDF document 25Kb)
Keywords: Boolean function, complete set, Post theorem, maximal depth, algorithmic computability
2000 MSC: main 06E30, secondary 94C10