Closure examples

The galactic.algebras.examples.closure defines classes for testing closures.

NumericalClosed for representing closed sets of integers;
NumericalClosure for representing closure of sets of integers;
ExtensibleNumericalFamily for representing Moore family of closed sets of integers;

class NumericalClosed(closure, min_element=None, max_element=None)

Bases: ClosedEnumerableMixin[int], Element

It represents finite closed sets of ints.

It is defined by the minimal and maximal value.

Parameters:

closure (NumericalClosure) – The closure operator
min_element (int | None, default: None) – An optional minimum element
max_element (int | None, default: None) – An optional maximum element

property min_element: int | None

Get the minimum element.

Returns:: The minimum element or None if there is no minimum element.
Return type:: int | None

property max_element: int | None

Get the maximum element.

Returns:: The maximum element or None if there is no maximum element.
Return type:: int | None

property closure: AbstractClosure[_T]

Get the closure operator.

Returns:: The closure operator.
Return type:: AbstractClosure[_T]

equivalence(element)

Compute equivalences of the element.

Parameters:: element (TypeVar(_T)) – The element whose equivalences are requested
Returns:: An iterator over the equivalence elements of element
Return type:: Iterator[_T]

join(*others)

Return the supremum of this element and the others.

Parameters:: *others (Self) – The others elements
Returns:: The join of this element and the others
Return type:: Self

join_level(generators)

Compute the level of an element considering an iterable of generators.

Parameters:: generators (Iterable[Self]) – An iterable of generators.
Returns:: The level of the element.
Return type:: int

meet(*others)

Return the infimum of this element and the others.

Parameters:: *others (Self) – The others elements
Returns:: The meet of this element and the others
Return type:: Self

meet_level(generators)

Compute the level of an element considering an iterable of generators.

Parameters:: generators (Iterable[Self]) – An iterable of generators.
Returns:: The level of the element.
Return type:: int

subsumption(element)

Compute subsumed elements of the element.

Parameters:: element (TypeVar(_T)) – The element whose subsumed elements are requested
Returns:: An iterator over the subsumed elements of element
Return type:: Iterator[_T]

property support: float

Get the closed set support.

Returns:: The closed set support.
Return type:: float

supsumption(element)

Compute supsumed elements of the element.

Notes

supsumption is a neologism to designate the inverse relation of subsumption.

Parameters:: element (TypeVar(_T)) – The element whose supsumed elements are requested
Returns:: An iterator over the supsumed elements of element
Return type:: Iterator[_T]

class NumericalClosure(min_element=None, max_element=None)

Bases: object

iT represents a simple numerical closure.

Parameters:

min_element (int | None, default: None) – The minimum element.
max_element (int | None, default: None) – The maximum element.

__call__(*others, elements=None)

Compute the closure of an iterable of elements.

Parameters:

*others (AbstractClosed[int]) – A sequence of finite closed sets.
elements (Iterable[int] | None, default: None) – An optional iterable of int.

Returns:

The new closed set.

Return type:

NumericalClosed

Raises:

ValueError – If an element is not in the universe.
ValueError – If the closure is not correct.
TypeError – If an element is not of the correct class.

class ExtensibleNumericalFamily(closure, *others, elements=None)

Bases: ExtensibleMooreFamilyEnumerable[int]

It defines a Moore family on subset of integers.

property atoms: Collection[_E]

Get the atoms of this lattice.

Return type:: The atoms.

property bottom: Collection[_E]

Get the bottom elements.

Return type:: The bottom elements.

closure()

Get the underlying closure operator of the current Moore family.

Return type:: AbstractClosureEnumerable[TypeVar(_T)]
Returns:: The closure operator.

property co_atoms: Collection[_E]

Get the co-atoms of this lattice.

Return type:: The co-atoms.

copy()

Get a copy of the lattice.

Return type:: Self
Returns:: The copy of this lattice.

property cover: AbstractFiniteCoveringRelation[_E]

Get the covering relation of this lattice.

Return type:: The covering relation.

extend(iterable)

Extend this lattice.

Parameters:: iterable (Iterable[TypeVar(_E, bound= Element)]) – An iterable of values.
Return type:: None

filter(element)

Get a filter of a lattice.

Parameters:: element (TypeVar(_E, bound= Element)) – The lower limit.
Returns:: A view on the bounded lattice.
Return type:: AbstractFinitePartiallyOrderedSet[_E]
Raises:: ValueError – If the element does not belong to the lattice.

property global_entropy: float

Compute the global entropy of the Moore family.

\[H(L)=\sum_{A\in L}p(A)I(A)=n-\frac{\sum_{A\in L}\kappa(( A,B))\log_2(\kappa(A))}{2^n}\]

Notes

See Information .

Returns:: The global entropy.
Return type:: float

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> round(family.global_entropy, 3)
1.311

property global_information: float

Compute the global information of the Moore family.

It is equal to the global entropy multiplied by the number of element defined by the closure operator.

\[I(L)=n H(L)\]

See also

See Information.

Returns:: The global information.
Return type:: float

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> round(family.global_information, 3)
7.868

property global_logarithmic_stability: float

Compute the global normalized logarithmic stability of the Moore family.

\[\lambda(L)=\sum_{A\in L}p(A)\lambda(A)\]

Returns:: The global normalized logarithmic stability.
Return type:: float

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> round(family.global_logarithmic_stability, 3)
0.335

property global_stability: float

Compute the global stability of the Moore family.

\[\sigma(L)=\sum_{A\in L}p(A)\sigma(A) =\sum_{A\in L}\frac{\kappa(A)^2}{2^{|A|+n}}\]

Returns:: The global stability.
Return type:: float

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> round(family.global_stability, 3)
0.703

greatest_join_irreducible(limit, strict=False)

Get the greatest join irreducible smaller than a limit.

Parameters:

limit (TypeVar(_J, bound= Joinable)) – The limit whose greatest join irreducible are requested.
strict (bool, default: False) – Is the comparison strict?

Returns:

The greatest join irreducible smaller than the limit.

Return type:

Collection[_J]

ideal(element)

Get an ideal of a lattice.

Parameters:: element (TypeVar(_E, bound= Element)) – The upper limit.
Returns:: A view on the bounded lattice.
Return type:: AbstractFinitePartiallyOrderedSet[_E]
Raises:: ValueError – If the element does not belong to the lattice.

information()

Get an iterator on elements (\(A\), \(I(A)\)).

\(I(A)\) is the information of \(A\). :rtype: Iterator[Measure[TypeVar(_T), float]]

\[I(A)=-\log_2(p(A)\]

Yields:: Measure[_T, float] – A couple (elements, information).

Notes

See Information .

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> for information in family.information():
...     print(information.closed, information.value)
2..3 4.0
1..3 4.0
2..4 4.0
1..4 4.0
0..5 0.4150374992788439

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a superset of the other.
Return type:: bool

property join_irreducible: AbstractFinitePartiallyOrderedSet[_E]

Get the join-irreducible elements of this lattice.

Return type:: The join-irreducible elements.

logarithmic_stabilities()

Get an iterator on (\(A\), \(\lambda(A)\)).

\(\lambda(A)\) is the normalized logarithmic stabilities of \(A\) (the normalized logarithmic stability is always between 0 and 1). :rtype: Iterator[Measure[TypeVar(_T), float]]

if \(\kappa(A)\) is equal to \(2^{|A|}\), the normalized logarithmic stability is equal to 1.
if \(\kappa(A)\) is equal to \(1\), the normalized logarithmic stability is equal to 0
the special case \(A=\emptyset\) (\(2^{|A|}=\kappa(A)=1\)) gives \(\lambda(\emptyset)=1\) by convention.

\[\begin{split}\begin{eqnarray} \lambda(A) &=&\frac{-\log_2\left(1-\sigma(A)+\frac{1}{2^{|A|}}\right)}{|A|}\\ &=&\frac{-\log_2\left(\frac{2^{|A|}-\kappa(A)+1}{2^{|A|}}\right)}{|A|}\\ &=&\frac{|A|-\log_2\left(2^{|A|}-\kappa(A)+1\right)}{|A|}\\ &=&1-\frac{\log_2\left(2^{|A|}-\kappa(A)+1\right)}{|A|}\\ \lambda(\emptyset) &=&1\\ \end{eqnarray}\end{split}\]

See also

parts()

Notes

Originally, the logarithmic stability was defined using

\[\begin{split}\begin{eqnarray} -\log_2\left(1-\sigma(A)\right) &=&-\log_2\left(1-\frac{\kappa(A)}{2^{|A|}}\right)\\ &=&|A|-\log_2\left(2^{|A|}-\kappa(A)\right)\\ \end{eqnarray}\end{split}\]

but this formulae can give an infinity value, and it is not normalized between elements.

References

A. Buzmakov , S. Kuznetsov , A. Napoli , Scalable estimates of element stability, in: C. Glodeanu, M. Kaytoue, C. Sacarea (Eds.), Formal element Analysis, Lecture Notes in Computer Science, 8478, Springer International Publishing, 2014, pp. 157-172

Yields:: Measure[_T, float] – A couple (elements, normalized logarithmic stability).

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> for stability in family.logarithmic_stabilities():
...     print(stability.closed, round(stability.value, 3))
2..3 1.0
1..3 0.226
2..4 0.226
1..4 0.075
0..5 0.319

lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_E, bound= Element)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_E]

property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

property meet_irreducible: AbstractFinitePartiallyOrderedSet[_E]

Get the meet-irreducible elements of this lattice.

Return type:: The meet-irreducible elements.

property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

property order: AbstractFinitePartialOrder[_E]

Get the partial order of this lattice.

Return type:: The partial order.

parts()

Get an iterator on (\(A\), \(\kappa(A)\)).

\(\kappa(A)\) is the number of parts of \(A\) whose closure \(\phi\) equal to \(A\). :rtype: Iterator[Measure[TypeVar(_T), int]]

\[\kappa(A)= \left|\left\{ \tilde A\subseteq A: \phi\left(\tilde A\right)=A \right\}\right|\]

Yields:: Measure[_T, int] – A couple (elements, #parts) \(\tilde A\subseteq A\subseteq X\) whose closure is equal to the element.

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> for part in family.parts():
...     print(part.closed, part.value)
2..3 4
1..3 4
2..4 4
1..4 4
0..5 48

probabilities()

Get an iterator on (\(A\), \(p(A)\)).

\(p(A)\) is the probability of \(A\). :rtype: Iterator[Measure[TypeVar(_T), float]]

\[p(A)=\frac{\kappa(A)}{2^n}\]

See also

parts()

Yields:: Measure[_T, float] – A couple (elements, probability).

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> for probability in family.probabilities():
...     print(probability.closed, probability.value)
2..3 0.0625
1..3 0.0625
2..4 0.0625
1..4 0.0625
0..5 0.75

property reduced_context: AbstractFiniteBinaryRelation[_E, _E]

Get the reduced context from this lattice.

Returns:: The reduced context.
Return type:: AbstractFiniteBinaryRelation[_E, _E]

smallest_meet_irreducible(limit, strict=False)

Get the smallest meet irreducible greater than a limit.

Parameters:

limit (TypeVar(_M, bound= Meetable)) – The limit whose smallest meet irreducible are requested.
strict (bool, default: False) – Is the comparison strict?

Returns:

The smallest meet irreducible greater than the limit.

Return type:

Collection[_M]

stabilities()

Get an iterator on (\(A\), \(\sigma(A)\)).

\(\sigma(A)\) is the stability of \(A\). :rtype: Iterator[Measure[TypeVar(_T), float]]

\[\sigma(A)=\frac{\kappa(A)}{2^{|A|}}\]

See also

parts()

Yields:: Measure[_T, float] – A couple (elements, stability), an iterator on elements and their stability.

Examples

>>> from galactic.algebras.examples.closure import ExtensibleNumericalFamily
>>> from galactic.algebras.examples.closure import NumericalClosure
>>> closure = NumericalClosure(min_element=0, max_element=5)
>>> family = ExtensibleNumericalFamily(closure)
>>> family.extend(
...     [
...         closure(elements=[1, 2, 3]),
...         closure(elements=[2, 3, 4])
...     ]
... )
>>> for stability in family.stabilities():
...     print(stability.closed, round(stability.value, 3))
2..3 1.0
1..3 0.5
2..4 0.5
1..4 0.25
0..5 0.75