The equivalence of Horn and network complexity for Boolean functions
type: Item
instance of: scholarly article
title: The equivalence of Horn and network complexity for Boolean functions
zbMATH Open document ID: 0477.94034
DOI: 10.1007/BF00289267
author: Stal O. Anderaa
author: Egon Börger
published in: Acta Informatica
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 03B05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3750862
zbMATH Keywords: Horn complexity
zbMATH Keywords: complexity measure for logical functions
zbMATH Keywords: Horn formula
zbMATH Keywords: quasi-Horn formula
MaRDI profile type: Publication
cites work: Q5639707
cites work: Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
cites work: Complete problems for deterministic polynomial time
cites work: Q4053629
cites work: The network complexity and the Turing machine complexity of finite functions
cites work: Q3851624
cites work: Q5537599
cites work: Komplexität von Entscheidungsproblemen. Ein Seminar
full work available at URL: https://doi.org/10.1007/bf00289267
OpenAlex ID: W2042029993
description: scientific article; zbMATH DE number 3750862