login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A349481 a(n) is the number of Boolean factors of the contranominal scale of size n by the GreConD algorithm for Boolean matrix factorization. 1
0, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Contranominal scales can be considered as Boolean matrices of size n X n full of ones except the main diagonal, which is filled by zeros (Ganter and R. Wille, 1999). The optimal number k of Boolean factors for a Boolean matrix A is known as its Schein rank (Kim, 1982; Marenich, 2010) and is defined as the smallest k such that A=P*Q, where * is Boolean matrix multiplication, A has the size n X m, and P,Q are n X k and k X m Boolean matrices, respectively. The problem of Boolean matrix factorization (BMF) is NP-hard and one of the state-of-the-art greedy algorithms is GreConD (Belohlavek & Vychodil, 2010). Contranominal scales are known as the worst theoretical case w.r.t. the number of potential Boolean factors (formal concepts), 2^n (Albano, 2014; Albano and Chornomaz, 2017; Dürrschnabel et al., 2021), while their Schein rank is given by A305233. The output of GreConD does not always result in the optimal number of factors for contranominal scales, so the sequence of its outputs is checked empirically for n up to 128 and the formula for a(n) is provided in (Ignatov & Yakovleva, 2021). See the links below for more checked examples up to n=513.

REFERENCES

A. Albano and B. Chornomaz, Why concept lattices are large: extremal theory for generators, concepts, and VC-dimension. Int. J. Gen. Syst. 46(5) (2017) 440-457.

A. Albano, Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts. ICFCA 2014: 44-53.

R. Belohlavek and V. Vychodil, Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences 76(1) (2010) 3 - 20.

D. Dürrschnabel, M. Koyda, and G. Stumme, Attribute Selection Using Contranominal Scales. ICCS 2021: 127-141.

B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundations. Springer 1999, ISBN 978-3-540-62771-5, pp. I-X, 1-284.

D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales. FCA4AI@IJCAI 2021, 87-98.

K. H. Kim, Boolean matrix theory and applications. Marcel Dekker, New York and Basel (1982).

E. Marenich, Determining the Schein Rank of Boolean Matrices. Matrix Methods: Theory, Algorithms and Applications (2010) 85-103.

LINKS

Dmitry I. Ignatov, Table of n, a(n) for n = 1..513

Dmitry I. Ignatov, iPython notebook with the code and the examples of factors up to 513

Dmitry I. Ignatov, iPython notebook in PDF with the code and the examples of factors up to 513

D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales.

A. Yakovleva, Python Code.

Wikipedia, Formal Concept Analysis.

FORMULA

a(n) = floor(log_2(n)) + ceiling(log_2(n)).

EXAMPLE

For n=1 there are zero factors.

For n=2 the factors are ({1}, {0}), ({0}, {1}). The coresspoding factorization is below:

  A  =  P  *  Q

[0 1] [0 1] [1 0]

[1 0] [1 0] [0 1] .

For n=3 the factors are ({1, 2}, {0}), ({0, 2}, {1}), ({0, 1}, {2}). The corresponding trivial factorization, A=P*Q, where P=A and Q is the 3 X 3 identity matrix, is below:

[0 1 1] [0 1 1] [1 0 0]

[1 0 1]=[1 0 1]*[0 1 0]

[1 1 0] [1 1 0] [0 0 1] .

For n=4 the factors are ({2, 3}, {0, 1}), ({0, 1}, {2, 3}), ({1, 3}, {0, 2}), ({0, 2}, {1, 3}).

...

For n=7 the factors are ({3, 4, 5, 6}, {0, 1, 2}), ({0, 1, 2, 6}, {3, 4, 5}), ({1, 2, 4, 5}, {0, 3, 6}), ({0, 2, 3, 5}, {1, 4, 6}), ({0, 1, 3, 4, 6}, {2, 5}).

The nontrivial factorizaion with the number of factors k=5 smaller than n=7 is below:

[0 1 1 1 1 1 1] [0 1 0 1 1]

[1 0 1 1 1 1 1] [0 1 1 0 1] [1 1 1 0 0 0 0]

[1 1 0 1 1 1 1] [0 1 1 1 0] [0 0 0 1 1 1 0]

[1 1 1 0 1 1 1]=[1 0 0 1 1]*[1 0 0 1 0 0 1]

[1 1 1 1 0 1 1] [1 0 1 0 1] [0 1 0 0 1 0 1]

[1 1 1 1 1 0 1] [1 0 1 1 0] [0 0 1 0 0 1 0]

[1 1 1 1 1 1 0] [1 1 0 0 1] .

CROSSREFS

A305233 represents the Schein rank of the contranominal scale of size n.

Sequence in context: A006159 A081610 A063273 * A200262 A347762 A270432

Adjacent sequences:  A349478 A349479 A349480 * A349482 A349483 A349484

KEYWORD

nonn

AUTHOR

Dmitry I. Ignatov, Nov 19 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 10:16 EDT 2022. Contains 356069 sequences. (Running on oeis4.)