Yi Guo

Xinjun Mao

Fu Hou

Cuiyun Hu

Jianming Zhao

The BDIP Software Architecture and Running Mechanism for Self-Organizing MAS

Keywords: multi-agent system, self-organization, agent architecture 1

As there are huge gaps between the local micro interactions among agents and the global macro emergence of self-organizing system, it is a great challenge to design self-organizing mechanism and develop self-organizing multi-agent system to obtain expected emergence. Policy-based selforganization approach is helpful to deal with the issue, in which policy is the abstraction of self-organizing mechanism and acts as the bridge between the local micro interactions and global macro emergence. This paper focuses on how to develop software agents in policy-based self-organizing multi-agent system and proposes a BDIP architecture of software agent. In our approach, policy is an internal component that encapsulates the self-organizing information and integrates with BDI components. BDIP agent decides its behaviors by complying with the policies and respecting BDI specifications. An implementation model and the running mechanism as well as corresponding decision algorithms for BDIP agents are studied. A case of self-organizing system is studied to illustrate our proposed approach and show its effectiveness.

Introduction

Self-organization refers to a process where a system changes its internal structure without explicit external and central control. It often results in emergent behavior in the global system [START_REF] Giovanna | Self-Organizsation in MAS[END_REF].With the pervasiveness of distributed information systems, selforganizing systems become more and more attractive to researchers from different application areas [START_REF] Mamei | Case Studies for Self-Organization in Computer Science[END_REF]. Agent technology is considered as an appropriate and powerful paradigm to develop large-scale complex systems applications. As a kind of such complex systems, self-organizing systems are usually engineered with agent metaphor, which views the whole system as MAS (Multi-Agent Systems) and using software agents as basic components to construct the systems [START_REF] Guo | A Survey of Engineering for Self-Organization Systems[END_REF].

However, developing self-organizing MAS in an iterative and effective way is still a great challenge in the literature of software engineering [START_REF] Parunak | Software Engineering for Self-Organizing Systems[END_REF]. The obstacle is how to obtain desirable global system characteristic through the local interactions among agents. In self-organizing MAS, there is an absence of centralized control node in the system and the agents only interact with their local environment. This leaves a significant gap between the local interaction and global system characteristic, and brings obstacles which are put in evidence during the development of the systems. To obtain the desirable global characteristic, the developer therefore must adjust the behaviors of agents iteratively. However, self-organizing MAS often consist of large numbers of agents and are deployed in complex environment. Designing and deploying such systems in an iterative way is difficult. How to effectively support the development of such systems is still an open issue [START_REF] Parunak | Software Engineering for Self-Organizing Systems[END_REF].

Against the background, we have proposed a policy-based self-organization approach in our previous work [START_REF] Guo | Design Pattern for Self-Organization Multi-agent Systems based on Policy[END_REF] which affects the emergences of multi-agent systems by restricting or guiding agents' behaviors in terms of policy. In order to support the development of the PSOMAS (Policy-based Self-Organizing Multi-Agent Systems), this paper proposes a BDIP software architecture in which policies are viewed as component of the agent. Based on the architecture, an implementation model and running mechanisms as well as agent behavior decision algorithms are also provided. The rest of this paper is organized as follows: Section 2 gives a brief introduction of policy-based self-organizing MAS. Section 3 proposes the agent architecture, policy representation, and running mechanism of the software agents. Section 4 discusses the policy-based agent decision algorithms and a case study is illustrated in section 5. Section 6 discusses the related works as well as conclusions and future works are discussed in section 7.

Policy based Approach to Self-Organizing Multi-agent Systems

To intuitively understand the challenges in self-organizing MAS, we firstly introduce an example of a group of self-organizing robots whose aims are to explore and carry ore in a strange environment. Each robot provides functions to randomly walk in the environment to find ore resource, and carry ore back to the base. Furthermore, each robot can broadcast its position to other robots. The system searches and takes ore by using the self-organization of these robots. When the users search for ore depending on these robots in strange environments, they perhaps need to cope with different circumstances, such as various landforms and ore distributing and etc. However, it is impossible that the fixed behaviors of robots can satisfy all scenarios. On the other hand, it is not always feasible that the users redesign and redeploy the robots after they have acquired the new requirements, for example the robots are exploring on the mars. Then we need a new approach to effectively change the behaviors of agent during runtime to meet the variety environment and requirements. In human society, policies are often used to restrict and guide the behaviors of people. With these policies, human society often presents a self-organizing process and results in different emergent phenomena. For example, the economic policies often result in the changes of macro economic index, which is owing to the people's economic behaviors like stock transaction are affected by such policies. In the literature of self-organizing MAS, in order to facilitate the solving of the issues discussed above, the policies in human society can be used for self-organizing MAS. By this approach, policies give a presentation of the behaviors of agents and the agents must to comply with them at runtime. On one hand, developers need to design the policies as well as the agents in the design phase of such systems. On the other hand, the behaviors of agents are affected by these policies at runtime, and developers can evaluate the system's macro characteristics whether satisfies the requirements or not. If it does not satisfy the requirements, developers can change the policies, which can cause changes of the agents' behaviors and result in the changes of the self-organizing process of the whole system.

3

BDIP Architecture and Running Mechanism

BDIP Architecture of Software Agent

The BDI architecture of software agents had been accepted for a long time both in academe and industry. The architecture has three components: Belief, Desire, and Intention. Belief means the cognitions of an agent about its environment and internal state. Desire means the goals that an agent wants to pursue, and Intention means the commitment plans of the agent which is useful for the accomplishment of the goals in Desire [START_REF] Rao | Modeling Rational Agents within a BDI-Architecture[END_REF]. We consider that the BDI architecture is useful for analyzing the autonomous behaviors of rational agents and easier to accept the policy as a new decision component than other architectures (e.g. reactive architecture). This paper proposes a BDIP (Belief, Desire, Intention and Policy) agent architecture by extending the BDI architecture (see Fig. 1).

Fig. 1. BDIP architecture of Agent

In PSOMAS, the environment of a BDIP agent consists of policies and other agents [START_REF] Guo | Design Pattern for Self-Organization Multi-agent Systems based on Policy[END_REF], and the BDIP agent can perceive the policies from its local environment. The perceived policies are deposited in the Policy component, and are triggered by the policy conditions (introduced in section 3.2) which are specified in the Belief component. Policies can affect both Desire component and Intention component. For the Desire component, a new goal will be created by the policy or some of goals are prohibited. For the Intention component, the execution of committed plan will be guided by the policy, for example some actions are forbidden to be executed and some actions are preferential (corresponding algorithms will be introduced in section 4). The relationship among Belief, Desire and Intention is same as [START_REF] Rao | Modeling Rational Agents within a BDI-Architecture[END_REF].

Representation and Realization of Policy

Policies can be viewed as a set of rules which restrict the behaviors or states of the agents in the system. This paper distinguishes two kinds of policies: Obligation and Prohibition. The Obligation represents the action that an agent need to perform or the state the agent need to keep as well as the Prohibition represents the action that an agent must not to perform or the state not to appear. On the other hand, a policy consists of the conditions to be satisfied and the action (state) to be performed (kept) by agents. Formally, it can be described by EBNF as follows:

Policy:= Obligation (IF Self-condition WHEN Env-event DO (Action|State))
| Prohibition(IF Self-condition WHEN Env-event DO (Action|State)) Self-condition specifies the internal state of an agent to be satisfied and Env-event represents the happened event of the environment of the agent. "Obligation(IF Selfcondition WHEN Env-event DO (Action|State)" means that when the Self-condition of the agent is satisfied and Env-event is happening in the environment, the agent need to perform the Action or keep the State, Prohibition means the opposite semantics. The Self-condition and Env-event can be viewed as policy-condition.

A policy at the run-time can be in four states: Deployed, Deactived, Executed, or Deleted. The initial state of a newly deployed policy is Deployed, what means that the policy exists in the system but is not yet perceived by any agents. More interesting is the policy inside an agent can has three states. Deactive means either the policy conditions are not satisfied or the behaviors of the agent are complying with the policy i.e. the agent does not need to adjust its Desire or Intention component. When the policy conditions are satisfied, the policy is transited to Executed. During this state, agent will adjust the Desire and (or) Intention component according to the policy. If there are some goals or plans prohibited by the policies, the goals and plans will be suppressed and saved. If a user deletes a policy from the system, the agents will be informed by the system. Before the policy is deleted from Policy component, the policy needs to be transited to the Deleted state in which the agent will check the Desire and Intention components whether there are goals or plans are suppressed by this policy and resume them respectively if existing. Moreover, the event in the environment of an agent may also add actions to the agenda, e.g. messages that have been received from other agents and messages need to be processed (External effects). When the policy conditions of a policy are satisfied, CE will add the Tig-gerPolicy on the agenda, the policy will be transited from Deactived" to Executed state. Moreover AE will add ExecutePolicy on the agenda after TiggerPolicy executed, and the D and I components will be adjusted by PD after ExecutePolicy executed. In the adjusting process, perhaps the actions on the agenda also be regulated by PD (agenda regulation), for example add new actions, delete action, and adjust the sequence of the actions. On the other hand, when a user changes the policies in the system, CE will acquire this message and add PerceivePolicy or DropPolicy on the agenda.

Implementation Model and Running Mechanism of BDIP Software Agent

Behavior Decision Algorithms of BDIP Agent

In the agent behaviors adjusting process, PD use different algorithms to cope with the different policy type. Table 1 shows the different algorithms for different policy type, the italic are the names of algorithms and "Null" means the regulation of this component is needless. The details of these algorithms are listed in Table 2. Moreover we consider the goal in D component as discussed in [START_REF] Pokahr | A Flexible BDI Architecture Supporting Extensibility[END_REF] is consists of different states at runtime: "Active" state means the goal is currently pursued by agent. "Suspended" state and "Options" state represent the goal is inactive. Therefore regulation of D component is the transition between goal states. In the algorithm Obligation_State_for_Goal, the goal(state) means to make the obligation state as a goal. PD searches this goal in D component, and upgrades the prior-ity of this goal as soon as the goal is found. If the goal dose not exist in D component, PD will create this goal in D. Achieve goal(state) means to pursuer this goal right now. In the Algorithm Obligation_Actiion_for_Plan PD creates a plan which obtains the execution of the obligated action and adds corresponding actions on the agenda. The plan will be deleted as soon as its execution finished. When a certain state of an agent is prohibited by a Prohibition policy, PD will search this state both in D and in I component. In the algorithm Prohibition_State_for_Goal, the state will be treated as a goal. PD will suppress this goal and add DeliberateNewOption which is used for selecting of another goal to pursue if the goal is "Active" state (line 1-4). When the prohibited goal is being "Suspended" or "Option" state, PD will suppress it and executes UpdateGoal by updating the D component. Algorithm Prohibi-tion_State_for_Planl is designed to search the prohibited state in I component. When the prohibited action belonging to the executing plan, PD will suppress this plan and add ScheduleCondidates on the agenda to select another plan. If the state can be achieved by the "Suspended" or "Options" plans, PD will suppress the plan and update I component. If the user prohibits a certain action to be executed in terms of Prohibition policy, PD will search this action on agenda and in I component. When the action is on the agenda, PD will suppress it and call another plan on the agenda (line 1-4). If the action is not executing currently but is contained in some plans in I component, PD will suppresses these plans and update the I component (line 5-7).

Case Study

In this section, we will analyze the case that we introduced in section 2. In this case, the actions of robots should be designed in the design phases. These actions include: random searching, taking ore, sending message, responding message etc. On the other hand, we assume that there are two scenarios need to be considered. The first scenario is that there is only one ore source in the environment. To find resource and carry ore more quickly, it is appropriate to make each robot performs behaviors as follows: 1) randomly works in the environment to find ore resource; 2) carries ore back to base if finds the ore resource; 3) broadcasts position of ore resource if finds it; 4) goes to the position and carries ore to base if having received position information from other robot. To realize these behaviors, the user can deploy the policies as follows:

Obligation( IF Searching WHEN Others_Send_Message DO TakeOreFromReceived- Position) Obligation( IF Find_Ore_at_Some_Position WHEN $ DO Broadcast(Position))
In the second scenario, robots will be deployed in an environment which has more than one ore resource. Moreover, the user needs all robots to carry the found ore from near to far. According to this requirement, robots should firstly collect some ore resource positions whatever the position is found by itself or received from others. Then select the nearest one from the base to carry ore. To realize this requirement, user should add some new policies: We have implemented the BDIP robots in a simulation way by using the Jadex platform [START_REF] Braubach | Jadex: A BDI Agent System Combining Middleware and Reasoning[END_REF]. The basic actions of agents are implemented as Plan of the agent. Some important information such as ore resource positions are implemented as Belief, the interaction among agents this case is implemented as the message events of the agent. The Intention of the robots are to find the ore resource and carry ore back to base. On the other hand, the policy conditions are implanted as either a part of belief (e.g. ore resource) or implemented as the message events. When the system is running, if the policy conditions are satisfied, the agent will perform its behaviors comply with these policies, the trigger condition of the plans are implemented same as the policy conditions. Fig. 3 shows the running snap shot of the case. The gray transparent pane is the base. The number below the base is the amount of ore in the base which has been carried by robots. The yellow transparent cycle of a robot presents the scope that the robot can explore for ore. The red points in environment mean the ore resources which have not been found by robots. The gray points mean the ore resource which has been found by robots and the number below the gray points mean the remained reserves of the ore resource. Fig. 3(a) shows the first scenario in which only one ore resource in the environment. From the figure we can see all robots are carrying ore from this resource when one of them has found it. Fig. 3 (b) shows the second scenario which has many ore resources in the environment. In Fig. 3(b), the robots have collected enough positions of the ore resources and carry the ore from the resource which is the nearest to the base among the collected positions.

Related Works

Recently, many research efforts have been made on the agent modeling based on norms and policies. However majority of them are engaged in the design of normbased MAS organization, which propose norms to have an effective influence on agent and agent role, for example organization regimentation [START_REF] Criado | Thomas: An Agent Platform for Supporting Normative Multi-agent Systems[END_REF] and enforcement mechanisms [13][14]. In the agent architecture aspect, the main contributions of norm acceptance of agents are focus on the theory of BDI agent, e.g. [3][9]. These works focus on the theory frameworks e.g. logical expressions to explain how to represent the norms or policies in the agent and how to influence the reasoning process of the agent. The implement of architecture and running mechanisms of BDI or norm-based BDI agent are relatively few. [START_REF] Castelfranchi | Deliberative Normative Agents: Principles and Architecture[END_REF] proposes a multi-level agent architecture, in which norms can communicated, adopted and used as meta-goals. [START_REF] Pokahr | A Flexible BDI Architecture Supporting Extensibility[END_REF] proposes a BDI Interpreter architecture for the running mechanisms of BDI agent, which our work can be seen as an extension of it.

Conclusion and Future works

In the development of self-organizing MAS, the great challenge is how to bridge the huge gap between the agent local interaction behaviors and the system macro emergence characteristics. Against this open issue, this paper proposes a BDIP architecture of software agent. In the BDIP architecture, agent can perceive the policies of the system and adjusts its behaviors according to policies. A flexible running mechanism is also proposed based on the architecture, which executing meta-operations from a dynamic agenda structure. The architecture and its running mechanism are flexible enough to support the adjustments of system policies so that the users could control the self-organizing process and result by changed policies in the system. Moreover, the details of policy-based decision algorithms of agents are designed, and a case study of policy-based self-organizing robot system is implemented in a simulation way with the Jadex platform. Through the case study we can see that the changes of policies of the system can alter the self-organizing emergence result, and users can satisfy different system requirements by adjusting the policies.

In future works we still focus on the development of the policy-based selforganizing multi-agent systems. A PSOMAS developing environment named PSOMASDE is in our current works. The developing environment include agent design platform and running environment, as well as the policies can be represented by the XML files that can be loaded by the system. Besides the implementation of such systems, the development methodology is also in consideration, which is based our previous work named ODAM [START_REF] Mao | An Organization-based Approach to Developing Self-Adaptive Multi-Agent Systems[END_REF].

Fig. 2

 2 Fig. 2 depicts the running mechanism of BDIP agents. B, D, I and P represent Belief set, Goal set, Plan set and the Policy set of the agent respectively. Agenda can be seen as a queue of actions. All executions of plans and other actions must on the agenda.

Fig. 2 .

 2 Fig. 2. Implementation Model and Running Mechanism of BDIP Agent

Obligation

  (IF Searching WHEN Others_Send_Message DO storage_message) Obligation (IF Message_number=MAX WHEN $ DO TakeOre_Nearest) Prohibition (IF Message_number <MAX]WHEN $ DO RespondMessage)

Fig. 3 .

 3 Fig. 3. Running snapshot of the Case

Table 1 .

 1 Behavior decision Algorithm for Different Policies Type

	Policy Type	Object	Algorithm for Intention	Algorithm for Desire
	Obligation	State Action	Null Obligation_Action_for_Plan	Obligation_State_for_Goal Null
	Prohibition	State Action	Prohibition_State_for_Plan Prohibition_Action_for_Plan	Prohibition_State_for_Goal Null

Table 2 .

 2 Behavior Decision Algorithms

	Name: Obligation_State_for_Goal
	Input: Obligated action; goal of Desire	08 if(goal(state) is Suspended) {
	Output: goal	09 waitfor (satisfyCondition);
	01 if (goal(state) is active) {	10 Achieve goal(state);
	02 Rise goal(state) Priority in Agenda;	11 }else {
	03 } else	12 Add action CreatGoal in Agenda;
	04 if(goal(state) is Option){	13 Achieve goal(state);
	05 Add action SuppressContents in Agenda;	14 Add action DropGoal in Agenda;}
	06 Acheve goal(state);
	07 } else
	Name: Prohibition_State_for_Goal	Name: Prohibition_State_for_Plan
	Input: Prohibited state; goal of Desire	Input: Obligated state; plan of Intention
	Output: goal	Output: plan
	01 if (goal(state)is one of achieving goals) {	01 if (goal(state) is executing Plan) {

Acknowledgement

The research acknowledges financial support from Natural Science Foundation of China under granted No 61070034, Program for New Century Excellent Talents in University, and Opening Fund of Top Key Discipline of Computer Software and Theory in Zhejiang Provincial Colleges at Zhejiang Normal University.


Zhuxiao Wang

Hui Peng
email: penghui@bisu.edu.cn

Jing Guo

Ying Zhang
email: yingzhang@ncepu.edu.cn

Kehe Wu

Huan Xu
email: xuhuan@ncepu.edu.cn

Xiao- Feng Wang
email: wangzx@ncepu.edu.cn

An Architecture Description Language Based on Dynamic Description Logics

Keywords: Architecture Description Languages, Knowledge Representation and Reasoning, Software Architecture, Dynamic Description Logics, Dynamic Adaptation 1

ADML is an architectural description language based on Dynamic Description Logic for defining and simulating the behavior of system architecture. ADML is being developed as a new formal language and/or conceptual model for representing the architectures of concurrent and distributed systems, both hardware and software. ADML embraces dynamic change as a fundamental consideration, supports a broad class of adaptive changes at the architectural level, and offers a uniform way to represent and reason about both static and dynamic aspects of systems. Because the ADML is based on the Dynamic Description Logic DDL(SHON (D)), which can represent both dynamic semantics and static semantics under a unified logical framework, architectural ontology entailment for the ADML languages can be reduced to knowledge base satisfiability in DDL(SHON (D)), and dynamic description logic algorithms and implementations can be used to provide reasoning services for ADML. In this article, we present the syntax of ADML, explain its underlying semantics using the Dynamic Description Logic DDL(SHON (D)), and describe the core architecture description features of ADML.

Introduction

ADML is a promising Architecture Description Language (ADL) towards a full realization of the representing and reasoning about both static and dynamic aspects of concurrent and distributed systems. Concurrent and distributed systems, both hard-ware and software, can be understood as a world that changes over time. Entities that act in the world (which can be anything from a monitor to some computer program) can affect how the world is perceived by themselves or other entities at some specific moment. At each point in time, the world is in one particular state that determines how the world is perceived by the entities acting therein. We need to consider some language (like the Architecture Dynamic Modeling Language, ADML) for describing the properties of the world in a state. By means of well-defined change operations named transition rules in ADML, transition rules can affect the world and modify its current state. Such transition rules denote state transitions in all possible states of the world.

In this paper we describe the main features of ADML, its rationale, and technical innovations. ADML is based on the idea of representing an architecture as a dynamic structure and supporting a broad class of adaptive changes at the architectural level. However, simultaneously changing components, connectors, and topology in a reliable manner requires distinctive mechanisms and architectural formalisms. Many architecture description languages [START_REF] Dashofy | A comprehensive approach for the development of modular software architecture description languages[END_REF][START_REF] Azevedo | The ArchC architecture description language and tools[END_REF][START_REF] Mishra | Architecture description languages for programmable embedded systems[END_REF][START_REF] Perez | Designing software architectures with an aspectoriented architecture description language[END_REF] are dynamic to some limited degree but few embrace dynamic change as a fundamental consideration. ADML is being developed as a way of representing dynamic architectures by expressing the possible change operations in terms of the ADML constructors.

ADML can be viewed as syntactic variants of dynamic description logic. In particular, the formal semantics and reasoning in ADML use the DDL(SHON (D)) dynamic description logic, extensions of description logics (DLs) [START_REF] Baader | The description logic handbook: theory, implementation, and applications[END_REF] with a dynamic dimension [START_REF] Shi | A logical foundation for the semantic web[END_REF][START_REF] Artale | A temporal description logic for reasoning about actions and plans[END_REF][START_REF] Baader | Integrating description logics and action formalisms: First results[END_REF][START_REF] Chang | A Family of Dynamic Description Logics for Representing and Reasoning About Action[END_REF]. So the main reasoning problem in ADML can be reduced to knowledge base (KB) satisfiability in the DDL(SHON (D)). This is a significant result from both a theoretical and a practical perspective: it demonstrates that computing architectural ontology entailment in ADML has the same complexity as computing knowledge base satisfiability in DDL(SHON (D)), and that dynamic description logic algorithms and implementations can be used to provide reasoning services for ADML.

In the following sections, we firstly present an overview of the capabilities of ADML in Section 2. It covers the basic language features and includes a few small examples. Furthermore, we demonstrate the descriptions of transition rules can be formalized as actions in the DDL(SHON (D)). In Section 3, we summarize basic ADML syntax with an overview of ADML semantics. We show that the main reasoning problem in ADML can be reduced to knowledge base (KB) satisfiability in the DDL(SHON (D)) dynamic description logic. Finally, we summarize the paper in Section 4.

An Overview of Adml

ADML is intended as a new formal language and/or conceptual model for describing the architecture of a system. ADML is built on a core ontology of six types of entities for architectural representation: components, connectors, systems, ports, roles, and behaviors. These are illustrated in Figure 1 and Table 1. Of the six types, the most basic elements of architectural description are components, connectors, systems, and behaviors. It's important to recognize that ADML is based on the idea of representing an architecture as a dynamic structure. In other words, ADML may also be used as a way of representing reconfigurable architectures by expressing the possible reconfigurations in terms of the ADML structures (like behaviors). For example, an architectural model might include behaviors that describe components that may be added at run-time and how to attach them to the current system.

ADML design element types

As a simple illustrative example, Figure 1 shows the architectural model of a secure wireless remote-access infrastructure, which is represented as a graph of interacting components. Nodes in the graph are termed components, which represent the primary computational elements and data stores of the system. Typical examples of components include such things as terminals, gateways, filters, objects, blackboards, databases, and user interfaces. Arcs are termed connectors, and represent communication glue that captures the nature of an interaction between components. Examples of connectors include simple forms of interaction, such as data flow channel (e.g., a Pipe), a synchronous procedure call, and a particular protocol (like HTTP). Table 1 contains an ADML description of the architecture of Figure 1. In the software architecture illustrated in Table 1, the secure access gateway (SAG), and the wireless terminal are components. The component exposes its functionality through its ports, which represents a point of contact between the component and its environment. The wireless terminal component is declared to have a single send-request port, and the SAG has a single receive-request port. The connector includes the network connections between the wireless terminal and the SAG. A connector includes a set of interfaces in the form of roles, which may be seen as an interface to a communication channel.

The rpc connector has two roles designated caller and callee. The topology of this system is defined by listing a set of attachments, each of which represents an interaction between a port and some role of a connector.

Components

A component provides an abstract definition of externally visible behavior-i.e., the behavior that is visible to, and may be observed by, a system containing the component. A component defines 1) the ports which may be used to represent what is traditionally thought of as an interface: a set of operations available on a component.

2) its states and state transitions. The syntax structure of components is outlined in Figure 2. Many features are omitted from this overview.

A component declares sets of port constituents. Those port constituents are visible to the system. Other components of the system can be wired up (by connectors) to those port constituents. Thus communication between components is defined by the ports.

A component must provide the objects and functions named in the port constituents. Thus, for example, other components can be connected to call its provided A component specifies the types of events it can observe and generate by declaring, respectively, in and out ports. Connectors in the system can call the in ports of a component, thus generating in events which the component can observe; conversely, the component can call its out ports, thereby generating events which the system can observe. Thus connectors define asynchronous communication between components.

A component optionally contains a behavior which consists of a set of objects, functions, and transition rules. The set of objects, functions is described as ADML facts (see Section 3). Facts declared in a component model state. Transition rules model how the component react to patterns of observed events by changing its states and generating events. The behavior of a component in a system is constrained to be consistent with the component's behavior.

A component observes in events from the system. It reacts by executing its transition rules and generating out events which are sent to other components. A component observes calls to its provides functions; the component must declare functions in its behavior that are executed in response to these calls. When a component calls its requires functions it depends upon the system to connect those calls to provides functions in other components.

Transition rules

One of the key ingredients of the behaviors in a component is a set of transition rules that model how the component react to patterns of observed events by changing their states and generating events. A state transition rule has two parts, a trigger and a body. A trigger is an event pattern (a finite set of facts). A body is an optional set of state assignments followed by a restricted pattern which describes a finite set of facts. In our description frameworks for transition rules, functional descriptions are essentially the state-based and use at least pre-state and post-state constraints to characterize intended executions of a transition rule. On the basis of the above consideration, we give some formal definitions related to transition rules: Definition. 1(Atomic transition rules) An atomic transition rule is a tuple Transition(t)= Transition(<trigger, transition_body>)= Transition(<Pre, Effects>), where Pre is a finite set of facts specifying the preconditions for the execution of t; and Effects is a finite set of facts holding in the newly-reached world by the transition rule's execution. A function body is treated as if it was a transition rule that is triggered by a function call; function calls are treated as events.

A close observation on the state transition rule reveals some resemblance between transition rules and DDL(SHON (D)) actions. As mentioned in [START_REF] Chang | A Family of Dynamic Description Logics for Representing and Reasoning About Action[END_REF][START_REF] Wang | Failure Diagnosis of Internetware Systems Using Dynamic Description Logic[END_REF][START_REF] Wang | An architecture dynamic modeling language for self-healing systems[END_REF][START_REF] Wang | Multi-agent based bioinformatics integration using distributed dynamic description logics[END_REF], the formulas in both Pre and Effects are conferred with well-defined semantics encoded in some TBox, which specifies the domain constraints in consideration.

The execution semantics of transition rules are as follows. If any of the preconditions of the transition rules are satisfied, the process of arbitrarily choosing one of the transition rules, executing its rule body is repeated until none of the preconditions are satisfied.

Executing a rule body consists of changing the state of the behavior part (by calling operations of facts declared there), generating new events defined by the instance of the restricted pattern, and adding the new events to the execution of the system.

Composite transition rules are constructed from atomic transition rules with the help of classic constructors in ADML. Both atomic and composite transition rules are transition rules:

Definition. 2(Transition rules) Transition rules are built up with the following rule: t i , t j ::= Transition(t) | Transition(t i test) | choiceOf(t i t j ) | sequenceOf(t i t j ) | Transition(t i iteration), where t is an atomic transition rule; t i , t j denote transition rules.

We name sequenceOf(t i t j ), choiceOf(t i t j ), Transition(t i iteration) and Transition(t i test) as sequence, choice, iteration and test transition rules, respctively.

Remark: Note that test Transition(t i test) is used to check the executability of the transition rules, which can be reduced to the satifiablity-checking of preconditions of the component transition rules. Test transition rules' execution effects no changes to the world.

ADML is a promising Architecture Description Language (ADL) towards a full realization of the representing and reasoning about both static knowledge and dynamic knowledge in concurrent and distributed systems. In addition to the features inherited from SHON (D), i.e., expressive power in static knowledge representation and decidability in reasoning, DDL(SHON (D)) still employs actions to capture functionalities of transition rules. Hence it is intuitive to model transition rules by actions in DDL(SHON (D)). As demonstrated in this section, the functionalities of transition rules can be semantically transformed into actions in DDL(SHON (D)) by a proper domain ontology (TBox). As a result, all kinds of reasoning tasks concerning the functionalities of transition rules thus can be reduced to the reasoning about actions in DDL(SHON (D)).

Adml as the DDL(SHON (D)) Dynamic Description Logic

ADML is very close to the DDL(SHON (D)) Dynamic Description Logic which is itself an extension of the SHON (D) Description Logic [START_REF] Baader | The description logic handbook: theory, implementation, and applications[END_REF] (extended with a dynamic dimension [START_REF] Shi | A logical foundation for the semantic web[END_REF][START_REF] Chang | A Family of Dynamic Description Logics for Representing and Reasoning About Action[END_REF]). ADML can form descriptions of components, connectors, and systems using some constructs. Given the limited space available, in this article I will not delve into the details of the ADML syntax. ADML axioms, facts, and transition rules are summarized in Table 2 below. In this table the first column gives the ADML syntax for the construction, while the second column gives the DDL(SHON (D)) Dynamic Description Logic syntax.

Because ADML includes datatypes, the semantics for ADML is very similar to that of Dynamic Description Logics that also incorporate datatypes, in particular DDL(SHON (D)).

The specific meaning given to ADML is shown in the third column of Table 2. A DDL(X) model is a tuple M = (W, T, ∆, I), where, W is a set of states; T : N A →2 W×W is a function mapping action names into binary relations on W; Δ is a non-empty domain;

I is a function which associates with each state w ∈ W a description logic interpretation I(w) =< ∆, • I(w) >, where the mapping • I(w) assigns each concept to a subset of ∆, each role to a subset of ∆×∆, and each individual to an element of ∆.

What makes ADML an architecture description language for concurrent and distributed systems, is not only its semantics, which are quite standard for a dynamic description logic, but also the use of transition rules for changes at the architectural level, the use of datatypes for data values, and the ability to use that dynamic description logic algorithms and implementations to provide reasoning services for ADML.

... C n ) A ⊑ C 1 ⊓... ⊓C n A I ⊆ C 1 I ∩... ∩ C n I Element( A complete C 1 ... C n ) A = C 1 ⊓... ⊓C n A I = C 1 I ∩... ∩ C n I SubElementOf (C 1 C 2 ) C 1 ⊑ C 2 C 1 I ⊆ C 2 I EquivalentElements (C 1 ... C n ) C 1 = ... = C n C 1 I = ... = C n I DisjointElements (C 1 ... C n ) C i ⊓ C j = ⊥, i ≠ j C i I ∩ C j I = φ, i ≠ j Datatype(D) D I ⊆ ∆ D Datatype Properties (U)
DatatypeProperty( U super(U 1 ) ...

super(U n )) U ⊑ U i U I ⊆ U i I DatatypeProperty(U do- main(C 1 ) ... domain(C m )) ≥ 1 U ⊑ C i U I ⊆ C i I ×∆ D DatatypeProperty(U range(D 1 ) ... range(D l )) ┬ ⊑ ∀ U.D i U I ⊆ ∆×D i I DatatypeProperty(U Functional) ┬ ⊑ ≤1U U I is functional SubPropertyOf(U 1 U 2 ) U 1 ⊑ U 2 U 1 I ⊆ U 2 I EquivalentProperties(U 1 ... U n ) U 1 = ... = U n U 1 I = ... = U n I Object Properties
ObjectProperty( R super(R 1 ) ...

super(R n )) R ⊑ R i R I ⊆ R i I ObjectProperty(R domain(C 1 ) ... domain(C m )) ≥ 1 R ⊑ C i R I ⊆ C i I ×∆ ObjectProperty(R range(C 1 ) ... range(C l )) ┬ ⊑ ∀ R.C i R I ⊆ ∆×C i I ObjectProperty(R Functional) ┬ ⊑ ≤1R R I is functional ObjectProperty(R Transitive) Tr(R) R I = (R I ) + SubPropertyOf(R 1 R 2 ) R 1 ⊑ R 2 R 1 I ⊆ R 2 I EquivalentProperties(R 1 ... R n ) R 1 = ... = R n R 1 I = ... = R n I Annotation AnnotationProperty(S) Facts Individual( o type(C 1 ) ... type(C n )) o ∈ C i o I ∈ C i I Individual( o value(R 1 o 1 ) ... value(R n o n )) <o, o i > ∈ R i < o I , o i I > ∈ R i I Individual( o value(U 1 v 1 ) ... value(U n v n )) <o, v i >∈ U i < o I , v i I > ∈ U i I SameIndividual(o 1 ... o n ) o 1 = ... =o n o 1 I = ... =o n I DifferentIndividual(o 1 ... o n ) o i ≠ o j , i ≠ j o i I ≠ o j I , i ≠ j negationOf (
= (R I(w) ∪ {(u I , v I ) | R(u, v)∈E }) \ {(u I , v I ) | ¬R(u, v)∈E}. } Transition (ϕ test) ϕ? {(w, w) | w ∈ W and (M,w)⊨ϕ} choiceOf (π π' ...) π⋃π' T(π)∪ T(π') sequenceOf (π π' ...) π ; π' { (w, w

Summary and Outlook

In this paper we presented ADML a new formal language and/or conceptual model for representing system architectures. We described the main features of ADML, its rationale, and technical innovations. By embracing transition rules into ADML, ADML combine the static knowledge provided by the system requirements with the dynamic descriptions of the computations provided by transition rules, and support the representing and reasoning about both static knowledge and dynamic knowledge in concurrent and distributed systems. ADML can be viewed as syntactic variants of dynamic description logic DDL(SHON (D)). The functionalities of the transition rules are abstracted by actions in DDL(SHON (D)), while the domain constraints, states, and the overall system objectives are encoded in TBoxes, ABoxes and DL-formulas, respectively. So the main reasoning problem in ADML can be reduced to knowledge base (KB) satisfiability in the DDL(SHON (D)) dynamic description logic. Afterwards, dynamic description logic algorithms and implementations can be used to provide reasoning services for ADML. ADML has evolved from several sources:1) Rapide [START_REF] Luckham | An Event-Based Architecture Definition Language[END_REF] (a concurrent event-based simulation language for defining and simulating the behavior of system architectures.), 2) Acme [START_REF] Garlan | Acme: an architecture description interchange language[END_REF] (a common representation for software architectures), 3) DDL [START_REF] Shi | A logical foundation for the semantic web[END_REF][9] (for event patterns and formal constraints on concurrent behavior expressed in terms of description logics). While ADML is still too new to tell whether it will succeed as a community-wide tool for architectural development, we believe it is important to expose its language design and philosophy to the broader software engineering community at this stage for feedback and critical discussion.

In the future, we plan to investigate how we can leverage Distributed Dynamic Description Logics (D3Ls) to support a larger variety of heterogeneous systems with our approach. Another issue for future work is the design of "practical" algorithms for DDL(SHON (D)) reasoning.

Fig. 1 .

 1 Fig. 1. Elements of an ADML Description

Fig. 2 .

 2 Fig. 2. Outline of component syntax

  Port name '= {' {property_declaration;} {representation_declaration;} '}' declaration_list : := ADML facts -see Section 3 state_transition_rule : := Transition '(< ' trigger ', ' transition_body '>) ' '; ; ' trigger ::= pattern -see Section 2.3 pattern ::= ADML axioms-see Section 3 transition_body : := {state assignment} [ restricted_pattern ]

  ϕ) ¬ϕ (M,w)⊭ϕ disjunctionOf (ϕ ϕ' ...) ϕ∨ϕ' (M,w) ⊨ϕ or (M,w) ⊨ψ diamondAssertion(π ϕ) <π>ϕ ∃w'∈W.((w, w')∈T(π) and (M,w') ⊨ϕ ) Transition rules Transition(α ) α T(α)= T(P, E)={ (w, w') | (M,w)⊨ P, (M,w)⊨ ¬ϕ for every ϕ∈E, (M,w')⊨ E, C I(w') = (C I(w) ∪ {u I | C(u)∈E}) \ {u I | ¬C(u)∈E}, and R I(w')

  ') | ∃w''.(w, w'')∈T(π) and (w'', w')∈ T(π') } Transition (π iteration) π * reflexive and transitive closure of T(π)

Table 1 .

 1 The architectural model in ADML

	Element Axioms	Property Axioms	Facts
	Element(System com-	ObjectProperty( has-
	plete Thing restriction	Comp domain(unionOf
	(hasComp minCardinal-	(System Comp))
	ity (1))) ;	range(Comp));
	Element(Comp com-	ObjectProperty( hasPort
	plete Thing unionOf	domain(Comp)
	(restriction (hasPort	range(Port));
	minCardinality (1))
	restriction (hasComp	ObjectProperty( hasRole
	minCardinality (1))));	domain(Connector)
		range(Role));
	Element(Connector
	complete Thing restric-	DatatypeProper-
	tion (hasRole minCar-	ty(Heuristic do-
	dinality (2)));	main(Connector)
		range(Float));
		ObjectProperty( attached
		domain(Port)
		range(Role));

Table 2 .

 2 ADML axioms, facts, and transition rules

	ADML Syntax	DDL Syntax	Semantics
	Elements
	Element( A partial C 1

Individual( sys type (System)); Individual( term type (Comp)); Individual( SAG type (Comp)); Individual( send-request type (Port)); Individual( receive-request type (Port)); Individual( caller type (Role)); Individual( callee type (Role)); Individual( sys value(hasComp term)); Individual( sys value(hasComp SAG)); Individual( sys value(hasConnector rpc)); Individual( term value(hasPort sendrequest)); Individual( SAG value(hasPort receive-request)); Individual( rpc value(hasRole caller)); Individual( rpc value(hasRole callee)); Individual( rpc value(Heuristic ex-pectedLatency)); Individual( send-request value(attached caller)); Individual( receive-request value(attached callee));

Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (No.11QG13) and the National Science Foundation of China (No.71101048).


Qianjin Wei
email: wei_qj@guet.edu.cn

Tianlong Gu

Fengying Li

Guoyong Cai

The Representation of Indiscernibility Relation Using ZBDDs

Keywords: rough set, Indiscernibility relation, Zero-Suppressed BDDs 1

The indiscernibility relation is the basic concept in Rough set theory, a novel representation of indiscernibility relation using Zero-Suppressed BDDs is proposed in this paper. Through introducing the indiscernibility matrix and the indiscernibility graph, we put forward the encoding of the variable and give the characteristic function. Once the characteristic function is constructed, it can be represented using ZBDDs.And further, combined with an example, we analyze the effectiveness of this method. It provides a basis for deal with rough set computing.

Introduction

The problem of imperfect knowledge has been tackled for a long time by philosophers, logicians and mathematicians. Recently it became also a crucial issue for computer scientists, particularly in the area of artificial intelligence. There are many approaches to the problem of how to understand and manipulate imperfect knowledge. The most successful one is, no doubt, the fuzzy set theory proposed by Zadeh. In this approach sets are defined by partial membership, in contrast to crisp membership used in classical definition of set. The theory of Rough set, proposed by Z. Pawlak in 1982, is a new mathematical tool to deal with imprecise, incomplete and inconsistent data [1] .In Rough set theory, expresses vagueness, not by means of membership, but employing a boundary region of a set. If the boundary region of a set is empty it means that the set is crisp, otherwise the set is rough. Nonempty boundary region of a set means that our knowledge about the set is not sufficient to define the set precisely. The rough set theory has become an attractive field in recent years, and has already been successful applied in many scientific and engineering fields such as machine learning and data mining, it is a key issue in artificial intelligence. The indiscernibility relation plays a crucial role in Rough set theory. Due to its importance, the different representations have been developed. Most existing are indiscernibility matrix and indiscernibility graph [START_REF] Yao | On Reduct Construction Algorithms[END_REF][START_REF] Yao | Discernibility matr Simplification for constructing attribute ruducts[END_REF][START_REF] Thangavel | Dimensionality reduction based on rough set theory: A review[END_REF][START_REF] Hu | Learning in relational databases: A rough set approach[END_REF][START_REF] Dongyi | A new discernibility matrix and the computation of a core[END_REF][START_REF] Guoyin | Calculation methods for core attributes of decision table[END_REF] .

Ordered Binary Decision Diagrams, graph-based representations of Boolean functions [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF] , have attracted much attention because they enable us to manipulate Boolean functions efficiently in terms of time and space. There are many cases in which conventional algorithms can be significantly improved by using BDDs [17][7] . Zerosuppressed BDDs [START_REF] Minato | Zero-suppressed BDDS for set manipulation in combinatorial problems[END_REF] are a new type of BDDs that are adapted for representing sets of combinations. It can manipulate sets of combinations more efficiently than conventional BDDs. especially when dealing with sparse combinations. A Muir, I Düntsch and G Gediga discussed rough set data representation using binary decision diagrams [5] , in which, a new information system representation is presented, called BDDIS. Chen Yuming and Miao Duoqian presented searching Algorithm for Attribute Reduction based on Power Graph [START_REF] Yuming | Searching Algorithm for Attribute Reduction based on Power Graph[END_REF] , a new knowledge representation, called power graph, is presented in those paper, therefore, searching algorithms based on power graph are also proposed. Visnja Ognjenovic, etc presents a new form of indiscernibility relation based on graph [START_REF] Ognjenovic | The Representation of Indiscerniblity Relation by Graph[END_REF] . In this paper, ZBDD is used to represent the family of all equivalence classes of indiscernibility relation; it has been shown how the indiscernibility relation can be obtained by ZBDD.

Indiscernibility relation in rough sets theory

The basic concepts, notations and results related to the theory of rough set are briefly reviewed in this section, others can be found in [START_REF] Pawlak | Rough sets[END_REF][START_REF] Skowron | The discernibility matrices and functions in information systems[END_REF][START_REF] Pawlak | Rough set approach to multi-attribute decision analysis[END_REF][START_REF] Pawlak | Rudiments of rough set[END_REF] .

Information Systems for Rough Set

An information system is composed of a 4-tuples as follows: I= < U, Q, V, f > Where U is the closed universe, a finite set of N objects {x 1 , x 2 … xn} Q is finite attributes {q 1 , q 2 … q m } V = ∪ q∈Q V q where V q is a value of the attribute q, called the domain of attribute q. f: U × Q → V is the total decision function called the information function Such that f(x, q) ∈ Vq for every q∈Q, x∈U .Such that f(x, q) =v means that the object x has the value v on attribute q. An information table is illustrated in Table 1,

Table 1. An information table U a b c x 1 x 2 x 3 x 4 x 5 x 6 x 7 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1
which has five attributes and seven objects, with rows representing objects and columns representing attributes.

Indiscernibility relation and set approximation

Let I=<U, Q, V, f> be an information system, then with any non-empty subset P⊆Q there is an associated indiscernibility relation denoted by IND (P), it is defined as the following way: two objects x i and x j are indiscernible by the set of attributes P in Q, if f (x i , q) =f (x j , q) for every q∈P, More formally: (3) Given any subset of attributes P, any concept X⊆U can be precisely characterized in terms of the two precise sets called the lower and upper approximations. The lower approximation, denoted by PX, is the set of objects in U, which can be classified with certainty as elements in the concept X using the set of attributes P, and is defined as follows:

IND(P)={( x i ,x j )∈U×U ⏐∀q∈P,f(x i ,q)=f(x j ,q)} (
PX={

x i ∈ U ⏐[ x i ] IND (P) ⊆X} (4)
The upper approximation, denoted by PX, is the set of elements in U that can be possibly classified as elements in X, and is defined as follows:

PX={

x i ∈ U ⏐[ x i ] IND (P) ∩X≠∅} (5
) For any object x i of the lower approximation of X, it is certain that it belongs to X. For any object x i of the upper approximation of X, we can only say that it may belong to X.

According to Table 1, we have the following partitions defined by attribute sets {a}, {b}, and {c}, {d}:

U/IND({a})={{x 1 , x 2 , x 3 , x 5 , x 6 },{x 4 , x 7 }} U/IND({b})={ {x 2 , x 3 , x 6 }, { x 1 , x 4 , x 5 , x 7 }} U/IND({c})={{x 1 , x 2 , x 4 }, { x 3 , x 5 ,

C. Indiscernibility Matrix

Given an information table I=<U, Q, V, f >, two objects are discernible if their values are different in at least one attribute, the discernibility knowledge of the information system is commonly recorded in a symmetric ⎟U⎥×⎟U⎥ matrix M I (c ij (x i , xj)), called the indiscernibility matrix of I. Each element c ij (x i , xj) for an object pair (x i , xj) ∈U×U is defined as follows:

c ij (x i , x j )= (6) ∅ otherwise {q∈Q f(x i , q)≠f(x j , q)} f(x i ) ≠ f(x j )
Since M I (c ij (x i ,x j )) is symmetric and c ii (x i , x i )=∅,For i=1, 2… m, we represent M I (c ij (x i , x j )) only by elements in the lower triangle of M I (c ij (x i , x j )), i.e. the c ij (x i , x j ) is with 1< i < j <m.

The physical meaning of the matrix element c ij (x i ,x j ) is that objects x i and x j can be distinguished by any attribute in c ij (x i , x j ), In another words, c ij (x i ,x j ) is defined as the set of all attributes which discern object x i and x i .The pair (x i , x j ) can be discerned if c ij (x i , x j ) ≠∅. The indiscernibility matrix of Table 1 is shown Table 2, for the underlined object pair (x 1 , x 2 ), the entry {b, c, d, e} indicates that attribute b, c, d or e discerns the two objects.

Table 2.

Indiscernibility matrix for the information system in Table 1 x

Zero-suppressed BDDS

Combination Sets

Sets of combinations often appear in solving combinatorial problems. The representation and manipulation of sets of combinations are important techniques for many applications. A combination on n objects can be represented by an n bit binary vector, (x 1 x 2 …x n ), where each bit, x k ∈{0, 1}, expresses whether the corresponding object is included in the combination or not. A set of combinations can be represented by a set of the n bit binary vectors. In other words, combination sets is a subset of the power set of n objects. We can represent a combination set with a Boolean function by using n-input variables for each bit of the vector, If we choose any one combination vector, a Boolean function determines whether the combination is included in the set of combinations. Such Boolean functions are called characteristic functions. For example, given three elements {a, b, c}, consider the set of subsets {{a, b}, {a, c}, {c}}.If we associate each element with a binary variable having the same name, the characteristic function of the set of subsets is f=abc′+ab′c+a′b′c .The first minterm corresponds to the subset {a, b}, and so on. The operations of sets, such as union, intersection and difference, can be executed by logic operations on characteristic functions.

Once the characteristic function is constructed, it can be represented using a OBDD or ZBDD. The two representations of the set of subsets {{a, b}, {a, c}, {c}} are given in Fig. 1 (a).In both diagrams, there are three paths from the root node to the1-terminal node, which correspond to the subsets {a, b}, {a, c}, and {c}.By using OBDD for characteristic functions, we can manipulate sets of combinations efficiently. Due to the effect of node sharing, OBDD compactly represent sets of huge numbers of combinations. Despite the efficiency of OBDD, there is one inconvenience that the forms of OBDD depend on the input domains when representing sets of combinations. This inconvenience comes from the difference in the model on default variables. In combination sets, default variables are regarded as zero when the characteristic function is true, since the irrelevant objects never appear in any combination.Unfortunately, such variables cannot be suppressed in the OBDD representation, and many useless nodes are generated when we manipulate sparse combinations. This is the reason why we need another type of OBDD for manipulating sets of combinations.

Zero-suppressed BDDs

Zero-suppressed BDDs are a new type of BDD adapted for representing sets of combinations. This data structure is more efficient and simpler than usual BDDs when we manipulate sets in combinatorial problems. They are based on the following reduction rules: pD-deletion rule: Delete all nodes whose 1-edge points to the 0-terminal node, and then connect the edges to the other subgraph directly, as shown in Fig. 2 Merging rule: Share all equivalent subgraphs in the same manner as with conventional BDDs Notice that we do not delete the nodes whose two edges point to the same node. The zero-suppressed deletion rule is asymmetric for the two edges, as we do not delete the nodes whose 0-edge points to a 0-terminal node. It has been shown how the indiscernibility relations can be obtained by a graph. The application of the indiscernibility graph enables the partitioning or the universe of objects represented by their attributes [START_REF] Ognjenovic | The Representation of Indiscerniblity Relation by Graph[END_REF] . Let I=<U, Q, V, f> be an information system, where U={x 1 , x 2 … x n }, the indiscernibility graph is a tree structure to represent the family of all equivalence classes over U, we call this graph IR-tree. P⊆Q is any subsets of Q, nodes equally distant from root node represent all equivalence classes over U for P. To be able to observe entire indiscernibility classes by a certain attribute, each node needs to be associated with an attribute value label<v q1 , v q2 ,…,v qm >,where v qm is a value of the attribute q m ∈P.

Fig. 3. The indiscernibility graph in Table 1 For example, the indiscernibility graph for the information system in table I is shown in Fig. 3. The root node of IR-tree is U= {x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 }, the children are nodes that represent the family of all equivalence class over U for attribute {a}.For the node which represents the first indiscernibility class for the attribute {a}( x 1 , x 2 , x 3 , x 5 , x 6 ,,<0>),its child nodes are equivalence classes for the attrib-ute{a,b},and so on .The leaf nodes represent indiscernibility relation classes for Q={a,b,c}.

Zero-suppressed BDDs of indiscernibility relation

Let I=<U, Q, V, f> be an information system, where U={x 1 , x 2 … x n }, Q= {q 1 , q 2 … q m }. By formula (1), for any attribute q∈Q, there is an indiscernibility relation IND({q}).The equivalence class[x i ] IND({q}) of any object x i ∈U consists of all objects x j ∈U such that (x i , x j ) ∈ IND({q}). In other words, an equivalence relation induces a portioning of the universe U, the partitions can be used to build new subsets of the universe, a subset of k objects can be represented by an k-bit binary vector, [x 1 , x 2 …x k ], in which 1-compent (x i ) means that the object x i is included in the subset and 0-compent (x i ') means that the object x i is not included in the subset. For the information system in table 1, the ZBDDs of indiscernibility relation for attribute {a}, {b}, {c} is given in Fig. 4.

On the foundation of research above, the crucial problem is to create unique ZBDDs of indiscernibility relation for all subsets of attributes Q, this can be done by the following way. We can encode the attributes with m-bit binary vector [q 1 q 2 … q m ], where each bit, q k ∈{0, 1}, expresses whether or not the attribute is included in the combination. Consider R⊆Q, the equivalence class of the equivalence relation of IND(R) can be represented by m+n -bit binary vector[q 1 q 2 … q m x 1 , x 2 …x k ]. we obtain the characteristic function of indiscernibility relation f (abc x 1 x 2 x 3 x 4 x 5 x 6 x 7 ) as follows: 3 Once the characteristic function is constructed, it can be represented using a ZBDDs,the ZBDDs of f is shown in Fig. 5. 1 5

Fig. 5. ZBDDs of indiscernibility relation for information table in Table

ZBDDs Of indiscernibility relation and state space

For evaluating the ZBDD node deletion, it can be proved that the upper bound on the size of the ZBDDs is the total number of elements appearing in all subsets of a set.Meanwhile, the upper bound on the size of the ZBDDs is given by the number of subsets multiplied by the number of all elements that can appear in them. This shows that ZBDDs should be much more compact when representing sets of subsets. The above theoretical upper bound on the ZBDDs size is rarely reached, this means that ZBDDs are particularly effective for representing sets of sparse combinations.

Conclusions

The indiscernibility relation is the mathematical basis of the Rough set theory; indiscernibility matrix is a widely accepted representation for it. In this paper, we gave a new representation of indiscernibility relation based on ZBDDs. Through introducing the method by a graph, we put forward the new method by the data structure of Zero-Suppressed BDDs.Then, the encoding variable and the characteristic functions have been introduced, and further ,the implementation steps which construct ZBDDs of indiscernibility relation is presented. At the same time, combined with ZBDDS and concrete example we analyze the effective of this method. the results is shown in Table 4.

1 )

 1 Where IND (P) is called the P-indiscernibility relation. If (xi, x j ) ∈ IND (P), then objects x i and x j are indiscernible from each other by attributes from P. Obviously IND (P) is an equivalence relation. The family of all equivalence classes of IND (P) will be denoted by U/ IND (P) , an equivalence class of IND(P) containing x will be denoted by [x] IND (P) . U/ IND(P)={[x] IND (P) ⏐x∈U } (2) [x] IND (P) ={y∈U ⏐(x,y) ∈ IND(P)}

Fig. 1 (Fig. 1 . 4 ZBDDs

 114 Fig. 1. OBDD and ZBDD for the set of subsets {{a, b}, {a, c}, {c}} Fig. 2. pD-deletion rule

Fig. 4 .

 4 Fig. 4. ZBDDs of indiscernibility relation for attribute {a}, {b}, {c} in Table 1

  x 6 , x 7 }} If we have the set {a, b} we will have: U/IND({a,b})={{x 1 , x 5 }, {x 2 , x 3 , x 6 }, {x 4 , x 7 }}

Table 3 .

 3 f (abc x 1 x 2 x 3 x 4 x 5 x 6 x 7 )= 0 otherwise 1 if X∈U/IND(P) where [abc] corresponding to subset P of attributes,[ x 1 x 2 x 3 x 4 x 5 x 6 x 7 ] corresponding to subset X of objects . characteristic function for the information system in Table 1 abc x 1 x 2 x 3 x 4 x 5 x 6 x 7 f abc x 1 x 2 x 3 x 4 x 5 x 6 x 7 f Based on the information table in Table 1, to subset{a,b}, U/IND({a,b})={{x 1 , x 5 }, {x 2 , x 3 , x 6 }, {x 4 , x 7 }},we can represent it used three vec-tor:[1101000100],[1100110010]and [1100001001],we obtained the characteristic function as Table

	001	0 010111	1	101	0001000	1
	001	1101000	1	101	0000001	1
	010	0110010	1	110	1000100	1
	010	1001101	1	110	0110010	1
	011	1001000	1	110	0001001	1
	011	0100000	1	111	1000000	1
	011	0010010	1	111	0100000	1
	011	0000101	1	111	0010010	1
	100	1110110	1	111	0001000	1
	100	0001001	1	111	0000100	1
	101	1100000	1	111	0000001	1
	101	0010110	1
	For example,

Table 4 .

 4 Storage efficiency comparison of ZBDDs with discernibility matrix Aknowledgment This work is supported by the National Natural Science Foundation of China (No.60963010, 60903079, 61063039) and the Natural Science Foundation of Guangxi Province (No. 2012GXNSFAA053220)

		⎟U⎥	⎟Q⎥	Size(KB)
				discernibility matrix	ZBDDs
	1	7	5	0.19	0.16
	2	50	5	9.76	6.89
	3	80	6	28.58	16.86
	4	100	7	53.67	29.38
	5	100	9	71.23	37.59
	6	150	10	175.78	108.62
	7	150	12	202.56	118.51
	8	200	10	299.34	151.12
	9	400	7	872.69	396.21
	10	500	11	2142.76	869.95


Yong Wang

Huadeng Wang

Cao Qiong

Analysis on Limitation Origins of Information Theory

Keywords: information theory, communication, reliability, model, uncertainty, probability

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Shannon information theory is aimed at the communication issues, and is not quite necessarily applicable to the information issues in the reality [START_REF] Shannon | A mathematical theory of communication[END_REF], and his infor-mation theory is called the special information theory by the later researchers. Aimed at the general information, some researchers have developed comprehensive information theory, generalized information theory, unified information theory etc [START_REF] Zhong Yixin | Principles of information science[END_REF][START_REF] Lu Chenguang | Generalized information theory[END_REF][START_REF] Klir | Uncertainty and Information:Foundations of Generalized Information Theory[END_REF][START_REF] Federico | Contributions towards a unified concept of information[END_REF], in which some limitations of the special information theory are identified, but no one of these information theories can eliminate all the limitations of information theories. In this paper, we attempt to analyze the limitations of the special information theory from some new perspectives.

Limitations of Shannon information theory in the reality

The currently recognized limitations of Shannon information theory are mainly as follows: Firstly, only the random uncertainty is considered in his information theory, while the uncertainties such as the limitations of sets in information expressions and the information fuzziness etc are not considered. Aimed at this issue, some researchers have developed the theories of fuzzy sets and rough sets. Secondly, neither the semantic nor the pragmatic aspects are considered in Shannon information theory, which were considered as the main origin of the limitation of information theory by some researchers [START_REF] Zhong Yixin | Principles of information science[END_REF][START_REF] Lu Chenguang | Generalized information theory[END_REF]. ZHONG Yixin developed his comprehensive information theory which includes syntactic information, semantic information and pragmatic information [START_REF] Zhong Yixin | Principles of information science[END_REF]. We find out the following limitations of information theory: Firstly, the information reliability is not considered in information theory, while most information in the reality is unreliable. The reliability of information is the precondi-tion to the information values, for example, the reliability of the intelligence informa-tion is very important. The reliability is a key indicator of information. however, it is not enough considered in information theory, which mainly emphasizes the uncertainty of information and the reliability of information transmission.

Secondly, the information completeness is not fully considered in information theory, while in the reality information is always incomplete (insufficient) and needs to be fused. When the more perfect information is unavailable, people cannot help but expediently take partial information temporarily as complete information. In this case, the information that may be deemed that the incomplete information is unreliable compared with the complete information [START_REF] Yong | Analysis and Betterment of Shannon's Information Definition[END_REF].

Thirdly, in information theory, some simple channels may be combined into a channel through parallel or serial connections, for example, the channel matrix of two simple serial channels may be directly multiplied into one channel. However, the complex and multi-level information transmissions are not considered in information theory. for example, the information may be transmitted from one source to an intermediate sink, and forwarded from the intermediate sink to a final sink, the information may be fused from many sources to many sinks, the transition probability matrix may be uncertain, furthermore, during such transmissions, the information may be converted, during multi-level transmissions or complex transmission, multiple uncertainty may occur. In that case, not only the message or code is uncertain, but the probabilities that express the uncertainty are uncertain. The information in the reality often needs to be conveyed through this kind of multiplex transmissions, during which multiple uncertainties may occur. If the above-mentioned fuzzy sets etc are also considered, such multiple uncertainties will become more complicated. The complexity of the parameters such as the channel matrix transmission probability etc is not considered in information theory, while in the reality, such transmission property may not be necessarily maintained certain and unchanged, it may be a random variable or more complex variable. Therefore the uncertainty of information system model should be considered.

Fourthly, the objects studied in information theory are the communications, whose transmission signals are certain. While in the reality, there are many uncertainties. During communications, it does not matter to define the information as something which reduces uncertainty. However, when confronted with the intrinsically uncertain information, the information is distorted if its uncertainty is eliminated. And the trifles are attended but the essentials are neglected during such eliminations. The quantum information theory serves as one kind of popularizations of the classical information theory. while the quanta bytes may include 0, 1 and superposed numbers between 0 and 1. In the reference [START_REF] Klir | Uncertainty and Information:Foundations of Generalized Information Theory[END_REF], the information reliability is considered, and it is pointed out that the information reliability is more important than its certainty. In the reality, people tend to select more uncertain but more reliable information, rather than selecting more unreliable but more certain information.

Fifthly, the conditions in information theory are comparatively simple, and mostly expressed in the probability of conditions. However, int the reality the conditions of information are often very complicated. For example, the given conditions may be knowledge, laws etc. Based on a known and prior probability, another law may be acquired, but it is impossible to easily calculate any corresponding probability of conditions through this law.

Sixthly, the known information is expressed with the prior probability in information theory, however in the reality, a lot of known information may not be expressed with the prior probability, for example, an unknown variable may be included, which may be a restrictive condition, or may be a law.

Seventhly, as the semantic aspects are not considered in information theory, it is not considered that the information may be mutually incompatible and contradictive. In the reality, a large quantity of information may be inconsistent and contradictive each other. .

Analyses on information examples

Considering the above limitations, and in order to make them look more obvious, we analyzed the following examples.

Example 1: If a sender sends a receiver an important intelligence saying: "Some two nations are going to start a war". When speaking from an information theory perspective, such information itself is the information that involves a large quantity of information. But if this information is not true, it may cause great disasters. People tend to emphasize more on the information reliability, if the information is unreliable, further communications become insignificant, and the information becomes valueless. In information theory, efforts are extended only to ensure that a receiver receives the original information. while it is not studied whether the information from an information source is truly reliable. If the above-exemplified information is unreliable, then the probability of a war between such two nations may be not at 1, but a number between 0 and 1. in this case, the probability value itself is randomly uncertain. In order to avoid confusing the probability uncertainty and the information uncertainty, it may be assumed that the sent intelligence is rewritten as: "the probability of a war to be started between some two nations is at 0.7". If this intelligence is not absolutely reliable, then this probability value is most likely not at 0.7, but close to 0.7. in this case, the probability itself is not certain, and the value at 0.7 may be just an average. This kind of reliability issues may be more complex. for example, in addition to that the war possibility is unreliable, it is possible that the subjects are unreliable. for example, maybe the war is possible between three nations instead of two nations, or between two persons etc.

Example 2: The probability of an event m is determined by some conditions, supposing that these conditions are c 1 , c 2 , …, c n , and supposing that the probability of the event m may be expressed as

P(m) = f (c 1 , c 2 , …, c n )
If the only condition c 1 is unknown to us, while all of the others are known, maybe the average value of P(m) can be calculated according to probability distributions of the condition c 1 . Based on specific cases, the condition c 1 is known and certain. But when this condition is unknown, we can only expediently replace the true probability with the average probability value calculated when this condition is unknown. In this case, the two probability values are close, but they are not equal. When the average value is used to replace a specific value, the information becomes obviously unreliable. Therefore, when the information in this example is incomplete, it may become an information unreliability issue. Generally speaking, the more conditions become known, the more complete the conditions are. and the probability well become more closer to the probability when the conditions are fully complete, therefore the information becomes more reliable. In this example, the case may become more complex. For example, the probability of m still may be a random variable even when all of the conditions are certain. It is like the inaccurate measurement principle in quanta dynamics, which is not caused by existences of hidden parameters or the incompleteness of quanta dynamics, but is one kind of natural uncertainties.

Example 3: The occurrence probability of an event m may be tested through experiments. When the known condition is t: "the experiment result is P(m|t) =0.7", we can't affirm P(m|t), which is the occurrence probability of the event m, we can only be sure that P(m|t) is a random variable close to 0.7. If this random variable has to be replaced with the fixed value 0.7, this value will cause reliability issues. The joint probability distributions and condition probabilities frequently appear in the probability theory and information theory. but it is not considered that under many conditions, the probability value itself in the condition probabilities or joint probability distributions may be a random variable, or partially unknown, or even completely unknown, and then the uncertain probability value will be improperly taken as a certain probability value.

Example 4: A student always gets very high scores with an excellence probability at 0.875, but he gets sick right before an exam. As his learning is delayed due to his sickness, the probability of his excellence may reduce to 0.75. Before we know that the student gets sick influencing his learning, the uncertainty of the prior probability that we known is less than the uncertainty of the posterior probability after we know that his learning is influenced. From an information theory perspective, the latter is reversely reduced in the information contents. In the reality, people will not select an prior probability on the ground that its uncertainty is low, but will select a posterior probability determined when the conditions become more complete as it is closer to the reality. This example shows that measurements on information per uncertainties are limited, and such measurements are not applicable to the uncertain issues. in addition, it also shows that the information needs to be specified in measurements on its reliability and completeness, and that this specification is more important than the information entropy used to measure the information uncertainties.

Example 5: A receives from B an intelligence saying: "it is 99% sure that the enemy will attack us on tomorrow morning". later, A receives the same intelligence from C. If seen from information theory perspective, the uncertainty of the question "will the enemy attack us on tomorrow morning?" is the same in such two cases. therefore the information contents equal to each other, while it seems that C does not provide any new information. However, people will still feel that they receive the information from C, and this kind of information makes A feel more certain "it is 99% sure that the enemy will attack us on tomorrow morning". this example further shows that the information reliability shall be taken as one specification to measure the information.

Example 6: When the information that "all events occur at equivalent probabilities" is received, and if speaking from what contents are included in this sentence, or the question "how are the occurrence probabilities of all events distributed?" the uncertainties hereof are eliminated. However, if speaking from what events will occur, it is impossible that such information becomes more certain. the information contents cannot be increased, but only be decreased. This point shows that the information contents are only measured on the information uncertainties, while the uncertainties of the questions derived from this information are not certainly related to the information contents. therefore, the measurements through an information entropy are applicable only to limited scopes, but not to the daily information issues.

Example 7: Brillouin once developed one paradox: If one information paragraph is sent in a text whose last part tells the receiver otherwise that all of the previous information is not true. In this case, is any information transmitted? Brillouin recommends that attentions be made on the negative information. In this paradox, there are two information parts, the second of which negates the first. I believe that such two information parts contradict each other and their reliabilities are both relative. But in general cases, if the sender is honest and not making purposeful jokes, then according to the context and reasoning analysis, the possibility of the latter information part being true becomes much higher. In this case, when the former and the latter information parts are summed up, it may be deemed that no useful information has been sent. Of course, the possibility that the sender made a mistake in the latter part or sent the mistaken information cannot be absolutely eliminated. In information theory, the associations between various information symbols are expressed with redundancies. but in general cases, this information may be integrally looked as one kind of redundancy codes, namely the codes that are impossible to be sent (the codes with a sending probability at 0). As time delays exist during communications (if no time delays exist. in general cases, the information will be self appropriate), such delays enable sending the information that is originally incompatible or impossible to be sent through the complete information.

Through the above analyses, some limitations of information theory are revealed to provide foundations for identifying the origins of information theory limitations. Of course, there are many other limitations, which will not be described here further.

Limitations origins of information theory

As analyzed through the above examples, it may be concluded that in information theory, the information reliability is not considered, while the information reliability is a very important indicator. During communications, as the information is certain, a certain relationship exists between eliminations of uncertainties and increases of reliabilities. In fact, it is easy for us to eliminate the uncertainty. while in Shannon information theory, an uncertainty is eliminated on the foundation that the information reliability and completeness are ensured. for example, error correction codes are used to correct errors, and the posterior probability is used to strengthen the information completeness. If the information certainty is taken as the sole specification, and the information reliability is disregarded. then the probability of an event may be randomly determined as 1, while the probabilities of the other events may be randomly determined as 0. Furthermore, if we take the information certainty as the primary target to be considered, and the reliability as the secondary one. then we may also designate the probability of the most probable event as 1, and of the other events as 0. In this case, the certainty is firstly ensured. while the reliability is also satisfied to certain extents. If so, information theory and the information processing become quite simple. obviously in the reality, people do not treat them in this way. According to many of the above analysis, the reliability is one of the primary information specifications.

The above information reliability, information completeness, and the incompliance of classical sets with the reality may be all summed up into the neglects of the multilevel information uncertainties. For example, during example analysis, we discovered the unreliable information, whose expression itself was not fixed, and whose probability value might be a random variable. while the incomplete information is also similar. The non-classical sets in the categories of fuzzy sets and rough sets then may be deemed to have been caused by one set that includes uncertain objects. For example, in rough sets, an object a may or may not belong to the set X. then a random uncertainty exists as to whether the object a belongs to the set X. When some uncertainties are accumulated on the original uncertainties in information theory, the multi-level uncertainties will occur. The uncertainties in this case may include the other uncertainties in more forms, in addition to the random uncertainty and the fuzzy uncertainty. they also include some uncertainties caused by incomplete restrictive conditions. It can be seen that the neglects of the multi-level information uncertainties are important origins of information theory limitations. while the neglect of the information reliability is also an important reason why it is impossible for information theory to be widely applied. Whereas all of the information is rarely reliable and complete, so we may attribute the information reliability and completeness to the information relativity. In fact, it is very rare that people in the reality receive the completely reliable information, they can only expediently apply the comparatively reliable information. when the more reliable information becomes available, people will apply the more reliable information to replace the previously experienced information. As the reliability is also related to the uncertainty of the probability values, the information reliability may be measured with reference to the measurements by Shannon on the information uncertainties. However, the calculations of the probability uncertainties will be more complex than the calculations of the information entropies, as the probabilities have to satisfy more restrictive conditions. From Brillouin paradox, example 4 and example 6, we can know that the formula of Shannon information contents is used only to measure the minimum transmission when the special information is being transmitted. during communications, it also reflects the reliability to some extents. However, when the meanings correspondingly derived from the information are considered, neither the information contents nor the information meaning certainties are certainly related to the sizes of the information contents. while the certain information may end up increasing the uncertainties of the other information. Some information may even increase the uncertainties of some information and meanwhile decrease the uncertainties of the other information. for example, the information, "it rains today" may decrease the uncertainty of "are the roads wet today?", but meanwhile increase the uncertainty of "will the students come late today?". Obviously, it deserves our deliberations on whether the negative information needs to be considered.

Of course, information theory is highly similar to the information issues in the reality. the methods applied in information theory provide very valuable references for researches on the information issues in the reality (including researches on the information reliabilities). For example, the mutual contradictions in Brillouin paradox are very similar to the inconsistence caused by the mistaken error correction codes. similarly, the most probable events may be taken as the events that really occur. while when all probabilities are close to each other, the information may be "deleted" in the similar way how the information channels are deleted.

Information theory limitations originate from the nature that information theory is oriented to communications issues, and are the intrinsic limitations of information theory models. Of course, such limitations are also related to the limitations of the probability theory. Due to insufficient researches on the randomness and multi-level random uncertainties of the probability values, people are likely to fall into the thinking tendencies that "the probabilities (including distributions of the joint probabilities) are the certain values which never happen to be random variables in any case", that "the condition probabilities may be determined whenever the conditions are given" etc. while these thinking tendencies are only applicable to some parts of the probability theory issues in the reality. As these restrictive conditions in information theory can better satisfy the communication demands, consequently information theory has been successfully applied in the communication fields. If we wish to popularize it in the general information fields, then corresponding restrictive conditions need to be removed according to its limitations.

Most of the limitations is rooted in the overlooking of the ubiquitous uncertainty of the objects about the information system, such as uncertainty of model, parameters, algorithms, functions, participator and process. We can simplify the information problem by using certain object to replace uncertain objects, this is very beneficial for research and can transform the reality problems to mathematical model so as to be processed by mathematical method, but this poses limitations and restricts the freedom of problems.

Conclusion

This paper analyzes some limitations of Shannon information theory. Through the researches on its limitations, on one hand, its applicable scopes can be determined to avoid abusing information theory and to apply information theory in suitable fields. On the other hand, directions may be provided for popularizing and referring to information theory. For example, the information expressions may be improved according to the limitations that the probabilities in the information expressions are fixed values, but not random variable or more complex variable, so as to accommodate the needs to research the information reliabilities, and to further popularize information theory. In addition, new directions are also proposed for the developments of the probability theory. Information theory is also similar, in many aspects, to the information issues in the reality, such as the afore-mentioned considerations of the information reliabilities and completeness. And some of these issues can be solved by referencing information theory.

.