Integration of Heterogeneous Systems as Multi-Agent Systems

Systems integration is a difficult matter particularly when its components are varied. The problem becomes even more difficult when such components are heterogeneous such as humans, robots and software systems. Currently, the humans are regarded as users of artificial systems (robots and software systems). This has several disadvantages such as: (1) incoherence of artificial systems exploitation where humans' roles are not clear and (2) vain research of a user's universal model. In this paper, we adopted a cooperative approach where the system's components are regarded as being of the same level and they cooperate for the service of the global system. We concretized such approach by considering humans, robots and software systems as autonomous agents assuming roles in an organization. The latter will be implemented as a multi-agent system developed using a multi-agent development methodology.

Introduction
The relation between humans and artificial systems ASs (robots and software systems) is considered in the way that humans are users of artificial systems according to ASs' needs. Such consideration has several disadvantages such as: The design of collective employment of ASs by several humans is difficult, Such employment can become easily incoherent where the humans roles aren't clear, Vain research of users' universal model for all roles and systems.
In this paper, we adopted a cooperative approach in which we consider each system's component as being cooperative and of the same level (peer-to-peer). No component is the server of another but they all serve the global system. We concretized this by considering humans, robots and software systems as autonomous agents assuming roles in an organization. Such an organization will be carried-out by a multi-agent system qualified of heterogeneous society (See Fig. 1). This has several advantages such as: It isn't necessary to search a user's universal model. In this approach, each human as a part of the system has a profile that will be defined according to a multi-agent development methodology, We use a multi-agent methodology for the development of such societies, The system can benefit, in the same time, from the artificial systems capacities but also from the humans' capacities since they are considered as components of the global system.
The heterogeneity of the components (humans, robots and software systems) of such societies poses the problem of their integration solved in this paper by associating specific software systems, qualified of interface agents, for humans and robots. In this paper, we show how we have exploited the cooperation based-approach of interface agents , developed initially for humans integration in multi-agent systems, to integrate robots also.
The remaining of the paper is organized in five sections. In section 2, we introduce a classification of the current robotics systems and then we address some of their limitations. Section 3 is a short introduction of the notions of agents and multi-agent systems. We clarify then the notion of heterogeneous societies as multi-agent systems, in section 4, where we explain the relation between heterogeneous societies and multi-agent systems. In section 5, we recall MASA-Method's basic elements, and we explain how we can develop heterogeneous societies in MASA. We illustrate such development by an example of pieces manufacturing society, in section 6. We terminate the paper by a conclusion in section 5, in which we trace some advantages and disadvantages of our approach.

Current robotics systems
Current robotics systems can be classified in individual robotics systems (implying only a single robot at a time), and Collective robotics systems (including several robots working together). Their limits can be then classified into two types: Individual robotics systems limits regarding the collective robotics, and limits of the robotics systems (individual or collective) not implying humans. The limits of individual robotics are well known for the works on the collective robotics (See for examples (Jung, D., & Zelinsky, A., 1999), (Zlot, R., et al. 2002), (Arai, T., et al.2002)). They can be summarized in the fact that it's impossible for a single robot to make: (1) too difficult tasks, or (2) tasks in parallel on spatially different sites. Furthermore, manufacturing powerful robots (carrying out hard works) is difficult.
The limits of robotics systems not implying humans can be looked in the advantages of some with regard to the others. For examples, the robots excel in the realization of painful, height precision, routine-minded, repetitive, dangerous, intricate ... tasks; while humans excel in the all tasks that humans can make and the robots cannot. Such tasks are numerous. They are those not foreseen in the robots functioning but, especially, those that we cannot endow robots with. The most convincing are, evidently, the intelligent activities. Consequently, robotics systems not implying the humans will be always limited.
A typical situation where an explicit relation among humans and robotics is needed is that of the difficulties that can encounter robots during the achievement of their missions. For example, in some cases, the robot's vision system cannot determine if the object in its front is an obstacle or it is harmless (Fong, T., et al. 2001). In such situations, the only choice a robot has is to continue to execute in bad way or to stop. The humans cannot assist it.
From the relation with humans, we classify the robotics systems in four classes: Individual robots completely autonomous (autonomous robots), Robots forming completely autonomous society (collective robotics or autonomous robotics society),

Autonomous robots
A robot of this category can realize a task in an autonomous way. This task can be a chaining (plan) of more elementary subtasks being able to include sequences and/or loops. The robot is a human's server in this task.
This category can be classified into two subclasses: Comments A human (or robot) is considered as an agent, called HR. To integrate such agents, we associate to the agent HR a soft-ware S, qualified of interface agent. S holds HR's objective. In this figure, S is: orange smiley for robots, blue smiley for humans. (green smiley is a software agent) S holds HR's plan and interacts with HR to carry out the plan's actions, such as [Act i (D, L); Act j (D, L);] where Act is an action on the environment, and D and L are any action parameters.
In the first, the human supplies the tasks plan, which the robot must execute without any help (in an autonomous way). In the second, the human establishes high level goals, which the robot will accomplish in an independent way by elaborating a plan itself. The difference between the two classes is in the nature of the goal (Fong, T., et al. 2001). In the first case, the goals are limited and the human realizes the tasks planning. In the second case, the goals are more abstract and the robot is responsible for the plan's elaboration. Let us indicate that the robot can be completely autonomous only for some simple applications (Fong, T., et al. 2001).
The autonomous robots are interesting for the numerous applications which they have in the daily and professional life but, furthermore, because they constitute the base of all the other categories. The limits of this category are those of the individual robotics and those of robotics systems not implying directly the humans.

Robotics autonomous societies
Robots organized in an autonomous society can make a common global task, autonomously. In this case, the autonomy concerns not only the robots but also all what is internal to the society. Robots are then human's servers in this task. The study of collective robotics extends naturally that on the individual robots systems, but it is also an independent discipline. This class can be also subdivided into two subclasses: 1. Supervised societies, 3. Completely autonomous societies.
Most of the proposed architectures for the collective robotics, such as AuRA (Arkin, R. C., & Balch, T., 1997) and ALLIANCE (Parker, L. E., 1998), concentrate on the intensification of the robot teams' autonomous capacities rather than on their operation with humans.
The research that incorporated the human operator (such as ROBODIS (Surmann, H., & Theißinger, M., 1999), RAVE (Dixon, K., et al. 1999), MokSAF (Payne, T. R., et al. 2000) and MissionLab (Arkin, R. C., et al. 1999)) consider the human as being, especially, available for the initial planning. The collective robotics advantages are those remedying the individual robotics limits and its limits are those of robotics systems not implying the humans.

Semiautonomous robots
A semiautonomous robot can realize several elementary tasks in an autonomous way, but only one task at a time (The chaining plan of such tasks is missing in such robots). Such robot serves the human by realizing, every time, one task. These robots can be considered as specialized tools, which are exploited by the humans in various ways. Robots are then considered as human servers who dictate them, every time, what they have to make. The human possesses then the robot's command. In this case, we have two roles: That of a tool knowing and able to make elementary things in a completely automatic way, That of a human who has to exploit this knowledge and this capacity to reach various objectives.
The importance of such robots lies in their use in situations where the human's supervision is very sought such as surgery. However, the difficulties of this category are, in part, those of the individual robotics. Furthermore, such robots are limited to the formed persons (experts' users) because of considerable difficulties and risks they put. Because all the command decisions are humandependent, the performance of the entire system is then bounded by the human skills. Several human factors, including skill and training, influence the system's functioning. Other factors, such as the communication's band width, in the case of the tele-operation, can also influence the operational efficiency.
If a semiautonomous robot has a difficulty, it is up to the human to get it out from this situation by indicating to the robot what to make. This can be qualified as an advantage, with regard to the autonomous robots. However, some situations are hard to solve, such as where the human does not: Know that the robot has a difficulty, such as a situation of tele-operation, or The difficulty's nature which has the robot; a robot remaining immovable and its user does not know for what reason.
In such situations, the only choices, which the robot has, are to continue to execute badly or to stop. Finally, the human is completely mobilized to command the robot. Such mobilization would overload the human being and/or sub exploits the robot (Fong, T., et al. 2001).

Collaborative autonomous robots
The robots of this category can realize tasks autonomously while having the capacity to ask the human to realize given tasks on behalf of the robot. The human is considered as being a source (Fong, T., et al. 2001) for the robot (supply information, resolves some ambiguities, etc.). The robot serves the human for a pre-established task while asking the human to realize particular tasks.
The most representative of these works is the Fong's collaborative approach (Fong, T., et al. 2001). In such approach, the human must be at the robot's disposal to serve it according to its needs.
The advantage of the robots of this category, with regard to the previous categories, is that they allow humans to compensate the autonomy's inadequacy in some situations while decreasing the human's overload and increasing the robot's exploitation. Among its disadvantages, we can cite those of the individual robotics. Furthermore, such systems cannot beneficiate completely from humans' capacities since humans are solicited only to realize tasks in some situations and they are not involved completely in the global system.

Conclusion
The major difficulties of current robotics systems reside in: the inability of isolated robots to accomplish some hardest and spatially distributed tasks, the limits of the robots autonomy where they always need humans.
Such systems fail also in finding equilibrium between the tasks that must be accomplished by humans, and those which must be accomplished by the robots. Finally, they fail in their visions of the software systems where such systems are considered as robots functioning only.
In the following sections, we explain the cooperative approach to the development of heterogeneous societies', which use both human faculties and software systems. The development of such societies was done using a multi-agent development methodology.

Agents and multi-agents systems
In order to clarify the reasoning followed in the development of heterogeneous societies, we introduce some notions about the vision of humans as systems and the cooperation between heterogeneous systems, including humans, robots and software systems. In subsection 3.1, we explain the systems properties. We show, particularly, the relationship between the general notion of system with software systems, robots and humans. We explain, then, the agent's notion as a system, in subsection 3.2, to introduce cooperation aspects in multi-agent systems, in subsection 3.3.

System's properties
A reactive system is the one that perceives its environment by means of its sensors and acts on it by means of its effectors. A communicative system uses some of its sensors to receive messages from other systems and uses some of its effectors to submit messages to others according to a preestablished communication protocols. Among the system's aspects two are fundamental: control and functioning. The system's control commands the sensors to perceive the environment and the effectors to act on such environment. It acts on its sensors and effectors by conforming to a system's functioning.
A classical system (CS) is considered as a server used according to a functioning and pre-established communication protocols. Its functioning is reduced to knowledge procedures. The user (an agent who is, usually, a human) invokes the system's knowledge procedures according to a plan that he (she) possesses that CS does not know. The role of CS's control is limited to interpreting the communication's protocols and the knowledge, and to command sensors and effectors according to external systems demands.

System's autonomy (self-control and pro-activity)
The system's autonomy can be seen from several viewpoints: energy, resources, decision-making, etc. From the control's viewpoint, CS can be considered as being autonomous. This means that the system, without any external intervention, commands its sensors and its effectors and interprets its knowledge and its communication protocols. However, a CS isn't functionally autonomous in a manner that it depends on another system, which indicates every time what it must make.
A functionally autonomous system can take the initiative to act on the environment; the system is called proactive. We obtain a proactive system by endowing the system with an objective allowing its control to make decisions on what it has to make. The system will be then directed by such an objective, which is proper to it, not by external interventions. The system rejects then external interventions that are not compatible with its objective.
To help a proactive system to make decisions on external interventions (asking it to accomplish actions) it is necessary that these demands must be accompanied with elements others than asked action, in contrast to the classical systems. These elements concern, in particular, a performative clarifying the demand's nature (wish, order, etc.). This implies that the communication protocols of proactive systems must be based on speech acts. Consequently, the proactive system's functioning consists in two parts: knowledge and system's objective supplied with speech acts protocols.

System's social ability.
A system, even though it is autonomous, lives in an environment with other systems with which it cooperates in a direct or indirect way. This cooperation is indirect if the system acts on the environment without coordinating (communicating and synchronizing) its actions with other systems. It's direct in the case of system's actions are coordinated with other systems. In this case, the system is qualified as being with a social ability.

Agents
Several works were used agent technology (such as (Mellah, H., 2011)) with different meanings. In this paper, we take the vision considering an agent as a system. In such vision, see Jennings (2001), an agent is considered as a system enjoying the properties of autonomy, reactivity, proactivity and social ability. An agent must be then endowed with: A control, which can be procedural, declarative or intelligent, Sensors and effectors which we subdivide into two classes: Class 1. those used for the communication with other agents, Class 2. those used to perceive and to act on the environment, such as the wheels of a robot, Communication protocols, which must be based on speech acts. Their descriptions are functions of perceptions and actions on the environment by means of the agent's sensors and effectors of the first class. They can be considered as particular knowledge, Knowledge described according to perceptions and actions on the environment by means of sensors and effectors of the second class, An objective described according to the agent's knowledge procedures and its communications. These last ones allow invoking the knowledge's procedures of other agents.
The agent's control is responsible of: Interpretation of the agent's objective, its communication protocols and its knowledge's procedures, Command its sensors and effectors.

Multi-agent systems
A multi-agent system is composed of agents assuming roles in a given organization. It possesses the system's fundamental aspects, which are: control and functioning. The agents are autonomous and pro-active systems. Consequently, the control and functioning of a multi-agent system are distributed on its agents. The only direct relation that can exist between the agents is that of their communication.
The agents are cooperative. We consider the cooperation as being an achievement of a common global task. Since the agents are autonomous, it is necessary to distribute this global task on the agents. Each agent will have its own subtask (its individual task) of the organization's global task. The achievement, in a coordinated way, of the agents' individual tasks must allow reaching the organization's global objective.

Heterogeneous societies as multi-agent systems
Heterogeneous societies' components are humans, robots and software systems. If the consideration of software systems and robots as systems is very common, this is less obvious for the humans. In this section, we try to explain the relation between such components and the agents (in subsection 4.1), we recall the cooperation based approach (in subsection 4.2), and the integration of heterogeneous agents so they constitute a multi-agent system (in subsection 4.3).

Humans
Humans are agents by Excellency. The agent's scientific notion itself is borrowed from that of the human. In theory, a human doesn't make any task without being aware of its meaning. He has the properties of control's autonomy, reactivity, pro-activity and social ability. However, the human's objective can be not compatible with that of the global system where we would place him. To overcome this difficulty, we require from a human to temporary change its implicit objective to follow a pre-established plan so he can be accepted as a part of a given system. This isn't new in the humans' societies or its relation with artificial systems. For example, to integrate him in a given work, we demand to a human to behave in a special way. Another example is that of using a tool where the human will follow the constructor's instructions. There is then always a required preliminary condition so a human can exploit a classical system. However, in contrast to this, in the cooperation-based approach, the human is directed by a clear objective.

Robots
A robot is an attempt to reproduce the human. The robots developers try to endow them with the human's characteristics. It has then several agents' characteristics. However, the developers' objective, which is that of human's reproduction, hasn't been reached completely. Consequently, the robots don't have some of the agents' characteristics. A robot is a physical system and has its own control. When we submit it under another system's supervision, such as a computer system or a human, it executes the commands dictated by such supervisor system. In this case, the commands sequence submitted to the robot constitute its functioning, not its control. A simple robot has then reactivity and control's autonomy characteristics but it isn't proactive. When we endow a robot by a simple explicit objective, such as that affected to special tasks or that with functioning, it becomes pro-active. But, to endow them with a social ability, these robots must have the ability of communication with other systems.

Software system
Before we associate it to a processor, the software system has not a control's autonomy. It is used by a hardware system as a functioning (a plan) to direct it in accomplishing some tasks. Consequently, the software system is considered as a functioning. When we associate a processor and peripherals to software, we obtain a system that has a control's autonomy and reactivity. Implicitly, what we consider as software system is the result of such association. In practice, we associate to a software system, which we will consider as agent, an independent thread representing its virtual control. We can then qualify a software agent as a virtual agent.
The reactivity of a software system is obtained by the command of its peripherals that constitutes its sensors and effectors. However, a classical software system isn't proactive and hasn't a social ability. It's then necessary to endow it with such characteristics.
Classical software systems have, in reality, an implicit objective that is the one of serving its users. It waits for the user's demand and reacts to it according to its knowledge. For example, the objectoriented system's control proceeds as follows: 1. Creates some system's objects, and displays references to some objects, in form of icons. The latter constitute an object-oriented interface, 2. Waits that a user selects (from a contextual menu, for example) one of these icons (O) and one of its actions or methods (M), 3. Executes M on O's state, and go to 2.
Such objective doesn't allow the system to make initiative in executing its methods without being demanded by another part. To make a classical system pro-active, we must change its implicit objective by an explicit one allowing it to take initiative. The means for this depends on the software classical system's model.

Cooperation-based approach for interface agents development
Abstractly, in the cooperation-based approach, we consider a human (or a robot) as an agent HR that assumes one or more roles. Conceptually, we associate to HR a software system S that holds the HR's objective. S is a software agent qualified of interface agent.
The interface agent for a human (hS) has neither the human's intellectual abilities nor its resources exploitation. We supplement this lack by an interaction between hS and a human. The agent HR consists then of hS completed by the human's intellectual abilities and his resources exploitation. Similarly, the interface agent for a robot (rS) hasn't the robot's physical abilities concerning the actions achievement on the physical environment. The agent HR will then be consisted of rS completed by a robot's physical abilities. Since HR is an agent belonging to a multi-agent system, the derivation of the required characteristics of HR and then those of rS or hS will follow a multi-agent development methodology.
In the cooperation-based approach, the actions' plan is qualified of individual task and must be explicit. Its base is the roles that the robot or the human must assume in a given organization (see section 5). It is then determined during the multi-agent system (MAS) design so that the MAS's functioning will be coherent. It is the interface agent's responsibility to hold the individual task, and to ensure its execution. In the case of the human, this execution consists of:

Sequencing actions plan,
Requesting from the human to execute his knowledge's procedures, Requesting from the software agents (including other interface agents) to execute their actions.
In the case of the robot, it consists of: Sequencing actions plan, Executing the knowledge's procedures by communicating to the robot the necessary commands, Demanding to software agents (including other interface agents) to execute their actions.
The difference between a robot's interface agent and that of a human is in the communicated objectives level. The human's interface agent can communicate with the human in high level objectives. This is not the case with a robot where we can communicate it only elementary actions in a specific command language. The difficulty is that in the design level where it isn't convenient to manipulate such commands, directly. Consequently, we use, at the design stage, high level objectives that we must implement in the specific command language, at the implementation stage. This means that the human's interface agent holds only the objective and the human possesses the knowledge's procedures. However, the robot's interface agent must hold also the knowledge's procedures that are functions of the robot's commands.

Heterogeneous agents integration as multi-agent system
As we explained it, software systems, robots and humans can be considered as classical systems that we can endow them with the agents properties, which are those of control autonomy, reactivity, proactivity and social ability. The difficult task is that of the heterogeneous agents' integration so that they can cooperate harmoniously. We overcome this difficulty by exploiting the cooperation-based approach for the interface agents . One of the interface agent's purposes is to establish a sound communication relation between the virtual (software) environment and the nonsoftware systems, and vice versa. Furthermore, such interface agents are software systems that can communicate with other software agents including other interface agents. As a consequence, we can establish a communication among software and non-software agents and among non-software agents themselves by means of interface agents.
Being given that the communication's relations are the only relation that exists between the agents, the result is then a multi-agent system with heterogeneous agents. The communication's relations are very useful between robots and humans. They are also useful for the communication among humans who cannot communicate directly (situated in remote spaces). But, sometimes, these relations are even useful for humans situated nearly (among video game's players, in the case of the communication of voluminous information, etc.). However, in many situations, the humans communicate directly among them in a suitable way. It is then the responsibility of the system's developer to choose the most suitable way to communicate between two humans who are a part of a heterogeneous society.
In heterogeneous society, we can charge the software agents with: Executing tasks concerning the data processing automation: calculations, storage, research...,

Making some decisions.
We can then charge the robots by achieving: Actions on physical environment, such as object transportation for mobile robots, manufacturing for tool machines (decided by themselves, by humans and/or by software agents), Information and events perception such as the axes positions, scene (camera), etc.
Whereas, the human can be charged by: Achieving treatments of intelligent tasks, Making some decisions, Achieving actions on the physical environment decided by them, by software agents and/or by robots.

Heterogeneous societies in MASA
In this section, we show how we can develop heterogeneous societies in MASA project. In subsection 5.1, we present briefly MASA-Method (see (Lahlouhi, A., 2006), for more details on MASA-Method's description). In subsection 5.2, we explain how we derive interface agents in MASA.

MASA-Method
MASA project (Multi-Agent modeling of Systems based on Autonomous and heterogeneous components) comprises three parts: MASA-meta-model which is a multi-agent meta-model, MASA-Method which is an organizational, complete and mixed multi-agent methodology (see , for a classification of multi-agent methodologies), MASA-applications which is a set of multi-agent applications.

Organizations in MASA
The organization's structure is composed of roles, and communication relations between them. In reality, we create an organization to achieve a given goal. From the methodological viewpoint, the developer puts in his mind an objective, and he creates, then, an organization to achieve such goal. Obviously, the objective will be merged in that of the organization once it is established. However, methodologically, it exists. Consequently, we define an organization as a pair (Organization's structure, Global objective).
We can replace a declarative expression of objective by a procedural expression "achieve goal". The task "achieve goal" is the organization's global task. Consequently, we define an organization as a pair (organization's structure, global task).
In MASA, we employ colored Petri nets (Jensen, K., 1994) (CPN) for describing global tasks. We made the global task's description as follows: A transition contains a role attached to one of its knowledge's procedures, Any entry arc to a transition is labeled with a procedure's input, Any exit arc from a transition is labeled with a procedure's output, The places are means of communication between such procedures (outputs for some procedures and inputs for others).

Agents and multi-agent systems description in MASA
A multi-agent system is composed of agents assuming roles of a given organization. The agents are cooperative in a way that their objectives are derived from those of the organization according to a roles attribution. Since the organizations' global objectives in MASA are described using CPN, the agents' objectives will be also expressed using CPN.
In ordinary Petri nets, the communication isn't explicit. This makes difficult to express the communication between agents in individual tasks. Research works on the agents' behaviors modeling employs autonomous Petri nets where they represent communications by arcs (see (Xu, H., & Shatz, S. M. 2001), for example). This does not express clearly the agents' autonomy, which is a fundamental characteristic. For the description of individual tasks, we employ then non-autonomous colored Petri nets (see (David, R., & Alla, H., 2010)). In autonomous Petri nets, the transitions are subjected to internal Petri nets conditions only, in particular, places marking. In non-autonomous Petri nets, the transitions are subjected to external events also.
In MASA, we perceive communication messages as events attached to transitions. A transition's outgoing arc schematizes the message's emission while an entering arc schematizes a message's reception. We do not consider what occurs between the message's emission and its reception. This belongs to implementations of the communication protocols.

MASA-Method's methodological process
The MASA-Method's methodological process consists in: Creating an organization satisfying the system's requirements. This includes, mainly, the description of its communication structure and its global task (GT), Derivation of the multi-agent model satisfying such organization. This includes, mainly, the attribution of the roles to agents and the derivation of the agents' individual tasks from GT, Multi-agent model's implementation as a distributed object oriented multi-system.

Interface Agents derivation in MASA
Knowledge's procedure of an interface agent for a human presents him the procedure's name and its data and/or receives from him its execution's results. If the communication means with the human are the usual ones (keyboard, screen, mouse...), displaying data and/or inputting results can be complex. They can be formatted texts, graphs and/or images. In this case, the associated procedures must use tools enabling them to display such data and/or to assist the human to enter results. A knowledge procedure of an interface agent will be then described as follows: Display the procedure's name and a description of it, Display its data if there is any, Recover results if there is any.

Case study: Pieces manufacturing society
The system of pieces' manufacturing takes the customer's demands Dem. Then, the designers create a schema (design) Cn satisfying each demand. Such schema will be transformed into a manufacturing program Pg by skilled programmers. Pg will be then translated into a memory image Im by a software translator PP. The worker W then supplies the digital machine with raw material Rm. The machine uses the memory image and the raw material to manufacture pieces. Once manufacturing is done, the worker cleans C the machine and removes waste Wst. Such scenario is described in the CPN of Fig. 2

Development of the multi-agent system for pieces manufacturing
In the following, we present a model of multi-agent system according to the following process (see (Lahlouhi, A., 2006) for further details on MASA-Method's development processes): 1. Develop an organization's model (see Tab. 1): This concerns mainly the development of the organization's task (Fig. 2) and the communication relations between roles ( Fig. 3.a), 2. Derivation of a multi-agent model (Tab. 2): This step includes identifying agents and assigning such agents to roles. In our case study, we identified three agents: a. WP: Worker-Programmer (Human), b. PP: Translator (Software system), c. M: Machine (Robot). 3. Derivation of the communications between the agents: In the organization's communication structure (Fig. 3.a), we substitute the roles by the agents assigned to them (Fig. 3.b) to lead to a simplified model of communication between agents (Fig. 3.c), 4. Derivation of the multi-agent's global task (Fig. 4). The latter is the same as that of the organization's task in Fig. 2; in which we substitute the roles by the agents assuming them, 5. Simplification of the multi-agent global task; if it can be simplified as indicated in Fig. 5. In the latter, we regrouped identical transitions into one transition. The parts of the agents' tasks are identified based on the transitions including the agents' identifiers illustrated by coloring them, 6. Derivation of the agents' models ( Fig. 6): we give such models in related tables as follows (further details on such derivation are given in subsection 6.2): Agent M (Tab. 3), Agent WP (Tab. 4), and Agent PP: we don't give the table describing PP. It is obvious. 7. Implementation of agents models which constitute an implementation of the multi-agent model (not given in this paper). Such implementation will be based on the tables (Tab. 3 and Tab.4) describing the agents.
It is important to note that such process doesn't make a distinction between software, human and robot agents. It is at the implementation phase that we distinguish between such agents particularly in the implementation of their knowledge procedures. For the humans, such procedures ask the human agent to carry out some actions where for the robots it commands them to do things.

Derivation of the agents tasks
To derive the agents' tasks (their associated CPN) from that of the multi-agent's global task, we proceed as follows. Firstly, we identify the parts of the agents' tasks as shown in Fig. 5. Secondly, we extract the CPNs of the different agents while adding the communication between the agents (see Fig.  6); i.e., sending messages from senders and receiving such messages by receivers (see (Lahlouhi, A, 2006) for further details on methodological guiding). Note that the agents' identifiers are needless in the transitions of the agents' CPN. The messages are based on speech acts (Smith, I. A., & Cohen, P. R., 1996) and they are composed as follows; as indicated in Fig. 6: 1. (Receiving agent, performative, action, (action parameters)), for sending a message. It is represented by a place containing the action's parameters and a transition labelled with "the agent's identifier followed with S (for Sensor)" which is followed by an action "Act Emission, AE". For example, for a transition labeled "WPS.AE", WPS indicates a communication sensor of the receiver WP. Such a sensor is an object of WP, in an object-oriented terminology. The same sensor will be used at receiving the message. Finally, an arrow indicates that the message exits such transition, 2. (Sent agent, performative, action, (action parameters)), for receiving a message. It is represented by a transition labelled with "the agent's identifier followed with S (for Sensor)" followed by a place containing the action's parameters. An arrow showing the message entering such transition as an event, which indicates that such CPN is not autonomous, i.e., firing such transition is conditioned by the reception of such message.

Tab. 2: Case study -Multi-agent system model
Identifier PM Fig. 4 Description Imitates the PMO's organization

Conclusion
In this paper, we described MASA's approach for the development of heterogeneous societies as multi-agent systems. MASA's approach consists in integrating heterogeneous agents (humans, robots and software systems). Such integration is made by using special software systems, called interface agents. The derivation of the interface agents' characteristics is made by using MASA-Method, a multi-agent development methodology. The tasks of the derived agents are synchronized using Colored Petri Nets. We showed the application of the approach by a case-study of manufacturing pieces that uses heterogeneous agents: software, robot and human.
The MASA's development approach of heterogeneous societies inherits the advantages of both collaborative and collective robotics approaches. The inheritance of the advantages of collaborative approach resides in the fact that the resulted robotics system contains humans where the robots can ask them for services. The inheritance of the collective robotics advantages resides in the fact that heterogeneous society can contain several robots, which cooperate to realize a common global task.
In addition, MASA's approach has several other advantages, with regard to previous approaches, such as the following: Heterogeneous agents (software, robots and humans) can share tasks in a coherent way, Using multi-agents methodology for the characteristics' derivation of the agents (robots and humans) and, consequently, for those of their interface agents, The same system can benefit from the (intellectual and/or physical) abilities of humans and robots, The cooperation can be managed easily between humans, between robots and/or between robots and humans through a computer network.


User Interface Design for E-Learning Software

User interface (UI) is point of interaction between user and computer software. The success and failure of a software application depends on User Interface Design (UID). Possibility of using a software, easily using and learning are issues influenced by UID. The UI is significant in designing of educational software (e-Learning). Principles and concepts of learning should be considered in addition to UID principles in UID for e-learning. In this regard, to specify the logical relationship between education, learning, UID and multimedia at first we readdress the issues raised in previous studies. It is followed by examining the principle concepts of e-learning and UID. Then, we will see how UID contributes to e-learning through the educational software built by authors. Also we show the way of using UI to improve learning and motivating the learners and to improve the time efficiency of using e-learning software.

B. UI Design Issues
Four common design issues almost always surface: System response time, help facilities available to user, error information handling, and command labeling. It is far better to establish each as a design issue to be considered at the beginning of software design, when changes are easy and costs are low [13].

V. UI DESIGN ISSUES FOR E-LEARNING SOFTWARE
Knowledge about the factors that affect teaching and learning will enable teacher (e-learning designer)to make informed decisions in the teaching activities. This section analyses some important factors affecting teaching and learning, which are related to the UI. Also it presents a way to apply these factors in UI.

A. Stimulus
Learners need to be diligent and active since the main goal

1) Using speech interface
Voice interface can help one overcome situations that are even highly stressful; it enables people to be more relaxed and creative. Moreover, Matching gender, personality, or accent fosters feelings of trust and interest [14].
A particular voice type can affect how much students like the speaker and how hard they try to understand the presented material [15].

2) Using informal communication style instead of formal
In order to stop computer looking like a piece of iron, Speech and text should be presented in an informal style to comfort the learner . Researches [16] show that under appropriate circumstances, people behave like a real person towardsa computer. Thus, to reach our purpose an informal style is more suitable. Nonetheless, the method must be approached carefully so as not to leave learners under the impression that the context is of no importance.Wordusage should not appear to be unreal. It is suggested to use the first person and second person pronouns instead of third-person pronouns.
Researches show that when people feel they are engaged in interactive conversation with the others, they try to understand more than when they just receive information [17].
Researches [18] demonstrate that students, who learn in an informal style, act better than the contrary.
It should be noted that conversation must be polite.
Politeness of speech and behavior acts as a positive impact on learning [19].Furthermore, using polite words rather than imperative phrases increases learning [20].
Learners also gave more positive ratings to the on-screen agent who spoke with a human voice rather than a machine voice on an instrument designed to capture the social characteristics of a speaker [15].

3) Using Animated Pedagogical Agent (APA)
Educational agents are the shapes which appear in educational materials to suggest tips. These shapes can be a cartoon character, a video of a speaking head or specific virtual images (Avatars). Texts, speeches, illustrations, and animations can be used to form an agent [7].
The APA interface face-to-face creates an affective link with user/student [21].
One of the important concerns for an APA presentation is how to achieve the best speech and gesture cooperation [1].
Designers of multimedia learning environments should create life-like on-screen agents that speak in human voice rather than a machine-synthesized voice [15].
Researchers have proven that there is no difference between real and cartoon characters in training. Furthermore,a picture of the agent is not required to be shown while being used; only the voice would be sufficient [22].

4) Using variety of colors in educational Medias
Color variety, causes motivation and attention in students and makes educational materials seem more realistic [23].
Colors can also be used to group related information together. However, it should be noted that if more than 10 colors are involved, distortion of relation between information will be inevitable. Proper use of colors also accelerates reviewing and makes it easier. In addition, enough white space should be used on the interface screen. These spaces can bring order to pages to prevent clutter of information on screen. The last thing to be acknowledged about colors is to use dark text on a light background which expedites the reading [8].

5) Learners having control over learning environment
The learner control strategy has become more appreciated than tutor control or program control. In order to achieve this purpose,the following should be noted: Currently, the commonly used learner control strategies concentrate on the selection of topics, sequencing and pacing of contents,

B. Role of working and long-time memory in learning
Working memory is the mental activity center, where all active thoughts take place. Although this is a powerful processor, its capacity is limited. In fact new information must be processed in working memory, then merge with information into long-term memory, and at the end, when needed; it transfers from long-term memory to working memory to be used [7].
Teaching styles in electronic courses should help learners by using words and images in the course so that it combines with knowledge in long-term memory. To accomplish this, the following should be considered:

1) Highlighting important contents in the lesson
Techniques such as flash, changing colors, and big or/and bold text etc. should be used to highlight important texts and visual information. Another way to attract learner's attention to important contents is to write a list of learning objectives [7].

2) Desaturation of working memory with unnecessary materials
Working memory should be free to process new information. When a limited capacity of working memory is saturated, the process doesn't work properly and learning process becomes slow. Even keeping a limited amount of However, this recommendation does not mean that adding interesting images under all circumstances is wrong, but they are problematic when they interfere with the efforts of the students trying to understand the course.

3) Integration of auditory and visual information in working memory with existing knowledge in long-term memory
Working memory integrates words with images to provide a unified structure, and then these ideas are combined with the existing knowledge in the long-term memory. This issue needs to be processed in the working memory. The textual and visual information being presented together, and not separately, makes it easier to integrate words with images [7] [28].
Texts can be fragmented and placed in different parts of the image. When the text describes an operation or mode on the picture, it can be used as a pop-up message [7].

4) Using elements of the real world
Merely adding new knowledge into the long-term memory is not enough. New knowledge must be encrypted in their longterm memory so that when needed it is simple and quick to recover. Electronic lessons should offer objective and practical activities in the examples and exercises; that way long-term memory is a good position for new knowledge to be retrieved.
The shape and appearance of the educational environment should be based upon the actual environment where the learners at the end of the course should present their acquired information [15].

C. Using multimedia to present lessons
It is recommended to use instructional materials through a combination of visual (such as texts, graphics, etc.) and auditory elements (such as speech, music, etc.). This suggestion is based on two principles [7]: a) Learning theory of mind; this is based on these assumptions: a) Humans have separate channels for processing verbal and visual materials, b) Each of these channels can process a limited amount of information at any given time c) Students seriously try to build visual and verbal models by the presented materials and the relation between them.
b) People understand the materials better, when they are fully engaged in the process. Presenting a content using words and images make learners' mind more active, learners try to establish a relationship between the words and the images.
Using the words solely can encourage students (especially learners who are less experienced) to learn superficially and This is due to the reason that there are two separate channels of information (visual and auditory) going to the brain which helps reduce the compression of information (Figure 2).
It should be indicated that in the presence of a complex material such as a mathematical formula, the text might be required to be displayed on the page.  There is no picture to present.
 Learner has enough time to process the images and words.
 Learner may have difficulty to process spoken words.
 When the learners need to see materials frequently (such as a guide for problem solving).

D. Availability
Availability means that users can easily access intended As it was mentioned before, to provide stimulus, speech interface, informal style, agents, learner control environment, colors and background music must be used in presentation. The working memory also has a crucial role in learning and it should not be saturated with unnecessary information. When using multimedia information, it's better to use both hearing and vision channels if possible.
The UID should not only be seen as an artistic phenomenon, but artistic tools such as, graphics, music, animation, etc., must be compatible with the educational psychological issues.
Statistics and reports indicate that there are many dropouts in e-learning inclusive control [7]. It seems that one of the most important challenges is the UI of software. It is required to examine the relation between the UI and dropouts.


extfieldsofstudy:
Mathematics
Computer Science

text:
Tighter Fourier Transform Complexity Tradeoffs

The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukey's Fast Fourier Transform (FFT) from 1964 is a method for computing this transformation in time $O(n\log n)$. Achieving a matching lower bound in a reasonable computational model is one of the most important open problems in theoretical computer science. In 2014, improving on his previous work, Ailon showed that if an algorithm speeds up the FFT by a factor of $b=b(n)\geq 1$, then it must rely on computing, as an intermediate"bottleneck"step, a linear mapping of the input with condition number $\Omega(b(n))$. Our main result shows that a factor $b$ speedup implies existence of not just one but $\Omega(n)$ $b$-ill conditioned bottlenecks occurring at $\Omega(n)$ different steps, each causing information from independent (orthogonal) components of the input to either overflow or underflow. This provides further evidence that beating FFT is hard. Our result also gives the first quantitative tradeoff between computation speed and information loss in Fourier computation on fixed word size architectures. The main technical result is an entropy analysis of the Fourier transform under transformations of low trace, which is interesting in its own right.

Introduction
The (discrete) normalized Fourier transform is a complex linear mapping sending an input x ∈ C n to y = F x ∈ C n , where F is an n × n unitary matrix defined by F (k, ℓ) = n −1/2 e −i2πkℓ/n . (1.1) The Fast Fourier Transform (FFT) of Cooley and Tukey [7] is a method for computing the Fourier transform of a vector x ∈ C n in time O(n log n) using a so called linear algorithm. A linear algorithm, as defined in [12], is a sequence F 0 , F 1 , . . . , where each F i is a set of affine functions, for each i ≥ 0 F i+1 = F i ∪ {λ i f + µ i g} for some λ i , µ i ∈ C and f, g ∈ F i , and F 0 contains (projections onto) the input variables as well as constants.
As for lower bounds, it is trivial that computing the Fourier Transform requires a linear number of steps. Papadimitriou, for example, derives in [13] an Ω(n log n) lower bound for Fourier transforms in finite fields using a notion of an information flow network. It is not clear how to extend that result to the Complex field. There have also been attempts [15] to reduce the constants hiding in the upper bound of O(n log n), while also separately counting the number of additions versus the number of multiplications (by constants). In 1973, Morgenstern proved that if the modulus of the λ i 's and µ i 's is bounded by 1 then the number of steps required for computing the unnormalized Fourier transform, defined by n 1/2 F in the linear algorithm model is at least 1 2 n log 2 n. He used a potential function related to matrix determinant, which makes the technique inapplicable for deriving lower bounds for the (normalized) F . Morgenstern's result also happens to imply that the transformation √ n Id ( √ n times the identity) has the same complexity as the Fourier transform, which is not a satisfying conclusion. We also note that the unnormalized Fourier transform, as studied by Morgenstern cannot be simply implemented on a computer of fixed word length, because that transformation increases norms by √ n, and hence Ω(log n) bit words are necessary.
Ailon [1] studied the complexity of the (normalized) Fourier transform in a computational model allowing only orthogonal transformations acting on (and replacing in memory) two intermediates at each step. He showed that at least Ω(n log n) steps were required. The proof was done by defining a potential function on the matrices M (t) defined by composing the first t gates. The potential function is simply the sum of Shannon entropy of the probability distributions defined by the squared modulus of elements in the matrix rows. (Due to orthogonality, each row, in fact, thus defines a probability distribution). That result had two shortcomings: (i) The algorithm was assumed not to be allowed to use extra memory in addition to the space used to hold the input. In other words, the computation was done in place. (ii) The result was sensitive to the normalization of F , and was not useful in deriving any lower bound for γF for γ ∈ {0, ±1}.
In [2], Ailon took another step forward by showing a lower bound for computing any scaling of the Fourier transform in a stronger model of computation which we call uniformly well conditioned. At each step, the algorithm can perform a nonsingular linear transformation on at most two intermediates, as long as the matrix M (t) defining the composition of the first t steps must have condition number at most κ, for all i. We remind the reader that condition number is defined as M (t) · (M (t) ) −1 , where · is spectral norm. Equivalently, it is defined as σ 1 (M (t) )/σ n (M (t) ), where σ 1 (A) ≥ · · · ≥ σ n (A) are singular values of a matrix A. Otherwise stated, the result implies that if an algorithm computes the Fourier transform in time (n log n)/b for some b > 1, then some M (t) must have condition number at least Ω(b). This means that the computation output relies on an ill conditioned intermediate step. It is not difficult to see from the proof of the main result of [2] that, in fact most of the algorithm steps have condition number at least Ω(b). Hence, the bottleneck is ubiquitous. (We will return to the point of bottleneck ubiquity shortly.) Ill conditionedness, as claimed in [2], leads to numerical instability and compromise in robustness against noise. In this work we make a quantification of these claims. Roughly speaking, we show that a speed up of factor b implies that we either have to represent scalars with Ω(log b) bits (implying increased computation complexity in bit operations), or we'd have to sacrifice numerical errors Ω(b) times larger than those of standard FFT, for a given fixed word size architecture.

Main Contribution
Our first result (Theorem 5.1) is that, a speedup by a factor of b requires not only b ill-conditionedness in the usual sense, but requires a stronger notion of ill conditionedness which we define below. The theorem generalizes the main result in [2], while also providing a simpler proof.
Our second and main result (Theorem 5.3) states that, roughly speaking, in an architecture of fixed word size, speeding up FFT by a factor of b implies the existence of Ω(n) orthogonal directions in input space that are numerically unstable in that they cause overflow or underflow at Ω(n) different time steps. (The exact definition of overflow and underflow will be defined below). Avoiding these numerical instabilities could be technically achieved by allowing word size of length Ω(log b) at the offending memory word locations at particular time steps, but this incurs a bit operation complexity of Ω(n log b) because the number of such steps is Ω(n).

Fourier Transform Types
In theory and practice of engineering and computer science, there are two main types of Fourier transforms considered. The n dimensional Discrete Fourier Transform (DFT), as defined in (1.1), is a complex unitary mapping defined by the characters of the Abelian group Z/nZ. The Walsh-Hadamard transform is a real orthogonal mapping defined by the characters of the n dimensional binary hypercube (Z/2Z) n . More precisely, for n an integer power of 2, the (i, j)'th matrix element is defined as , where ·, · is dot-product, and [p] denotes (here only) the bit representation of the integer p ∈ {0, . . . , n − 1} as a vector of log n bits. Similarly to FFT for DFT, there is an O(n log n) time algorithm for computing the Walsh-Hadamard transform of an input x.
In this work we consider computation over the reals, and must hence view the n-DFT as an orthogonal mapping in R 2n in a standard way. (Each complex input coordinate is viewed as two real coordinates, one representing the real part and the other the imaginary part. Each complex matrix element of DFT is, accordingly, viewed as a two-by-two real matrix.) Throughout, we will assume n is an integer power of 2 and will use F to denote either the n−Walsh-Hadamard transform or the real representation of the n/2-DFT transform. In order for our results to work for the DFT case, however, we will have to make a slight modification to the potential function Φ defined in [2]. (This was not an issue there). We will present the modified function Φ C below and briefly explain where it is necessary, but will omit the technical details of working with Φ C , which are not much different than for Φ. For simplicity, the reader is invited to assume that F denotes the Walsh-Hadamard transform, and FFT refers to the fast Walsh-Hadamard transform.

Paper Structure
We start by defining the computational model in Section 3. In Section 4 we introduce further notation and recall (and generalizee) the matrix quasi-entropy function which was first defined in [2]. In Section 5 we present our results. The proofs, together with useful lemmas, are deferred to Section 6. One particular Lemma 6.4, a key to proving Theorem 5.3, is interesting in its own right.

Computational Model and Notation
We remind the reader of the computational model discussed in [1,2], which is a special case of the linear computational model. The machine state represents a vector in R ℓ for some ℓ ≥ n, where it initially equals the input x ∈ R n (with possible padding by zeroes, in case ℓ > n). Each step (gate) is either a rotation or a constant. A rotation applies a 2-by-2 rotation mapping on a pair of machine state coordinates (rewriting the result of the mapping to the two coordinates). We remind the reader that a 2-by-2 rotation mapping is written in matrix form as cos θ sin θ − sin θ cos θ for some real (angle) θ. A constant gate multiplies a single machine state coordinate (rewriting the result) by a nonzero constant. In case the constant equals −1, we call it a reflection gate. In case ℓ = n we say that we are in the in-place model. Any nonsingular linear mapping over R n can be decomposed into a sequence of rotation and constant gates in the in-place model, and hence our model is, in a sense, universal. FFT works in the in-place model, using rotations (and possibly reflections) only. A restricted method for dealing with ℓ > n was developed in [2], and can be applied here too in a certain sense (see Section 7 for a discussion). We focus in this work on the in-place model only.
Since both rotations and constants apply a linear transformation on the machine state, their composition is a linear transformation. If A n is an in-place algorithm for computing a linear mapping over R n , it is convenient to write it as A n = (M (0) = Id, M (1) , . . . , M (m) ) where m is the number of steps (gates), M (t) ∈ R n×n is the mapping that satisfies that for input x ∈ R n (the initial machine state), M (t) x is the machine state after t steps. (Id is the identity matrix). The matrix M (m) is the target transformation, which will typically be F in our setting. For any t ∈ [m], if the t'th gate is a rotation, then M (t) defers from M (t−1) in at most two rows, and if the t'th gate is a constant, then M (t) defers from M (t−1) in at most one row.
Both the n-Walsh-Hadamard and the real representation of the (n/2)-DFT can be implemented in-place using O(n log n) rotations.

Numerical Architecture
The in-place model implicitly assumes representation of a vector in R n in memory using n words. A typical computer word represents a coordinate (with respect to some fixed orthogonal basis) in the range [−1, 1] to within some accuracy ε. The accuracy level ε is Θ(1). For sake of simplicity, it should be thought of as 2 −31 or 2 −63 in modern computers of 32 or 64 bit words, respectively.
To explain the difficulties in speeding up FFT on computers of fixed precision words in the in-place model, we need to understand whether (and in what sense) standard FFT is at all suitable on such machines. First, we must restrict the domain of inputs. Clearly this domain cannot be R n , because computer words can only represent coordinates in the range [−1, 1], by our convention. We could restrict the input to come from the cube [−1, 1] n . Initializing the machine with such input is easy, but the output (as well as intermediate steps) of the standard FFT map the cube to orthogonal transformations thereof, which might exceed the cube. The extreme case is an orthogonal transformation that translates the unit vector (1/ √ n, . . . , 1/ √ n) to (0, . . . , 1). Under such transformation, an input of (1, . . . , 1) from the cube is mapped to (0, . . . , 0, √ n), overflowing in the last coordinate. It makes more sense to consider input from an n-ball of radius Θ( √ n), which we denote ). An n-ball is invariant to orthogonal transformations. Additionally, a coordinate of a random input from B(Θ( √ n)) is of typical magnitude Θ(1), and hence typically does not overflow. The problem is that, using well known principles from high dimensional geometry, it is very likely for some coordinate to be of magnitude Θ( √ log n). Hence, paradoxically, it is likely that some coordinate would overflow. Perhaps the reason that this issue is hardly every considered in literature on Fourier transform complexity (including the author's prior work) is because a number of magnitude Θ( √ log n) can be accommodated using Θ(log log n) bit words. It is unlikely to encounter an application with n = Ω 2 2 32 (let alone Ω 2 2 64 ), and hence this is really a non-issue for applications. Nevertheless, it's an issue for complexity theoretical purposes. So is the true running time of standard FFT O(n log n) × (time to multiply two Θ(log log n) bit words) , owing to a tiny minority of coordinates that overflow? The answer is no, because on expectation the number of bits required to encode a coordinate x(i) of a random vector x from B(Θ( √ n)) to within accuracy ε = Θ(1), is Θ(1). 1 In fact, using state-of-the-art integer multiplication technology [8,9], the expected time required to multiply such a random coordinate with a number of Θ(1) bits is Θ(1) when taking logical bit operations into account. However, we prefer to avoid dealing with bit operations in this work, and leave it to future work discussion (see Section 7). Instead, we shall take an information theoretical approach, and think of a word in memory, at a particular time step of the algorithm, as a channel that is used for encoding a random coordinate. If the coordinate is drawn from a distribution that requires O(1) bits on expectation to encode to within the fixed accuracy of ε, then no overflow occurs. If ω(1) bits are necessary, then we define this as overflow. 2 By this definition, standard FFT for input drawn uniformly from B(Θ( √ n)) does not overflow at all, because any coordinate of the machine state at any step is tightly concentrated (in absolute values) around Θ(1).
It will be easier to replace the uniform distribution from the ball with the multivariate Gaussian N (0, Id(Θ(n))), which is a good approximation of the former for large n. With this assumption, any coordinate of the standard FFT machine state at any step follows the law N (0, Θ(1)). By simple integration against the Gaussian measure, one can verify that the expected number of bits required to encode such a random variable (to within fixed accuracy ε) is Θ(1), hence no overflow occurs. This input assumption together with the no-overflow guarantee will serve as our benchmark.
Two notes regarding the numerical architecture: 1. Our definition of overflow is counterintuitive, because we are used to thinking about overflow as an offending machine state at a particular step of the algorithm execution for a particular input, while our definition is stochastic. The reason we use this definition is from the combination of (a) our desire to work with a spherically symmetric input and (b) avoiding measuring complexity in the granularity of logical bit operations, stemming from the varying word length typically arising even in the standard FFT benchmark. 3 2. We are completely ignoring the fact that the machine state after t steps on input x in any computer is not only a result of quantizing the vector M (t) x. Rather, errors are accumulated from the effects of quantizing at earlier steps. Taking accumulated errors into account should affect the numerical accuracy of both the benchmark and of any speed-up, but quantifying this effect seems extremely difficult. Again, we take an information theoretical approach by saying that the machine state after t steps contains at most the information in the quantization of 1 By "encoding" here we simply mean the base-2 representation of the integer ⌊x(i)/ε⌋. 2 By encoding of a random number X here we simply mean the integer representation of its quantization ⌊X/ε⌋. 3 It is possible to somewhat practically justify the stochastic definition of overflow by thinking of running FFT on a large number L of iid inputs, which can be thought of as being stacked as columns of an input matrix X. The larger L is, the more concentrated the total number of bits required to encode each row of the matrix around Θ(L) will be. For L polynomial in n, the probability of requiring more than Θ(L) bits per row becomes exponentially small at any step of standard FFT. We could have defined this as our benchmark, but we do not think that anyone would want to compute over a tightly compressed representation of matrix rows into arrays of words. Hence we've decided to settle for the stochastic definition of overflow. the coordinates of M (t) x, and whatever information lost (due to this quantization) cannot be later recovered because the machine state encodes everything that is known about the input (and output) at any given step.
Our chosen approach (and compromises) enable us to obtain what we believe are important insights into inherent tradeoffs of information version computation speed.

The Matrix Quasi-Entropy Function
The set {1, . . . , q} is denoted by [q]. By R a×b we formally denote matrices of a rows and b columns. Matrix transpose is denoted by (·) T . We use (·) −T as shorthand for ( We slightly abuse notation and extend the definition of the quasi-entropy function Φ(M ) defined on nonsingular matrices M from [2], as follows. Given two matrix arguments A, B ∈ R a×b for some This extends naturally to vectors, namely for u, v ∈ R a , Φ(u, v) is as above by viewing R a as R a×1 . If A, B ∈ R a×b and a, b are even, then we define the complex quasi-entropy function Φ C (A, B) to be: The function Φ C can be used for proving our results for the real representation of the complex DFT, which we omit from this manuscript for simplicity. The reason we need this modification to Φ for DFT is explained in the proof of Lemma 6.4, needed by Theorem 5.3 below. Elsewhere, we will work (for convenience and brevity) only with Φ. Abusing notation, and following [2], we define for any nonsingular matrix M : It is easy to see that Φ(F ) = n log n for the Walsh-Hadamard transform, because all matrix elements are ±1/ √ n. If F is a real representation of the (n/2)-DFT, then it is easy to see that Φ C (F ) = n log(n/2), because all matrix elements of the (complex representation of the) (n/2)-DFT are complex unit roots divided by n/2. It will be also useful to consider a generalization of the potential of a nonsingular matrix M , by allowing linear operators acting on the rows of M and M −T , respectively. More precisely, we will let Φ P,Q (M ) be shorthand for where P, Q ∈ R n×a are some mappings. (We will only be working with projection matrices P, Q here). Similarly, Φ C P,Q (M, M −T ) := Φ C (M P, M −T Q). Finally, for any matrix A ∈ R n×n , let σ 1 (A), . . . , σ n (A) denote its singular values, where we use the convention σ 1 (A) ≥ · · · ≥ σ n (A). If A is nonsingular, then the condition number κ(A) is defined by σ 1 (A)/σ n (A). For any matrix A, we let A denote its spectral norm and A F its Frobenius norm. If x is a vector, hence, x = x 2 = x F . Let B denote the Euclidean unit ball in R n 5 Results

FFT Speedup ⇒ Bottleneck
The result for this section should interpreted as follows: If an in-place algorithm A n = (M (0) = Id, . . . , M (m) = F ) speeds up FFT by a factor of b ≥ 1, then there exists an intermediate step M (t) that is ill conditioned (in a generalized sense, to be explained).
Theorem 5.1. Fix n, and let A n = {Id = M (0 , . . . , M (m) } be an in-place algorithm computing some linear function in R n and let P, Q ∈ R n×n be two matrices. For any t ∈ [m], let {i t , j t } denote the set of at most two indices that are affected by the t'th gate (if the t'th gate is a constant gate, then i t = j t , otherwise it's a rotation acting on indices i t , j t ). Then for Additionally, if R = 1 then the t'th gate can be assumed to be a rotation.
In particular, if M (m) = F and m = (n log n)/b for some b ≥ 1 ("A n speeds up FFT by a factor of b") and P = Q = Id, then For the main result in this paper in the next section, we will only need the case R = 1 of the theorem. It is worthwhile, however, to state the following corollary for general R, which is a simple consequence of the fact that for any matrix X and integer q, q i=1 σ 2 q (X) ≥ X(I, :) 2 F whenever |I| ≤ q.
This repeats the main result in [2], for the case R = 1 (our proof is also simper). The bound (5.3) is stronger in the sense that it imposes a stronger restriction on the spectrum of M (t) for larger values of R. The interesting case is, say, R = 2 b/2 . With this choice, (5.3) becomes: One extreme case of (5.4) is when σ 1 (M (t) ) = Ω(2 b/2 ) and σ 2 (M (t) ) = · · · = σ n (M (t) ) = 1. In this case, the condition number is exponentially higher than the bound achieved in [2]. The other extreme is the case σ 1 (M (t) ) = · · · = σ 2 b/2+1 (M (t) ) = α and σ n−2 b/2+1 +1 (M (t) ) = · · · = σ n (M (t) ) = 1, for some global α > 1. In other words, α-ill-conditionedness is exhibited by 2 b/2 disjoint pairs of eigenvalues of M (t) . We do not continue the discussion of this extended notion of ill condition, because we only need the R = 1 case for our main result in what follows.

Implications of Theorem 5.1 on Numerical Accuracy
We discuss the implication of Theorem 5.1, in case R = 1, P = Q = Id. The theorem implies that an algorithm with m = (n log n)/b must exhibit an intermediate matrix M (t) and a pair of indices i t , j t such that the t'th gate is a rotation acting on i t , j t and additionally: Hence, either Case (i). We can assume wlog that Then, letting x T over = M (t) (i t , :)/ M (t) (i t , :) ∈ R n (x over is the normalized i t 'th row of M (t) , transposed), we get that the i t 'th coordinate of M (t) x over is at least √ b. But this implies that, for input x = x over , the t'th step acts on a pair of numbers (M (t) x over )(i t ), (M (t) x over )(j t ), at least one of which requires representation using O(log b) in the numerical architecutre described in Section 3. Now, for input x ∼ N (0, Θ(n)), the i t 'th coordinate just before the application of the t'th gate equals M (t) (i t , :) x T x over , and is hence distributed Using (5.5), this distribution is N (0, Ω(b)). If b = ω(1), then by our definition we reach overflow.
Note also that it is possible as a preprocessing step to replace x with x − (x T x over )x over (eliminating the overflow component), and then to reintroduce the offending component by adding (x T x over )F x over as a postprocessing step. In the next section, however, we shall show that, in fact, there must be Ω(n) pairwise orthonormal directions (in input space) that cause such an overflow at Ω(n) different time steps, so such a simple "hack" cannot not work.
Case (ii). This scenario, as the reader guesses, should be called underflow. In case (ii), wlog Now define x T under = (M (t) ) −T (i t , :)/ (M (t) ) −T (i t , :) ∈ R n , and consider the orthonormal basis u 1 , . . . u n ∈ R n so that u 1 = x under . For any t ′ ∈ [m] (and in particular for t ′ = t): Now notice that the i t 'th coordinate of (x T over (M (t) ) −1 ) has magnitude at least b/2 by (5.6) and the construction of x over . Also notice that for all i = i t , the row M (t) (i, :) is orthogonal to x over , by matrix inverse definition. This means that coordinate i = i t of M (t) x contains no information about g 1 . All the information in g 1 is hence contained in (M (t) x)(i t ). More precisely, g 1 is given by where e is a random variable independent of g 1 . But |(( is known only up to an additive error of ε, due to our assumptions on quantization in the numerical architecture. This means that g 1 can only be known up to an additive error of at least ε b/2, for any value of e. It is important to note that this uncertainty cannot be "recovered" later by the algorithm, because at any step the machine state contains all the information about the input (aside from the input distribution prior). In other words, any information forgotten at any step cannot be later recalled. The uncertainty interval of size ≥ ε b/2 is not very severe, in the sense that it affects just one out of n input components. Indeed, at step 0 the input vector coordinates x(1), . . . , x(n) are represented in individual words, each of which gives rise to an uncertainty interval of width ε. This means that merely storing the input in memory in the standard coordinate system implies knowing its location up to an uncertainty n-cube with side ε, and of diameter ε √ n. 4 An uncertainty interval of size ε b/2 = O(ε √ log n) in a single direction is therefore hardly a deterrent for someone who wants to asymptotically beat FFT. The next section tells us, however, that the situation is much more severe, in the sense that underflow occurs in Ω(n) pairwise orthogonal input directions. (i) (Severe Overflow) There exists an orthonormal system v 1 , . . . , v n ′ ∈ R n , integers t 1 , . . . , t n ′ ∈ [m] and i 1 , . . . , i n ′ ∈ [n] with n ′ = Ω(n) such that for all j ∈ [n ′ ],

7)
where P j is projection onto the space orthogonal to v 1 , . . . , v j−1 .
In both cases of severe overflow and severe underflow, the gates at time t 1 , . . . t n ′ are all rotations, for all j ∈ [n ′ ] the index i j is one of the two indices affected by the corresponding rotation. Additionally, the set {t 1 , . . . , t n ′ } is of size at least n ′ /2.
The proof is deferred to Section 6.2. We discuss its implications, continuing the discussion following Theorem 5.1 in Section 5.2.
In the severe overflow case, Theorem 5.3 tells us that there exists an orthonormal collection v 1 , . . . , v n ′ (with n ′ = Ω(n)) in the input space, such that each v i behaves like x over (from Section 5.2). This means that, if the speedup factor b is ω(1), we have overflow caused by a linear number of independent in put components, occurring at Ω(n) different time steps (by the last sentence in the theorem). In the extreme case of speedup b = Θ(log n) (linear number of gates), this means that in a constant fraction of time steps overflow occurs.
The severe underflow is more interesting to analyze. An intuitive analysis is as follows: For each orthogonal direction v j , for j ∈ [n ′ ], we lose Θ(log b) bits of information about x T v j just before applying the t j 'th gate because, roughly speaking, we are trying to squeeze the value x T v j /γ j ∼ N (0, Θ(1/γ 2 j )) in the i j 'th word while not storing any information about x T v j in any other word, and γ j ≥ b/2. This lost information cannot be recovered later.
Although this explanation can be made rigorous using information theoretical tools, we prefer to offer a geometric interpretation. The theorem tells us that there exists an orthonormal collection u 1 , . . . , u n ′ in the input space that is bad in the following sense. For each j ∈ [n ′ ], redefine g j = u T j x to be the input component in direction u j . Again, the variables g 1 , . . . , g n ′ are iid N (0, Θ(1)). The first element in the series, u 1 , can be analyzed as x under (Section 5.2), whereby it was argued that before the t 1 'th step, the component g 1 = u T 1 x can only be known to within an interval of width Ω(γ 1 ε), independently of information from components orthogonal to u 1 . We remind the reader that by this we mean that the width of the interval is independent, but the location of the interval depends smoothly (in fact, linearly) on information from orthogonal components of x (see Figure 1).
As for u 2 , . . . , u n ′ : For each j ∈ [n ′ ], let z j := (M (t j ) ) −T (i j , :). Therefore u 1 = z 1 / z 1 and by (5.8), for j > 1 we can write z j = γ j u j + h j where h j ∈ span{u 1 , . . . , u j−1 }. Treating z j / z j as x under in Section 5.2, we conclude that the component (z j / z j ) T x of x can only be known to within an interval of size Ω(ε z j ), given any value of the projection of input x onto the space orthogonal to z. We extend the list of vectors z 1 , . . . , z n ′ , orthonormal vectors u 1 , . . . , u n ′ , numbers γ 1 , . . . , γ n ′ and projections Q 1 , . . . , Q n ′ to size n as follows. Having defined z j , u j , Q j , γ j for some j ≥ n ′ , we inductively define Q j+1 as projection onto the space orthogonal to span{z 1 , . . . , z j } = span{u 1 , . . . , u j } and z j+1 to be a standard basis vector such that Q j+1 z j+1 2 ≥ 1 − j/n. (Such a vector exists because there must exist an index i 0 ∈ [n] such that j j ′ =1 u j ′ (i 0 ) 2 ≤ j/n, by orthonormality of the collection u 1 , . . . , u j ; Now set z j+1 to have a unique 1 at coordinate i 0 and 0 at all other coordinates.) We let u j+1 be Q j+1 z j+1 / Q j+1 z j+1 , that is, a normalized vector pointing to the component of z j+1 that is orthogonal to span{z 1 , . . . , z j } = span{u 1 , . . . , u j }. The number γ j+1 is defined as Q j+1 z j+1 . By construction, γ j+1 ≥ 1 − j/n.
The above extends the partial construction arising from the severe underflow to a full basis, with the following property: Proposition 5.4. For any j ∈ n, even given exact knowledge of the exact projectionx of x onto the space orthogonal to z j , the quantity x T (z j / z j ) upon termination of the algorithm can only be known to within an interval of the form [s, s + ε z j ] where s depends smoothly (in fact, linearly) onx.
The proposition is simply a repetition of the analysis done for x under in Section 5.2, for j ≤ n ′ . For j > n ′ it is a simple consequence of the fact that upon initialization of the algorithm with input x, each coordinate of x (and in particular x T z j ) is stored in a single machine word, while all other machine words store information independent of x T z j . Hence the uncertainty of width ε z j = ε.
What do we know about x upon termination of the algorithm? As stated earlier, any information that was lost during execution, cannot be later recovered. Let I denote the set of possible inputs, given the information the we are left with upon termination. Consider the projection Q 2 onto the space orthogonal to u 1 = z 1 / z 1 , as a function defined over I. Let I 2 = Q 2 I denote its image. The preimage of any point w ∈ I 2 must contain a line segment of length at least εγ 1 parallel to u 1 , due to the uncertainty in x T u 1 . Hence the volume of I is at least εγ 1 times the (n − 1)-volume of I 2 . 5 Continuing inductively, we lower bound the (n − j + 1)-volume of I j := Q j I = Q j I j−1 for j > 2. Consider the projection Q j as a function operating on I j−1 , and any point w in the image I j . By definition of Q j , there existsŵ ∈ I such that Q jŵ = w. By proposition 5.4, the intersection of the line L = {ŵ + ηz j : η ∈ R} with I must contain a segment ∆ of size ε z j . The projection Q j ∆ of this segment is contained in the line Q j L = {w + ηu j : η ∈ R}. The size of the segment is ε Q j z j = εγ j . This means that the (n − j + 1)-volume of I j+1 is at least εγ j times the (n − j)-volume of I j+1 = Q j+1 I j .
Concluding, we get that the volume of I is at least n j=1 γ j . From the construction immediately preceding Proposition 5.4, we get (using the fact that n ′ = Ω(n)): The bound (5.9) tells us that the volume of uncertainty in the input (and hence, the output) of a b-speedup of FFT in the in-place model is at least b Ω(n) times the volume of uncertainty incurred simply by storing the input in memory.

Proofs
We start with some useful lemmas. Lemma 6.1. Let x, y ∈ R a for some integer a, with x 2 = y 2 = 1. Then − log a ≤ Φ(x, y) ≤ log a . (6.1) The proof is a simple done by a simple analysis of the function Φ(x, y) under the stated constraints using, say, Lagrange multipliers. Lemma 6.2. Let A, B ∈ R a×n . Let U ∈ R a×a be orthogonal. Then rs · x(j)y(j) log |rs · x(j)y By orthogonality of U , we have that a j=1 x(j)y(j) = a j=1 (U x)(j)(U y)(j). Also for the same reason we have U x 2 = U y 2 = 1. Using Lemma 6.1, we conclude Proof. Let U, V ∈ R a be orthogonal and Σ ∈ R a diagonal (and nonsingular) so that D = U ΣV .
(Such a composition exists by standard SVD theory.) as required. (We used Lemma 6.2 twice in the second inequality, and the orthogonality of U for the last derivation. The reason the middle term in the RHS of the first inequality is null is by properties of Φ that are trivial to check.) The following is the most important technical lemma in this work. Roughly speaking, it tells us that application of operators that are close to Id to the rows of F and F −T does not reduce the corresponding potential by much. Similarly, assuming that P, Q are PSD with spectral norm at most 1, applying these transformations to the rows of Id does not increase the corresponding potential by much. Lemma 6.4. Let P, Q ∈ R n×n be two matrices. LetP = Id −P,Q = Id −Q.Then If, additionally, P and Q are positive semi-definite contractions (the spectral norm of P, Q is at most 1), then The proof is deferred to Section 6.3. The bounds (6.8)-(6.9) use the smoothness of the matrices F and Id (that is, almost all matrix elements have exactly the same magnitude). This is the reason we needed to modify Φ and work with Φ C for the complex case: If F were the real representation of the n/2-DFT matrix, then it is not smooth in this sense. It does hold though that for any i ∈ [n] and j ∈ [n/2]: F (i, 2j − 1) 2 + F (i, 2j) 2 = 2/n, in other words, the matrix is smooth only in the sense that all pairs of adjacent elements have the same norm (viewed as vectors in R 2 ).

Proof of Theorem 5.1
We directly prove the less general (5.3). The more general bound (5.1) is shown similarly, but with more notation. Fix R ∈ [⌊n/2⌋]. Let m ′ be the smallest integer divisible by R satisfying m ′ ≥ m. If m ′ > m, then "pad" the algorithm A n by defining M (m+1) . . . M (m ′ ) = M (m) = F . By the triangle inequality, Combining (6.11) with (6.10), we get For any matrix A ∈ R n×n and any subset I ⊆ [n], we have A(I, : (this can be seen e.g. using the SVD theorem). Therefore, But Φ(M (m ′ ) ) = Φ(F ) = n log n and Φ(M (0) ) = 0, hence, there must exists 2Rn log n 2((n log n)/b) log 2R = Rb log 2R .

Proof of Theorem 5.3
Let V = {v 1 , . . . , v k } ⊆ R n be an orthonormal set satisfying the properties described in case (i) of the theorem. Similarly, let U = {u 1 , . . . , u ℓ } ⊆ R n be an orthonormal set satisfying the properties described in case (ii) of the theorem. We show that as long as k + ℓ is at most O(n), then we can extend one of the two sets by one element. Let P denote the projection onto (span V ) ⊥ and Q the projection onto (span U ) ⊥ . Using Lemma 6.4, we have that for some global C > 0, whereP = Id −P,Q = Id −Q (the orthogonal projections). By known properties of projection matrices, trP = P 2 F = k, trQ = Q 2 F = ℓ. Therefore, for some global C ′ > 0. This implies, using Theorem 5.1 (with R = 1) that for some t ∈ {0, . . . , m} and i ∈ [n]: Hence, as long as k + ℓ ≤ n/(2C ′ ): This implies that either M (t) P ⊥ (i, :) ≥ b/2 or that (M (t) ) −T Q ⊥ (i, :) ≥ b/2. In the former case we can extend the set V by adding v k+1 = M (t) P (i, :)/ M (t) P (i, :) , which is orthogonal to v 1 , . . . , v k by construction. In the latter case we can extend the set U by adding u k+1 = (M (t) ) −T Q(i, :)/ (M (t) ) −T Q(i, :) which is again, orthogonal to u 1 , . . . , u ℓ by construction.
This process of augmenting V and U can continue until k + ℓ ≥ n/2C ′ , which implies that either k ≥ n/4C ′ (establishing extreme overflow of the theorem) or ℓ ≥ n/4C ′ (establishing extreme underflow).
Assume k ≥ n/4C ′ and let n ′ = k. For j ∈ [n ′ ] let t j denote the time step of the overflow corresponding to direction v j ∈ R n and let i j denote the coordinate at which the overflow occurs. It is clear from the construction that i j is one of the at most two coordinates affected by the t j 'th step. We show that there exist no 1 ≤ j < j ′ ≤ n ′ such that (t j , i j ) = (t j ′ , i j ′ ). Indeed, note that M (t j ) P j ′ (i j , :) must be null by construction, contradicting the fact that . The conclusion is that for any t ∈ [m] there can be at most two indices j, j ′ ∈ [n ′ ] such that t j = t j ′ = t, and therefore the cardinality of the set {t 1 , . . . , t n ′ } is at least n/2. A similar argument is done for the extreme underflow case, concluding the proof.
For A, we just need to notice that: We now bound B.
This concludes the proof of (6.8).

Future Work
Taking into account bit operation complexity, and using state-of-the-art integer multiplication algorithms [8,9] it can be quite easily shown that both severe overflow and severe underflow could be resolved by allowing flexible word size, accommodating either large numbers (in the overflow case) or increased accuracy (in the underflow case). In fact, allowing O(log b)-bit words at the time steps at which overflow (or underflow) occur, of which there are Ω(n) many by Theorem 5.3, suffice. Hence, this work does not rule out the possibility of (in the extreme case of b = Θ(log n)) a Fourier transform algorithm in the in-place model using a linear number of gates, in bit operation complexity ofΩ(n log log n), whereÕ() here hides log log log n factors arising from fast integer multiplication algorithms . We conjecture that such an algorithm does not actually exist, and leave this as the main open problem.
Another problem that was left out in this work is going beyond the in-place model. In the more general model, the algorithm works in space R ℓ for ℓ > n, where the (ℓ − n) extra coordinates can be assumed to be initialized with 0, and the first n are initialized with the input x ∈ R n . The final matrix M (m) of Fourier transform algorithm A n = {Id = M (0) , . . . , M (m) } contains F as a sub matrix, so that the output F x can simply be extracted from a subset of n coordinates of M (m) x, which can be assumed to be the first. The matrix M (m) (and its inverse-traspose) therefore contains (ℓ − n) extra rows. The submatrix defined by the extra rows (namely, the last ℓ − n) and the first n columns were referred to in [2] as the "garbage" part of the computation. To obtain an Ω(n log n) computational lower bound in the model assumed there, 6 it was necessary to show that Φ P,P (M (m) )P = Ω(n log n), where P ∈ R ℓ×ℓ is projection onto the space spanned by the first n standard basis vectors. 7 To that end, it was shown that such a potential lower bound held as long as spectral norm of the "garbage" submatrices was properly upper bounded. That result, in fact, can be deduced as a simple outcome of Lemma 6.4 that was developed here. What's more interesting is how to generalize Theorem 5.3 to the non in-place model, and more importantly how to analyze the numerical accuracy implications of overflow and underflow to the non in-place model. Such a generalization is not trivial and is an immediate open problem following this work.
The closing question of Section 5 is another avenue of possible research stemming from this work, and seems (to the author) as an achievable goal in the quest to solve the half decade old problem of understanding the complexity of Fourier transform. In view of this work and of the preceding [1,2], it seems that the correct way to understand the hardness of this important transformation is by way of trading off time versus accuracy, for a given machine architecture.
Another interesting possible avenue is to study the complexity of Fourier transform on input x for which some prior knowledge is known. The best example is when F x is assumed sparse, for which much interesting work on the upper bound side has been recently done by Indyk et al. (see [10] and references therein).
Many algorithms use the Fourier transform as a subroutine. In certain cases (fast polynomial multiplication, fast integer multiplication [8,9], fast Johnson-Lindenstrauss transform for dimensionality reduction [3,4,5,11] and the related restricted isometry property (RIP) matrix construction [14,6,11]) the Fourier transform subroutine is the algorithm's bottleneck . Can we use the techniques developed here to derive lower bounds (or rather, time-accuracy tradeoffs) for those algorithms as well? Moreover, we can ask how the implications of speeding up the Fourier transform subroutine (as derived in this work) affect the numerical outcome of these algorithms, assuming they insist on using Fourier transform as a black box.