MAXIMAL DEPTHS OF BOOLEAN FUNCTIONS

TitleMAXIMAL DEPTHS OF BOOLEAN FUNCTIONS
Publication TypeJournal Article
Year of Publication2004
AuthorsSkordev D
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume96
Keywordsalgorithmic computability, Boolean function, complete set, maximal depth, Post theorem
Abstract

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.

2000 MSC

main 06E30, secondary 94C10

AttachmentSize
PDF icon 0996.pdf25.9 KB
AttachmentSize
PDF icon 96-089-099.pdf918.84 KB