On connected Boolean functions

DOI10.1016/S0166-218X(99)00098-0MaRDI QIDQ1961460zbMATH OpenFDO

Authors Oya Ekin, Peter L. Hammer, Alex Kogan

Publication date 14 February 2000

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

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00098-0

zbMATH Keywords

Boolean functioncomputational complexityDNF representationgeodeticmonotonesubgraph of the Boolean hypercubeunate

Mathematics Subject Classification ID

Connectivity (05C40) Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Review text

Various classes of Boolean functions are introduced: connected, strongly connected, geodetic, convex, strongly convex and concordant. They are characterized by some properties of the subgraph of the Boolean hypercube induced by the (false) true points of a function. The relationships between these properties and the DNF representation of a Boolean function as well as the inclusions between these classes are studied.

Recommendations

• scientific article; zbMATH DE number 5852793
• scientific article; zbMATH DE number 822063
• On the variables of the conjunctively polynomial-like Boolean functions
• On a class of Boolean functions with matroid property
• Coverings of Boolean graphs

Cites work

• A Way to Simplify Truth Functions
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3029852 (Why is no real title available?)
• On the geometric separability of Boolean functions
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time

Cited in

(16)

• Logical analysis of numerical data
• Convexity and logical analysis of data
• Expanding \(\text{FL}_{ew}\) with a Boolean connective
• Logical analysis of data -- the vision of Peter L. Hammer
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Integrated optimization model and algorithm for pattern generation and selection in logical analysis of data
• On the structure of solution-graphs for Boolean formulas
• On computing Boolean connectives of characteristic functions
• scientific article; zbMATH DE number 822063 (Why is no real title available?)
• Connected Boolean functions with a locally extremal number of prime implicants
• One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
• Join-irreducible Boolean functions
• On the Boolean connectivity problem for Horn relations
• Learning weakly convex sets in metric spaces
• Exact algorithms and hardness result for the Boolean connectivity problem of k-Horn formulas
• On a class of Boolean functions with matroid property

This page was built for publication: On connected Boolean functions

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