In the paper, we discuss an extension of exploration systems introduced by Andrzej Ehrenfeucht and Grzegorz Rozenberg. The extension is de ned by adding an interpretation of nodes and edges in zoom structure of exploration system. The interpretation is based on the concepts, namely local logic and logic infomorphism, from the notion of information ow by Jon Barwise and Jerry Seligman. This extension makes it possible, in particular, to give a natural interpretation of reaction systems in exploration systems as tools for controlling attention in reasoning about the perceived situation in the physical world.
In the paper, we present a preliminary discussion about possible links between the exploration systems and the information ow approach.
The original motivation behind reaction systems (mostly taken from [
Zoom structures were introduced to integrate structure of a depository of
knowledge of a discipline of science (e.g., biology) in the context of reasoning
about the perceived situation related to reaction systems in the physical world.
A discipline of knowledge must be structured and the integrating structure here
is a well-founded partial order which is well suited to represent a hierarchical
structure of knowledge. Exploration systems combine the zoom structures with
the reaction systems that are \running within" zoom structures (see, e.g., [
We propose to extend exploration systems by adding interpretation of nodes
and edges of zoom structures. The interpretation of nodes of zoom structures,
in the form of labels of nodes, is de ned by local logics (related to information
systems) [
The content of the paper is organized as follows. In Sect. 2 we present the basic concepts of reaction systems. Rudiments of the information ow approach are included in Sect. 3. The zoom structures, exploration systems, and their extension are discussed in Sect. 4.1. 2
In this section we recall some basic notions concerning reaction systems (mostly
taken from [
De nition 1. A reaction is a triplet a = (Ra; Ia; Pa), where Ra; Ia; Pa are nite nonempty sets with Ra \ Ia = ;. If S is a set such that Ra; Ia; Pa S, then a is a reaction in S.
The sets Ra; Ia; Pa, are called the reactant set of a, the inhibitor set of a, and the product set of a, respectively. Clearly, since Ra; Ia are disjoint and nonempty, then if a is a reaction over S, then jSj 2: We will use rac(S) to denote the set of all reactions over S:
The enabling of a (biochemical) reaction in the given state of a biochemical system and the resulting state transformation are de ned as follows.
{ Let a be a reaction. Then a is enabled by T , denoted by ena(T ), if Ra T and Ia \ T = ;. The result of a on T , denoted by resa(T ), is de ned by: resa(T ) = Pa if ena(T ) and resa(T ) = ;, otherwise. { Let A be a nite set of reactions. The result of A on T; denoted by resA(T ), is de ned by: resA(T ) = Sa2A resa(T ).
The intuition behind a nite set T is that of a state of a biochemical system, i.e., a set of biochemical entities present in the current biochemical environment. Thus a single reaction a is enabled by state T if T separates Ra from Ia, i.e., Ra T and Ia \ T = ;: When a is enabled by T , then its result on T is just Pa: For a set A of reactions, its result on T is cumulative, i.e., it is the union of the results of all individual reactions from A. Since reactions which are not enabled by T do not contribute to the result of A on T; resA(T ) can be de ned by resA(T ) = [fresa(T )ja 2 A and ena(T )g:
Now the central notion of a reaction system is de ned as follows. De nition 3. A reaction system is an ordered pair A = (S; A); where S is a nite set such that jSj 2 and A rac(S) is a nonempty set of reactions in S:
Thus a reaction system is basically a nite set of reactions over a set S, which is called the background set of A and its elements are called entities. The result function of A, resA : 2S ! 2S is de ned by resA = resA:
The behaviour of a reaction system (which results from the interactions between its reactions) is determined by its dynamic processes which are formally de ned as follows.
De nition 4. Let A = (S; A) be a reaction system and let n 1 be an integer. An (n-step) interactive process in A is a pair = ( ; ) of nite sequences such that = C0; : : : ; Cn and = D0; : : : ; Dn, where C0; : : : ; Cn; D0; : : : ; Dn S, and Di = resA(Di 1 [ Ci 1) for all i 2 f1; : : : ; ng:
The sequence is the context sequence of and the sequence is the result sequence of : Then, the sequence = W0; W1; : : : ; Wn de ned by Wi = Ci [ Di for all i 2 f0; : : : ; ng is the state sequence of with W0 = C0 called the initial state of (and of ). If Ci Di for all i 2 f1; : : : ; ng, then we say that (and ) is context-independent. Note that we can assume then that Ci = ; for all i 2 f1; : : : ; ng without changing the state sequence.
Thus, an interactive process begins in the initial state W0 = C0 [ D0. The reactions from A enabled by W0 produce the result D1 which together with C1 forms the successor state W1 = C1 [ D1: The iteration of this procedure determines : for each i 2 f0; : : : ; n 1g, the successor of state Wi is Wi+1 = Ci+1 [ Di+1; where Di+1 = resA(Wi):
The context sequence formalizes the intuition that, in general, a reaction system is not a closed system and so its behavior is in uenced by its environment. Note that a context-independent state sequence is determined by its initial state W0 and the number of steps (n). In general, for an n-step interactive process of A; is determined by its context sequence and n:
Also, in a context-independent state sequence = W0; : : : ; Wi; Wi+1; : : : ; Wn,
during the transition from Wi to Wi+1 all entities from Wi resA(Wi)
vanish. This re ects the assumption of no permanency: an entity from a current
state vanishes unless it is produced/sustained by A. Clearly, if is not
contextindependent, then an entity from a current state Wi can be also sustained
(thrown in) by the context (Ci+1). This feature is also a major di erence with
standard models of concurrent systems such as Petri nets (see, e.g., [
In [
De nition 5. A classi cation A = hT ok(A); T yp(A); j=Ai consists of (i) a set, T ok(A), of objects to be classi ed, called tokens of A, (ii) a set, T yp(A), of properties used to classify the tokens, called the types of A, and (iii) a binary relation, j=A, between T ok(A) and T yp(A).
If a j=A , then a is said to be of type in A. That is, j=A basically speci es which
token is of which type. Following the literature of rough sets [7, 8], the notion
of classi cation, presented in [
Now the notion of infomorphism, de ned below, represents relationship between classi cations, and provides a way of moving information back and forth between them.
De nition 6. Let A = hT ok(A); T yp(A); j=Ai and B = hT ok(B); T yp(B); j=Bi be two classi cations. An infomorphism f : A B from A to B is a contravariant pair of functions f = (f^; f ) such that f^ : T yp(A) 7! T yp(B) and f : T ok(B) 7! T ok(A) satisfying the following fundamental property of infomorphisms. f (b) j=A i b j=B f^( ) for each b 2 T ok(B) and 2 T yp(A).
The notion of an interpretation, sometimes also called a translation of one language into another, is an example of infomorphism between classi cations. There are two aspects of an interpretation; one is to do with tokens (structures), and the other is to do with types (sentences). An interpretation I : L1 L2 of languages L1 into L2 does two things. At the level of types, it associates with every sentence of L1, a sentence I( ) of L2, its translation. At the level of tokens, it associates with every structure M for L2, a structure I(M ) for L1. The relation that I(M ) j=L1 i M j=L2 I( ), presents that what I( ) says about the structure M is equivalent to what says about the structure I(M ). L1 – sentences ╞ L1 α I(M)
I(α) M
╞ L2 L1 – structures
L1 – structures
C of f and g is the infomorphism de ned by g^f = g^f^ and gf = f g. B and g : B
Given a classi cation of information, often it is found that some tokens are
identical with respect to some types, and distinct with respect to the rest. The
example, as given in [
mon with that of my next door neighbour. If mine has a picture of President Clinton on page 2, so does hers. If mine has three sections, so does hers. . . . Mine has orange juice spilled on it, hers does not. Hers has the crossword puzzle solved, mine does not.
In the theory of classi cation, this aspect is captured by the following notions of invariant and quotient classi cation.
De nition 8. Given a classi cation A, an invariant is a pair I = ( ; R) consisting of a set T yp(A) of types of A and a binary relation R between tokens of A such that if aRb, then for each 2 , a j=A if and only if b j=A . In the above de nition though R needs not to be an equivalence relation, in the further considerations R is considered to be the smallest equivalence relation containing the concerned relation.
De nition 9. Let I = ( ; R) be an invariant on the classi cation A with respect to an equivalence relation R. The quotient of A by I, denoted as A=I, is the classi cation with types , whose tokens are the R-equivalence classes of tokens of A, and with [a]R j=A=I if and only if a j=A .
One can notice that the notion of invariance, as de ned in [
Example 1. For a given information system A=(U; A; fVaga2A; ffaga2A) and
the indiscernibility relation IN D(A) one can de ne two classi cations Cl(A) =
(U; ; j=A) and Cl(A=IN D(A)) =(U=IN D(A); ; j=A=IND(A)), where is a
subset of T ype(A) (cf. below Def. 5), x j=A denotes that x satis es , and
[x]IND(A) j=A=IND(A) means that x j=A [7, 8]. One can easily check that
these two classi cations can be linked by infomorphisms (id; g) : Cl(A)
Cl(A=IN D(A)), where id is the identity on and g assigns to [x]IND(A) any
object from [x]IND(A) and (id; h) : Cl(A=IN D(A)) Cl(A), where id is the
identity on and h(x) = [x]IND(A) for x 2 U .
2
As pointed out in [
one way to think about information ow in a distributed system is in terms of a `theory' of the system, that is, a set of known laws that describes the system.
Based on this general notion of classi cation, the notion of sequent or notion of consequence of a deductive logic is captured as follows.
As a classi cation, say (T ok(A); T yp(A); j=A), speci es a perspective about the properties of the T ok(A) we may call the classi cation as classi cation of A considering A to refer to that particular perspective.
De nition 10. Let cl(A) = (T ok(A); T yp(A); j=A) be a classi cation of A. (i) For any ; T yp(A), h ; i is considered to be a sequent of T yp(A). (ii) A sequent h ; i is a partition of 0 T yp(A) if [ = 0 and \ = . (iii) A binary relation ` between subsets of T yp(A) is called a (Gentzen) consequence relation. (iv) A theory T = ( ; `) is a pair, where T yp(A) and ` is a consequence relation on . (v) A constraint of the theory T is a sequent h ; i such that ` . (vi) A token a of T ok(A) satis es h ; i provided that if a is of type for every
called a counterexample to the sequent. (vii) The theory T (cl(A)) = (T yp(A); `A) generated by cl(A) is the theory whose constraints are the set of sequents satis ed by every token of T ok(A). (viii) A theory whose constraints are satis ed by every token of the classi cation is called a complete theory.
Here it is to be noted that sequents are all possible pairs of sets of types, and some of them come under the consequence relation. Usually, some natural conditions are imposed on the set of sequents if one would like to consider it as a theory. Below we present such conditions in the de nition of the regular theory. ` If `
If ; 0 ` De nition 11. A theory T = ( ; `) is regular if it satis es the following properties viz., identity, weakening, and global cut for all types , and all set ; 0; ; 0; 0; 0; 1 of types.
, then ; 0 ` ; 0.
; 1 for each partition h 0; 1i of 0, then ` .
Proposition 1. The theory T (cl(A)) = (T yp(A); `A) generated by the classi cation cl(A) of A is a regular theory.
Proposition 2. Any regular theory T = ( ; `) satis es the following condition. Finite cut: If ; ` and ` ; , then ` .
De nition 12. Given two theories T1 = (T yp(T1); `T1 ) and T2 = (T yp(T2); `T2 ), a (regular theory) interpretation f : T1 7! T2 is a function from T yp(T1) to T yp(T2) such that for each ; T yp(T1) if `T1 , then f ( ) `T2 f ( ). The notion of local logic puts the idea of a classi cation together with that of a regular theory. Moreover, introducing a notion of normal tokens it models resonable but unsound inferences.
De nition 13. A local logic L = (T ok(L); T yp(L); j=L; `L; NL) consists of (i) a classi cation cl(L) = (T ok(L); T yp(L); j=L), (ii) a regular theory T h(L) = (T yp(L); `L), and (iii) a subset NL T ok(L), called the normal tokens of L, which satis es all the constraints of T h(L).
pair f = (f^; f ) of functions such that (i) f : cl(L1) cl(L2) is an infomorphism of classi cations, (ii) f^ : T h(L1) 7! T h(L2) is a theory interpretation, and (iii) f (NL2 ) NL1 .
It can be observed that through these notions of classi cation, local logic, and
logic infomorphism the target of the authors [
In this section, we consider exploration systems which combine zoom structures
with reaction systems \running within" zoom structures (see, e.g., [
Formally zoom structures are de ned as follows (we consider irre exive partial orders; recall that a partial order is well-founded if every walk against its edges is nite).
De nition 15. A zoom structure is a 6-tuple Z = (D; E; ; ; fDigi2 ; fEj gj2 ), where (i) D is a non-empty set, (ii) E D D is such that the E+ (i.e., the transitive closure of E) is a well-founded partial order, (iii) ; are nite sets, (iv) fDigi2 is a partition of D (into non-empty sets), and (v) fEj gj2 is a partition of E (into non-empty sets).
Obviously, Z can be also seen as a node- and edge-labelled graph, where D is its set of nodes labelled by elements of , and E is its set of edges labelled by elements of :
Data structures for implementing large sets of data are often hierarchical: in accessing speci c data one usually performs a series of zoom operations each of which leads from a topic to its \subtopic." This is re ected in the basic notion of an inzoom of Z: De nition 16. Let Z = (D; E; ; ; fDigi2 ; fEj gj2 ) be a zoom structure. An inzoom of Z is a nite sequence x = x1; x2; : : : ; xn such that n 2, xi 2 D for i 2 f1; : : : ; ng; and, for each i 2 f2; : : : ; ng; (xi; xi 1) 2 E:
The set of inzooms of Z is denoted by IN ZOOM (Z):
Thus an inzoom represents a \reverse walk" in Z; i.e., a walk through nodes such that each single step goes against an edge of E: In the framework of zoom structures, inzooms (rather than nodes) are basic units for reasoning about and the usage of zoom structures.
While a zoom structure represents the static integrating structure of a depository of knowledge, the dynamic processes of exploring depositories of knowledge are represented by reaction systems \embedded" (rooted) in zoom structures. The embedding of a reaction system in a zoom structure is realized by requiring that the background of the reaction system consists of inzooms of the zoom structure.
De nition 17. Let Z be a zoom structure. A reaction system A = (S; A) is rooted in Z if S IN ZOOM (Z):
Recall that a reaction system A = (S; A) speci es, through the result function resA; a set-theoretical transformation of the set of subsets of its background set S (hence on the states of A). (When one allows processes of A to be more general than context-independent, then more general transformations are considered.) The background set can be any set and if we choose it to be a set of zooms of
This leads to the notion of an exploration system.
Z; then we root A in Z, \ allowing" A to explore (the knowledge deposited in) Z: De nition 18. An exploration system is an ordered pair E = (Z; F ); where Z is an extended zoom structure and F is a family of reaction systems rooted in Z:
In the original de nition (see [
Exploration systems can be used for reasoning about perceived situation in the physical world. Note that objects in D do not have to belong to the ground level of hierarchical modeling obtained by sensory based perception of reality. They can be constructs of higher level of the hierarchical modeling for perception based reasoning about the currently perceived situation. Moreover, edges in E can be interpreted as links representing possible relevant interactions between objects from D. This means that results of interactions can be used in perception based reasoning about the currently perceived situation.
Example 2. Let Z = (D; E; ; ; fDigi2 ; fEjgj2 ) be a zoom structure such that D = fx1; x2; : : : ; x10g, = f1; 2; 3g, = f4; 5; 6g, D1 = fx1; x2; x3g, D2 = fx4; x5; x6; x7g, D3 = fx8; x9; x10g, E = E4 [ E5 [ E6, E4 = f(x5; x7); (x8; x10); (x1; x4); (x3; x5)g, E5 = f(x6; x7); (x4; x7); (x2; x3)g, and E6 = f(x5; x10); (x1; x3); (x1; x2); (x3; x8); (x9; x10)g (see Figure 2). It is illustrated in Figure 2.
Let A = (S; A) be a reaction system rooted in Z such that S = f(x3; x2; x1); (x3; x1); (x3; x2); (x2; x1); (x7; x4); (x10; x8)g and A contains the reaction a = (Ra; Ia; Pa) with Ra = f(x3; x2; x1); (x2; x1)g, Ia = f(x10; x8)g, and Pa = f(x7; x4)g. This gives an example of a reaction system rooted in a zoom structure. 4.1
Exploration Systems Grounded in the Space of Information
Systems
We propose to extend exploration systems by adding interpretation of nodes
and edges of zoom structures. The interpretation of nodes of zoom structures
is given in the form of labels of nodes de ned by local logics (related to
information systems) [
Having such a framework, following the information ow approach [
Instead of this we propose to construct local logics only for some fragments of zoom structures which are relevant for the perceived situation. Namely, we propose to construct local logics corresponding to subnetworks de ned by the D2 2 x6 5
5 2 x4 4 D1 4 partition of nodes given by a zoom structure (representing subdomains of knowledge). It should be noted that the partition blocks can be further restricted by using reactants of relevant reactions from exploration system. In the consequence, the fragments of networks for which it is necessary to construct locals logic representing them is substantially reduced. The aim is to make the reasoning process e cient and leading to conclusions on the perceived situation. The products of reactions from the considered exploration system are used as pointers indicating relevant fragments of zoom structure. These fragments are used in further steps of reasoning on the basis of local logics toward understanding the perceived situation.
There is one more extension we propose to the zoom structure de ned above. This is speci ed by a selection function making it possible to select, from the family of reaction systems given in the considered exploration system, a relevant reaction system, for the next step of reasoning on the basis of the current information on the currently perceived situation. We assume here that this information is represented, in particular, in a distinguished nodes (called sensory nodes) of extended zoom structure, where information systems and corresponding to them local logics are labeling nodes. 5
We presented a preliminary discussion about extension of exploration systems
de ned in [
In our further research, we plan to consider the exploration systems as dynamic complex networks with the structures changing by the control mechanisms responsible for the behavior of exploration systems. The control of an agent, using a given exploration system interacting with the environment, is aiming to satisfy the 'needs' of the agent. It should be noted that the needs may change with time. One may ask how such complex exploration systems may be constructed and modi ed with time. Here, we would like to point to two special strategies following two kinds of judgments used for making changes in the current exploration system. The rst one is based on aggregation of information systems labeling nodes of zoom structures of these exploration systems and consequently the local logics corresponding to them. The aggregations are such as operations of join of information systems with some relevant constraints. These constraints are used to lter Cartesian products of sets of objects in the joint information systems to obtain relevant computational building blocks (granules) for describing the perceived situation, e.g., the ones which are used for approximation of complex vague concepts responsible for triggering action or plans (see, e.g., [9]). The second kind of strategies is based on the ability of agents to create the so called complex granules making it possible to extend the fragments of the physical world, perceived by agents, to the new fragments localized in the scope of these complex granules (see, e.g., [10{12]). More detailed discussion on the issues related to dynamic behavior of exploration systems will be included in our next papers.
The research of Andrzej Skowron was partially co-funded by EU Smart Growth Operational Programme 2014-2020 under GameINN project POIR.01.02.00-000184/17-00. 7. Pawlak, Z., Skowron, A.: Rudiments of rough sets. Information Sciences 177(1) (2007) 3{27 8. Pawlak, Z., Skowron, A.: Rough sets: Some extensions. Information Sciences 177(1) (2007) 28{40 9. Skowron, A., Stepaniuk, J.: Hierarchical modelling in searching for complex patterns: Constrained sums of information systems. Journal of Experimental and Theoretical Arti cial Intelligence 17 (2005) 83{102 10. Jankowski, A.: Interactive Granular Computations in Networks and Systems Engineering: A Practical Perspective. Lecture Notes in Networks and Systems. Springer, Heidelberg (2017) 11. Skowron, A., Jankowski, A.: Interactive computations: Toward risk management in interactive intelligent systems. Natural Computing 15(3) (2016) 465 { 476 12. Skowron, A., Jankowski, A.: Rough sets and interactive granular computing. Fundamenta Informaticae 147 (2016) 371{385