page_title: Complexity index
section_title: Definition of sentry function
hierarchical_section_title: Complexity index / Definition of sentry function
caption_attribution_description: English: A schematic outlook of outer sentineling functionality: concept c0 sentineled against c1, c2, c3, c4 through {x1, x2, x3}. x1 and x3 are used as its own sentry points also by c1, and x2 prevents c1 to invade c0; x2 and x3 are sentry points also of c2, and x1 prevents invasion of c0 by c2; and x1 and x2 are sentry points also of c4 and x3 prevents invasion; c3 does not include c0 ∪ S(c0), hence it cannot invade c0. x4 is a useless point. All marked points are negative examples of c0.
context_page_description: Besides complexity intended as a difficulty to compute a function, in modern computer science and in statistics another complexity index of a function stands for denoting its information content, in turn affecting the difficulty of learning the function from examples.
  Complexity indices in this sense characterize the entire class of functions to which the one we are interested in belongs. Focusing on Boolean functions, the detail of a class of Boolean functions c essentially denotes how deeply the class is articulated.
  To identify this index we must first define a sentry function of.
  Let us focus for a moment on a single function c, call it a concept defined on a set of elements that we may figure as points in a Euclidean space. In this framework, the above function associates to c a set of points that, since are defined to be external to the concept, prevent it from expanding into another function of. We may dually define these points in terms of sentinelling a given concept c from being fully enclosed by another concept within the class.
context_section_description: For a concept class  on a space , a sentry function is a total function  satisfying the following conditions:
  Sentinels are outside the sentineled concept ( for all ).
  Sentinels are inside the invading concept (Having introduced the sets , an invading concept  is such that  and . Denoting  the set of concepts invading c, we must have that if , then ).
   is a minimal set with the above properties (No  exists satisfying (1) and (2) and having the property that  for every ).
  Sentinels are honest guardians. It may be that  but  so that . This however must be a consequence of the fact that all points of  are involved in really sentineling c against other concepts in  and not just in avoiding inclusion of  by . Thus if we remove  remains unchanged (Whenever  and  are such that  and , then the restriction of  to  is a sentry function on this set).
   is the frontier of c upon .
  With reference to the picture on the right,  is a candidate frontier of  against . All points are in the gap between a  and . They  avoid inclusion of  in , provided that these points are not used by the latter for sentineling itself against other concepts. Vice versa we expect that  uses  and  as its own sentinels,  uses   and  and  uses   and  analogously. Point  is not allowed as a  sentry point since, like any diplomatic seat, it should be located outside all other concepts just to ensure that it is not occupied in case of invasion by .
caption: A schematic outlook of outer sentineling functionality
exif: {}