Error-free and best-fit extensions of partially defined Boolean functions

DOI10.1006/inco.1997.2687zbMath0892.68091OpenAlexW2026480866MaRDI QIDQ1383161

Endre Boros, Toshihide Ibaraki, Kazuhisa Makino

Publication date: 27 July 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b369bc48e61fac028d4532180d972b22dad1c59b

zbMATH Keywords

polynomial algorithmsinductionNP-hardnesslearning from examplespartially defined Boolean functionsminimum error extension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30)

Related Items

A decomposability index in logical analysis of data ⋮ Pareto-optimal patterns in logical analysis of data ⋮ Boolean analysis of incomplete examples ⋮ An efficient top-down search algorithm for learning Boolean networks of gene expression ⋮ Positive and Horn decomposability of partially defined Boolean functions ⋮ Logical analysis of data -- the vision of Peter L. Hammer ⋮ Logical analysis of numerical data ⋮ Variations on extending partially defined Boolean functions with missing bits. ⋮ Interior and exterior functions of positive Boolean functions. ⋮ Unnamed Item ⋮ Logical analysis of data: classification with justification ⋮ Analysing DNA microarray data using Boolean techniques ⋮ Bidual Horn functions and extensions ⋮ Inner-core and outer-core functions of partially defined Boolean functions ⋮ Extendable local partial clones ⋮ The Complexity of Partial Function Extension for Coverage Functions ⋮ Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees ⋮ Decision lists and related Boolean functions ⋮ Double Horn functions ⋮ Recognition of interval Boolean functions ⋮ Logical analysis of data with decomposable structures. ⋮ Logical analysis of binary data with missing bits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure identification in relational data
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Decomposability of partially defined Boolean functions
• Queries and concept learning
• Complexity of identification and dualization of positive Boolean functions
• A theory of the learnable
• Computational limitations on learning from examples
• On Learning Ring-Sum-Expansions
• Predicting Cause-Effect Relationships from Incomplete Discrete Observations
• The decision problem for some classes of sentences without quantifiers