( ■ (T^ T 1-H O^ ITQ d Dh co" . (D e - p ai Ol t-H ■ © ' T-l (tì O U 1 .s Volume 19 Number 3 September 1995 ISSN 0350-559^ Informatic An International Journal of Computìn and Informatics Guest Editor: Johann Eder Concurrent Software with Redundancy Self-Learning Fuzzy Rules Scheduhng Parallel Tasks Object-Oriented Database Language Hot Living Systems Informational Calculus The Slovene Society Informatika, Ljubljana, Slovenii f '1 "»--=1 i I \ -Jr J: Informatica An International Journal of Computing and Informatics Basic info about Informatica and back issues may be FTP'd from ftp.arnes.si in magazines/informaticalD: anonymous PASSWORD: FTP archive may be also accessed with WWW (worldwide web) clients with URL: http://www2.ijs.si/"mezi/infonnatica.html Subscription Information: Informatica (ISSN 0350-5596) is published four times a year in Spring, Summer, Autumn, and Winter (4 issues per year) by the Slovene Society Informatika, Vožarski pot 12, 61000 Ljubljana, Slovenia. The subscription rate for 1995 (Volume 19) is - DEM 50 (US$ 35) for institutions, - DEM 25 (US$ 17) for individuals, and - DEM 10 (US$ 7) for students plus the mail charge DEM 10 (US$ 7). Claims for missing issues will be honored free of charge within six months after the publication date of the issue. BT^X Tech. Support: Borut Žnidar, DALCOM d.o.o.. Stegne 27, 61000 Ljubljana, Slovenia. Lectorship: Fergus F. Smith, AMIDAS d.o.o., Cankarjevo nabrežje 11, Ljubljana, Slovenia. Printed by Biro M, d.o.o., Žibertova 1, 61000 Ljubljana, Slovenia. Orders for subscription may be placed by telephone or fax using any major credit card. Please call Mr. R. Murn, Jožef Stefan Institute: Tel (+386) 61 1773 900, Fax (+386) 61 219 385, or use the bank account number 900-27620-5159/4 Ljubljanska banka d.d. Slovenia (LB 50101-678-51841 for domestic subscribers only). According to the opinion of the Ministry for Informing (number 23/216-92 of March 27, 1992), the scientific journal Informatica is a product of informative matter (point 13 of the tariff number 3), for which the tax of traffic amounts to 5%. Informatica is published in cooperation with the following societies (and contact persons): Robotics Society of Slovenia (Jadran Lenarčič) Slovene Society for Pattern Recognition (Franjo Pernuš) Slovenian Artificial Intelligence Society (Matjaž Gams) Slovenian Society of Mathematicians, Physicists and Astronomers (Bojan Mohar) Automatic Control Society of Slovenia (Borut Zupančič) Slovenian Association of Technical and Natural Sciences (Janez Peklenik) Informatica is surveyed by: AI and Robotic Abstracts, AI References, ACM Computing Surveys, Applied Science & Techn. Index, COMPENDEX*PLUS, Computer ASAP, Cur. Cont. & Comp. & Math. Sear., Engineering Index, INSPEC, Mathematical Reviews, Sociological Abstracts, Uncover, Zentralblatt für Mathematik und ihre Grenzgebiete. The issuing of the Informatica journal is financially supported by the Ministry for Science and Technology, Slovenska 50, 61000 Ljubljana, Slovenia. Reliability Optimization of Concurrent Software with Redundancy Jie Wu and Kejun Yao Department of Computer Science and Engineering Florida Atlantic University Boca Raton, FL 33431 Keywords: concurrent systems, fault tolerance, fault-tree, software reliability Edited by: Johann Eder Received: February 22, 1995 Revised: July 30, 1995 Accepted: September 7, 1995 We consider in this paper an optiniization naodel of concurrent software with redundancy. The software fault-tolerance technique used is conversation, a special mechanism for concurrent systems. Two optimization models are combinatorial model and fault-tree model which calculate system reliability based on the same method but under different fault assumptions. These two models are illustrated by examples. 1 Introduction With the increasing complexity of computer systems and importance of performing intended functions in critical tasks, such as nuclear plant control, defense systems, and automated factories, the dependability of these systems becomes essential. Dependability [8] is defined as the ability of a system or product to deliver its intended level of services to its users, especially in the lights of failures or other incidents that impinge on its level of serve. Dependability is a high-level framework that encompasses several measures including reliability. Fault prevention and fault tolerance are two complementing strategies for achieving reliability. A fault-tolerant system is one that can continue to correctly perform its specified tasks in the presence of hardware or software faults. Fault tolerance is usually achieved by means of redundancy [6]. Hardware fault tolerance and software fault tolerance in sequential systems have been extensively studied, however, software fault tolerance in concurrent systems has not been exploited much. The conversation [9] is a special software fault tolerance construct for concurrent systems. A conversation involves two or more processes, as it constitutes a boundary to prevent possible error propagation to eliminate the domino effect [9]. Identification of a set of conversations in a given systems has been discussed by Wu and Fernandez [11] using Petri nets and by Tyrrell and Carpenter [10] using CSP. The potential practical value was shown in a 3-year experiment conducted at the University of Newcastle during 1982-1984. However, there are still important practical problems that remain to be solved. For example, under a given cost, how to construct one or several conversation to achieve a maximum reliability? The optimal structure for software reliability models was initially proposed by Belli and Je-drzejowice [2], which involves application of the existing reliability predictions, evaluation of the amount of resources needed to develop and implement a system, and calculation of the optimal sequential software structure. This scheme was extended later in Zhang's reliability model [12]. However, the software fault tolerance schemes considered in BeUi's model and Zhang's model are for sequential systems only. Software fault tolerance schemes for concurrent systems, such as the one using conversation, have not been studied for optimization. In this paper, we extend the optimization model proposed by Belli and Jedrzejowice by considering the following problem: Select a set of software versions to construct one or multiple conversation such that the system has a maximum reliability while the total system cost is bounded by a given value. Normally, different reliability results are obtained by using different fault assumptions. We study the combinatorial model and the, fault- tree model which are based on. the same method but under different fault assumptions. The paper is organized as following: Section 2 describes the mechanism of conversation. Section 3 studies the combinatorial model. Section 4 proposes the fault-tree model. Section 5 concludes the paper. 2 Conversation The conversation is a language construct which is a generalization of the recovery block scheme [5] in a concurrent system. A conversation defines an atomic action for a set of communicating processes. Two conversations are either nested or independent. The boundaries of a conversation consist of a recovery line, a test line and two side walls. A recovery line is a set of recovery points which are established before any process communication. A test line is the correlated set of the acceptance tests of the interacting processes. Two side u)a//s prevent the processes within a conversation from interacting with processes outside the conversation. A conversation is successful only if all its processes pass their acceptance tests at the test line. If any acceptance test fails, all the processes within the conversation go back to the recovery line, restore the previous state by replacing necessary variables with the ones saved in the recovery points, and retry using their alternate try versions. The structure of conversation is shown in Figure 1, where it is assumed that there are pj parallel processes in one conversation that have the same number of versions. A version, a sequence of instructions, consists of two parts. The first part is a sequence of instructions called the function segment. The second part is the test segment. The role of the test segment is to test the result of various versions in sequence and to accept (or reject) them. The test segment is also subject to failures. The failure of the test segment means that it either judges the correct result of a version as incorrect or judges the incorrect result of a version correct. If the computation result in the ith version of any process is rejected then every process's initial state is restored, and its (i l)th version is activated and performed. A fault-tolerant concurrent system consists of a set of special objects which are conversations and a set of regular objects where no fault-tolerance mechanism is applied. Since the correct execution of the whole system depends on the correct execution of each object, the reliability model of the system could be defined as objects connected in series. Basically, there are four different types of errors that can occur in a conversation structure [7]. A Type 1 error occurs when any process version produces an incorrect result, but the acceptance test labels the result as correct. As a Type 2 error, the final version produces a correct result, but the acceptance test erroneously determines that the result as incorrect. A Type 3 error occurs when the recovery mechanism can not successfully recover the input state of the previous version in preparation for executing another version, or it can not successfully execute the next version. Finally, a Type 4 error occurs when the last version produces an incorrect result even though the test segment correctly judges it. In our models, we don't consider Type 3 error. We assume that the recovery mechanism can recover the previous state successfully aU the time. We focus on finding a set of versions such that the system has the maximum reliability under a given cost. Different reliability results can be obtained by using different fault assumptions. Here, we study two models which are based on the same method but under two different fault assumptions. The first model is a combinatorial model which considers only Type 2 and Type 4 errors. The second model is a fault-tree model which concerns with only Type 1, Type 2 and Type 4 errors. The combinatorial reliability model used in this paper is based on the following assumptions: 1. All software failures are independent. 2. The total system cost is equal to the sum of the costs of all the objects. 3. All the software version reliabilities and costs are known. 4. Reliabilities of test segments are known as the probability that the error is detected if it occurs. The fault-tree model also use the above assumptions 1, 2 and 3. But the assumption 4 is different: 4'. Failure probability of each test segment has two parts: the probability that the test segment recc^ery line side walls Vj Vj Vj M \ \ \ \ Pj process ■ version conversation test line Figure 1: Structure of a conversation I I function segment test segment judges a correct result as incorrect and the probability that it judges an incorrect result as correct. The following notation is introduced: Number of independent conversations (j is used as index for conversation) Number of software versions in the jth conversation {i is used as index for version) Number of processes in the jth conversation {k is used as index for process) Amount of cost needed for the ith version in the k process of the jth conversation Reliability of the jth conversation System reliability Specified cost Pi fk Rj Rs C J« Reliability of the function segment of the ith version in the /sth process of the jth. conversation Reliability of the test segment of the Jth version in the A;th process of the jth conversation (probability that an error is detected when it occurs) Using the combinatorial model, we can derive the reliability of the jth conversation as follows: Rj — I'jjtji i=i Pj rji k=i ■Pi k=i 3 Combinatorial Model The following is notation used in the combinatorial model: Pj pj(i+i) = - E k=i (1) (2) (3) (4) where pji = 1, pji denotes the probability that the ith path in the jth conversation is executed. There is only one possible condition under which A B B A (a) (b) Figure 2: A pair of conversations, (a) independent, (b) nested the {i + l)th version wiU not be activated. That happens when aU the function segments in the ith versions of all the processes set their correct results, and test segments judge them as correct. (To simplify the calculation, we don't consider here the Type 1 fault condition which has a relative small possibility: the function segment fails and the test segment judges the incorrect result as correct.) r-j,- is the reliability of the ?th version of aU the processes in the jth conversation, and tji is the possibility that all the test segments in the ith version of all the processes of the jth conversation judge their correct results as correct. Usually, there are more than one conversation in a fault-tolerant system. In these case, for any pair of conversations, they are either independent or nested. As in Figure 2, conversations A and B are independent in Figure 2(a), while A is nested within B in Figure 2(b). First, we examine systems with only independent conversations. In such a system, the system structure can be partitioned into a set of special objects (conversations) together with a set of regidar objects (without using conversations). Each regular object can also be considered as a special conversation with one software version for aU the participating processes. Therefore, the reliability model of a system with q conversations is equivalent to the one for serial system of q objects. The system reliability Rg can be expressed as follows: R. j=i (5) Rj is the reliability of the jth object (special or regular), I < j < q. When there are nested conversations in the system, to simplify the calculation, we first consider a case in which one conversation is nested within another conversation. In Figure 2(b), conversation A is nested within conversation B. Obviously, if conversation A fails, then the conversation B also fails (if conversation A fails, as part of con- J 1 2 Pj rl?. I 'k 3 0.85 0.85 0.85 10 10 10 0.8 0.8 0.8 2 0.88 0.88 12 12 0.7 0.7 Table 1: Failure probabilities and costs for a system with two independent conversations Cost 3 -- 2.5 -- 2 -- 1.5 -- 1 -- 0.5 -- Reliability (2, 3) (2, 5) (3, 3) (3, 5) (4, 3) (4, 5) (5, 3) (5, 5) (vl, v2) Figure 3: Costs/reliabilities of the combinatorial model Versions versation A, conversation B never gets the correct result). So the system reliability for this case is: subject to: Rs RaRb' (6) (8) where R^ is the reliability of conversation A, and Rgi is the reliability of the part included in conversation B but is excluded in conversation A. Equations(l)-(5) are stiU suitable in the reliability calculation of nested conversations; however, r^-and tj^ in conversation B should be changed to r'j''- and t'J'i in calculating R^i, which are: 4 Reliability of the function segment (which is not included in conversation A) in the ith version of the fcth process in the jth conversation. Reliability of the test segment (which is excluded in conversation A) in the ith version of the fcth process in the 7th conversation. Hence, the software optimization problem becomes: q Vj ' j=lt=l The optimal solution is obtained by solving the nonlinear programming problem defined in (7) and (8). However, there is a heuristic method [13] that solves this problem. As an example, we consider a system consists of two conversations. Component reliabilities and their costs are given in Table 1. For the sake of simplicity, we assume that reliabilities of function segments and testing segments of different processes in each conversation are identical. Also the cost of each path in the same conversation is identical. The results of different version combinations from (2, 2) (the first number represents the number of versions in the first conversation, the second number represents the number of versions in the second conversation) to (5, 5) are obtained from expression (7) and are shown in Figure 3 and Table 2. Assume that the specified cost is 200, we can obtain the optimal result from those sets of versions (shown in Table 2) which have the cost below 200. Obviously, the optimal structure is: 112=3, ižs=0.653 as shown in Figure 4. Xi O « tì ò.....o pj pj Xi: function segment fails or test segment judges the correct result as incorrect in any process among the Pj processes Xi Si Xi: the ith version fails which activates the (i+l)th version. Si: in the (i-f-l)th version, the function segment fails and the test segment judgs the incorrect result as correct which causes the system failure. Figure 5: Fault-tree diagram of two types of failures in the jth conversation (vl, v2) (2, 2) (2, 3) (2,4) (2, 5) (3,2) (3,3) (3,4) (3,5) Rs 0.387 0.465 0.494 0.548 0.488 0.574 0.622 0.689 C 108 132 156 180 138 162 186 210 (vi, v2) (4, 2) (4, 3) (4, 4) (4, 5) (5, 2) (5, 3) (5,4) (5, 5) Rs 0.554 0.653 0.706 0.783 0.608 0.716 0.776 0.859 C 168 192 216 240 198 222 246 270 Table 2: Rs and C under different conversation configurations in the combinatorial model vl=4 v2=3 Figure 4: The optimal structure of the example in Table 1 4 Fault-Tree Model The overall design goal of fault-tolerant software can be briefly stated as preparing for the unexpected. Unfortunately, even in principle, there is no way to anticipate aU the problems that wiU be encountered. However, in designing fault-tolerant software, one can have a conception of the general classes of failures that can occur. Review of the fault-tolerant aspects of the software is facilitated by the use of the trees: failures that are covered are explicitly listed; uncovered failures do not appear. Fault-tree [4] is such a model used as means of identifying these classes of faults in a top-down fashion. The basic notation used in a fault-tree is listed in Figure 5. The idea is that a top event is broken into several low (or simple) events that are characterized as a "yes/no" occurrences. These low events are linked together by AND or OR gates. System probability can be calculated by combining probabilities of the lower events based on the types of linkage: addition in the case of an OR gate; multiplication in the case of an AND gate. Therefore, conceptually the combinatorial and the fault-tree models are the same. To facilitate the discussion, we illustrate the fault-tree model by including the Type 1 error. Let the following symbols denote probabilities of the basic event: n; Fi Probability that the functioning segment in the ith version of the fcth process in the jth conversation has failed Probability that the test segment in the ith version process of the A;th process in the jth conversation judges the incorrect results as incorrect Probability that the test segment in the ith version of the /cth process in the jth conversation judges the incorrect results as correct Failure probability of the jth conversation The parameters such as j, Uj, i, pj, k are the same as in the combinatorial model. There are two types of failure which will cause the system failure. The first one is that the function segment fails or the test segment judges the correct results as incorrect in each version. The illustration of this failure in fault-tree model is shown in Figure 5(a) named as Xi. The other one is that the function segment or test segment of the j'th version fails which activates the (i-F l)th version, then the function segment of the {i + l)th stiU fails, and the test segment of the (i + l)th version judges the incorrect result as correct. The fault-tree diagram of the {i l)th failure is shown in Figure 5(b) named as Si. Therefore, we can easily PF FI A EZ3 xi ra Si F2 Xi □ Eä EZ3 1 2 Vj fi? '' 20 Övj raESBÈS......EZS ^ 1 1 2 12 Figure 6; Tlie fault-tree diagram of tlie ^Jj-versioii conversation Vj i 1 2 Pj rh. i' r ■■ S 3 0.15 0.15 0.15 10 10 10 0.18 0.18 0.18 0.02 0.02 0.02 2 0.12 0.12 12 12 0.22 0.22 0.08 0.08 Table 3: Failure probabilities and costs for a system with independent conversations obtain the fault-tree diagram of the Ujth version conversation as shown in Figure 6. The failure probability of the system consists of two parts. Fl is caused by the Xi failure, which represents that the function segment fails or the test segment judges the correct result as incorrect in each version. F2 is caused by the failure of Si, which represents that the function segment fails and the test segment judges the incorrect result as correct and the next version is not activated. Fj = F1 + F2-F1*F2 (9) Fl can be obtained by the following equations: k=i k^ii>k i-iy^-' n (12) fc=l Vi Pj Pj Mi = - n m^-.-) + ... + k=i k=i t>k Pj i-iy^-' n (13) A—1 F2 can be obtained by the following equations: t=i t=i ;>i i=i (14) n = (15) i; = 5/nxKi>i) (16) 1=1 Pj Pj Pj Si = Zjk - Y1 m^ik nZii + ...+ k=l k=ll>k «=n i=l Xi = E i -t- Mi -Ei* Mi (10) (11) kzzl Zik = e% * n% Rj = l- Fj (17) (18) (19) Cost Reliability —Đ reliability —o- - cost/100 0.5 -- -\-1-:-1-1-1-1-1-1-^ (2, 3) (2, 5) (3, 3) (3, 5) (4, 3) (4, 5) (5, 3) (5, 5) Versions (vl, v2) Figure 7: Costs/reliabilities of the fault-free model (vl, v2) (2,2) (2, 3) (2,4) (2,5) (3,2) (3,3) (3,4) (3,5) Rs 0.424 0.493 0.531 0.603 0.521 0.606 0.652 0.741 C 108 132 156 180 138 162 186 210 (vl, v2) (4, 2) (4, 3) (4, 4) (4, 5) (5, 2) (5, 3) (5, 4) (5,5) Rs 0.585 0.680 0.731 0.831 0.674 0.801 0.863 0.980 C 168 192 216 240 198 222 246 270 Table 4: Rg and C under different conversation configurations in the fault-tree model Ra = Y[ (20) Hence, the software optimization problem is: max Vi UR. subject to: j=i i=i (21) (22) We use the same example as used in the combinatorial model and provide a set of parameters as shown in Table 3. According to the above equations, we can obtain reliabilities of different version combinations from (2, 2) to (5, 5) as shown in Table 4. As the specified cost is 200, we can get the optimal result: vi = 4, V2 = 3,Rs = 0.68. The results are also shown in Figure 7. 5 Conclusion In this paper, we have studied the reliability optimization problem in concurrent software with redundancy using heuristic methods. The models presented in this paper show that it is possible to formulate and solve a particular reliability optimization problem. The combinatorial model and the fault-tree model have been used, which are based on the same method, but are illustrated by using different fault assumptions. The combinatorial model is more convenient to calculate, while the fault-tree model can be clearly illustrated by the fault-tree diagram. The next steps in the development, of reliability optimization models can lead toward incorporating the effect of correlated errors [3] on reliability models. References [1] Avizienis, A., The n-version approach to fault-tolerant software, IEEE Transactions on Software Engineering, Vol. 11, No. 12, Dec 1985, 1491-1501. , [2] BeUi,F and P. Jedrzejowicz, An approach to the reliability optimization of software with redundancy, IEEE Transactions on Software Engineering, Vol.17, No. 3, Mar.1991, 310312. [3] Eckhardt, Jr., D. C. and L. D. Lee, A theoretical basis for the analysis of multiversion software subject to coincident errors, IEEE Transactions on Software Engineering, Vol. 11, No. 12, Dec. 1985, 1511-1517. [4] Hecht, H. and M. Hecht, Fault-tolerant software. Fault-tolerant Computing: Theory and Techniques, Vol. 27, D.K. Pradham, ed. Prentice-Hall, 1986. [5] Horning, J. J., H. C. Lauer, P. M. Melliar-Smith, and B. RandeU, A program structure for error detection and recovery, Proc. Conf. Operating System: Theoretical and Practical Aspects IRIA, Apr. 1974, 177-193. [6] Johnson, B.W., Design and Analysis of Fault-Tolerant Digital Systems. Addison-Wesley Publishing Company, Inc. 1987. [7] Scott, K. R. and J. W. Gault, Fault-tolerant software reliability modeling, IEEE Transactions on Software Engineering, Vol. 13, No.5, May 1987. [8] Laprie, J.C., Dependability: A unifying concept for reliable computing and fault-tolerance. Dependability of Resilient Computers. T. Anderson, ed, BSP Professional Books, 1989,1-28. [9] RandeU, B., System structure for fault tolerance. IEEE Transactions on Software Engineering. Vol. 1, No. 6, June, 1975, 220-232. [10] Tyrrell, A. M. and G. F. Carpenter, CSP methods for identifying atomic actions in the design of fault tolerant concurrent systems, IEEE Transactions on Software Engineering, Vol. 21, No. 7, July 1995, 629-639. [11] Wu, J. and E. B. Fernandez, Using Petri nets for the design of conversation boundaries in fault-tolerant software, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 10, Oct. 1994, 1106-1112. [12] Wu, J., Zhang, M. and E. B. Fernandez, Design and Modeling of Hybrid Fault-Tolerant Software with Cost Constraints, accepted to appear in the Journal of Systems and Software. [13] Zhang, M., Design and Modeling of Hybrid Fault-Tolerant Systems. Master's Thesis. Florida Atlantic University, Boca Raton, FL., 1992. An Algorithm for Self-Learning and Self-Completing Fuzzy Control Rules Xiaozhong Li and Shuo Bai National Research Center for Intelligent Computing Systems(NCIC) P. 0. Box 2704, Beijing Beijing 100080. P. R. C Faoc: 86-10-2541342, Tel:86-10-2534642 email:{lxz, bai}@tango.ncic.ac.cn AND Zemin Liu Beijing University of Posts & Telecommunications Keywords: self-learning, self-completing, fuzzy control Edited by: Johann Eder Received: December 12, 1994 Revised: June 30, 1995 Accepted: September 8, 1995 In this paper, we introduce a method of generating control rules for fuzzy logic controllers, called an algorithm of self-learning and self-completing (ASLSC). This method can learn to generate rules from the sample data with the unsupervised competitive learning (UCL) of the neural network. If a rule table generated is not full, the ASLSC method can fill those blanks in the rule table with proper rules. Besides, ASLSC can determine automatically the universes of discourse of fuzzy variables. The simulations on an inverted pendulum system and the experiments on temperature controlling of an industrial electric heating ring show that ASLSC is practicable and effective. 1 Introduction and trapezoid-shaped functions. The real diffi- culties are the tasks (1) and (2). Since E. H. Mamdani and S. Assilian first imple- As to (1), usually at first, one must determine mented afuzzy controller in 1974 [5], fuzzy control the universes of discourse (intervals) of fuzzy va-technology has been widely used and developed riables empirically, and then begin to try and because of its strong robustness and insensibility adjust it to get a "better" interval. There is to environmental parameters and short settling not a common way to get it directly. As to (2), time. However, the fuzzy control theory itself is there has been much work on the choice of lin-not perfect, yet, and many aspects rely on the guistic control rules in the literature [6]-[13][17]. experience of an expert or a skilled operator, for But recently, some fusion techniques have attrac-example, (1) selection of a universe of discourse or ted people's attention, such as NN fuzzy and GA an interval of a fuzzy variable; (2) determination fuzzy [1][4][16][18]. An early and typical work of fuzzy control rules; (3) selection of membership is the Bart Kosko's book "Neural Networks and functions. In order to do those tasks, continuous Fuzzy Systems", which describes a method of trial and tuning are necessary. Therefore, fuzzy adaptive FAM-rule generation system (abbrevi-control technology has been hindered to some de- ated as MFAM in this paper) [1]. Our algori-gree from gaining wider application and dissemi- thm of self-learning and self-completing (ASLSC) nation. As to (3), generally, it is not a true knotty to be introduced in this paper is mainly based problem which wiU be encountered in designing on MFAM and the parametric functions method fuzzy controUers(FCs), because in most cases it [14]. It is composed of three sub-algorithms; that is enough to solve the problem with membership is, an algorithm for generating universes of disfunctions of fixed form, such as triangle-shaped course (AGUD), and an algorithm for generating Figure 1: A diagram of a dual control system control rules (AGCR), and an algorithm for completing control rules (ACCR). Each sub-algorithm may be used as an independent one. So we may introduce them separately. Because AGCR is an important postulate in this paper, we wiU first discuss it in Section 2. Section 3 will introduce ACCR, and Section 4 wiU introduce AGUD and ASLSC. Section 5 wiU report the simulation results from an inverted pendulum and Section 6 wiU report the experimental results from an industrial electric heating ring. Finally Section 7 wiU discuss some other related problems. 2 AGCR The basic idea of AGCR is to make the division of the input and output spaces crisp, and cluster aU sample data with a kohonen network, and count the number of weight vectors in each crisp subspace, and the middle rule among the incompatible rules is selected. Before describling the AGCR algorithm, we make some technical assumptions. Suppose that the control system is a dual control system(the plural is similar) as shown in figure 1 in which R represents the fuzzy controller with two input variables X and Y and an output variable Z, the rules have the following form: if X is Ai and Y is 5,-, then Z is Ci, or {Ai, Bi] Ci) for short (1) where X, Y, Z have dual meanings on notation, and they are viewed as the universes of discourse and fuzzy variables. Fuzzy variable X assumes fuzzy-set values Ai,A2,...,Am, and fuzzy variable Y assumes fuzzy-set values B\,B2,- ■ .,Bn, and fuzzy variable Z assumes fuzzy-set values C I, C2,..., Cp, where Ai, Bj, C k are linguistic values, such as positive large, negative smaIL,etc.. For clarification, we often assume m = n = p = 7 output lay input layer Figure 2: An adaptive clustering network and the linguistic values set consists the following seven fuzzy sets: Al = Bi = Ci = NegativeLarge{N L) = = C2 = NegativeMiddle{NM) A3 = B3 = C3 = NegativeSmall{NS) A4 = 54 = C4 = Zero{ZE) As^B^^Cs^ Positivesmall{PS) Ae = Be = C6 = PositiveMiddle{PM) A-! — Bj = Ct = PositiveLarge{PL) Suppose the input space X and Y are the real intervals [Xi,Xr] and [y;,yr], respectively, and the output space Z is the real interval [Zi,Zr]. We also assume we have a known sample data set: {s(i) = {xi,yi,Zi)\xi e [Xi,Xr],yi 6 [Yi,Yr],Zi G [Zi,Zr],i = 1,2, ...,iV} where N is the total number of aU sample data and N ^ m x n x p. To get the fuzzy control rule table from the sample data set, at first, a two-layer network which has 3 input nodes and m X n X p output nodes must be made, as shown in figure 2. It is a kind of kohonen's adaptive clustering network, whose purpose is to cluster the sample data set, so the number of input nodes is equal to that of components of a sample datum, i.e. 3 here. Because a cluster corresponds to a fuzzy control rule and the most of rules is m X n X p, the number of output nodes is certainly m x n x p. On the other hand, like [1], the membership functions here are assumed to have fixed shape. For instance, we assume in this paper they have the forms of symmetrical triangle-shaped functions shown in figure 3. One of the advantages of choosing such membership functions is that, to any point in the universe of discourse, a fuzzy set always exists to make the membership degree of the point belonging to the fuzzy set greater than or equal to 0.5. NL NM .NS Z E PS PM PL 0.6 \/ \/ \ a 0 a Figure 3: Membership functions have the forms of symmetrical triangle-shaped functions NL NM NS PS PM PL -a NL NM NS ZÈ PS PM PL a Figure 4: According to the "0.5 partition principle" to partition [-a, a] into 7 intervals With the preparation above, we describe AGCR as follows: - Step 1. Partitioning the universes of discourse (or the input and ouput spaces) This step is to make the division of the input and output spaces crisp. We present a principle of partitioning that the point whose membership degree belonging to a fuzzy set is greater than or equal to 0.5 should be included into the corresponding interval. For instance, to the case of figure 3, the diagram of partitioning is shown in figure 4. We call it the "0.5 partition principle". - Step 2. Training the samples set with unsupervised competitive learning(UCL) The purpose of this step is to cluster the sample data set. Here we don't use differential competitive learning(DCL) which is always used in [1], because we have proved that UCL possesses faster speed in computing and occupies less memory than DCL [15]. - (1) Initialize the weight vectors Wi(0) = s{i), i= 1,2,..., m X nxp. - (2) For additional random sample s{t), find the closest ("winning") weight vector Wj(^): ||wj(0-s(i)|| = mjn||wi(0-s(0|| (2) where ((wjp = wf + w^ + w^ gives the squared Euclidean norm of w. - (3) Update the winning weight vector(s) I Wj(t+ 1) = Wj(i) + c,[s(i) - Wj(<)] |wi(f-f-l) =Wi(/), if i^j (3) where {cj defines a slowly decreasing sequence of learning coefficients. For instance, ct = 0.1[1 - (f/1000)] for 1000 samples s(t). Step 3. Generating rules After step 2, all sample data have been clustered to mx nxp clusters whose centers are those m X n X p weight vectors respectively. This step is to count the number of the weight vectors in each crisp sub-space and generate rules with a weight preliminarily. - (1) Initialization Pijk = O.tjT = l,i = l,2,...,m.i = - (2) To aU weight vectors Wq{s),q = l,2,...,m X n X p,Wq = ' Pijk = Pijk + 1, if w] e e Bj, Pijk = Pijk, w^^eCk else (4) where pijk indicates the number or the frequency of all the weight vectors Wq{s){q ~ 1,2,..., m X n X p) falling in the cuboid composed of {Ai,Bj,Ck) in R^. We double up on notation and view Ai^Bj and C k as fuzzy variables as weU as intervals. - (3) li pijk 0, then.rule {Ai,Bf,Ck) exists, and Ai,Bj and C k are three fuzzy sets. The weight of this rule is where Pijk T ' T=j:Pijk (5) (6) The rule {Ai,Bj-,Ck) can also be considered as a mapping [14]: ip: Xxy-^2 (7) 6I\Ö NL NM NS ZE PS PM PL NL PL PL PL PL PS PS ZE NM PL PL PL PM ZE ZE NS NS PL PL PM PS ZE NS NM ZE PL PM PS ZE NM NL PS PZ ZE ZE NS NM NL NL PM ZE ZE NS NM NL NL NL PL ZE ZE NS NL NL NL NL where X,y,Z is the linguistic values sets for the variables X,Y and Z, respectively, and X = y = and 2 = {Ci,C2,.. So the mapping (7) can be represented as Pijk^ > then (Ai,Bj\Cki) i® t^® o^^ly o®^® that should be selected, else (A,-, Bj; Cki) is the only one that should be selected. We call the technique above the "selecting the middle rule (SMR)". 3 ACCR In the simulation results of AGCR to be introduced later, it always occurs that some rules are absent in the last rule table. For example. Table 1 misses a rule, i.e., (PS, ZE; 00), where "00" represents this rule is absent or lost. Absence of a rule will affect controlling. How can this problem be solved? PENG Xian-Tu [14] had proposed a method of generating rules by functions, such as by linear functions, but a linear function must be a monotonie function. It means that the monotonicity exists in a rule table. We also find this hidden law in many other cases, and we wiU use it to solve the above problem. This method is called ACCR which always assumes the rule table is monotonie. For example, returning to table 1, if we regard NL, NM, NS, ZE, PS, PM and PL as 1, 2, 3, 4, 5, 6 and 7, respectively, we can find the monotonie tendency decreasing from the upper-left corner to the lower-right corner, and in a row from left to right, and in a column from up to down. Then, for the blank in table 1, we can guess it might be NS. Hence, in the case that some rule is absent, we should observe the rules on it's left and right and up and down, and fiU a proper rule according to the monotonicity law. This is the very idea of the "self-completing". For example, if the linguistic values sets A" = y = Z = {NI, NM, NS, ZF, FS, FM, FL}, then the rule table has at most 49 rules. i,From (8), any rule may be represented as (p{Ai,Bj) = where f is a function of the form /:{1,2,...,7}X{1,2,...,7}^{1,2,...,7}. Additionally, we assume f{i,j) = 0, if the rule whose antecedent is Ai and Bj is absent. Then an special ACCR may be summed up as the following. We view ACCR as a method which makes a rule table complete, not only a specific algorithm. - Let /(l,l) = 7,/(4,4) = 4,/(7,7) = l. - For Vi,i,l < i<4,2 0, then f{i,j) = f (i J + 1) = f{i, j-I), else iif(i,j+l) > 0, then let f(i,j) = min((/(z,i-M)1), 7). - For Vi,i,2 < i < 3,1 < i < 4,f{i,j) = 0, if f{i - = fii + l,i) > 0, then f{i,j) = fii + l,j) = /(«■-!,;■)> else if f{i + l,j) > 0, then let f{i,j) = min{{f{i+l,j)+l),7). - For Vi,i,4 < i <7,5 < j < 6,/(i,j) = 0, if fii, j - 1) = fii J + 1) > 0, then fii,j) = fii, 3 + 1) = fii, j - 1), else if fii, j - 1) > 0, then let /(i,i) = max((7(i,i - 1) - 1), 1). - For Vi,j,5 < i < 6,4 < j < 7, fii, j) = O, if fii - l,j) = fii + l,j) > 0, then fii,j) = fii + l,j) = fii-l,j), else iffii-l,j) > 0, then let /(i, j) = max((/(i - 1,;) - 1), 1). - For Vi, J, 1 < I < 3,5 < i < 6, fii, j) = 0, if fii, j - 1) > fii, j + 1) > 0, then fii,j) = fii, j - 1) - 1, if fii, j - 1) = fii, j + 1) > 0, then fii,j) = fii, j - 1) = fii, j 4-1). - For Vi, J, 2 < i < 3,5 < j < 7, fii, j) = O, if fii - l,j) > fii + l,j) > 0, then fii,j) = fii -l,j)-l, if fii - 1, j) = fii l,j) > 0, then fii,j) = fii - l,j) = fii + l,j). - For Vi,i,5 fii, j -M) > 0, then fii, j) = fii, j - 1) - 1, if fii, j - 1) = fii, j + 1) > 0, then /(i,i) = /(i,i-l) = /(i,j + l). - For Vi,i, 5 < i < 6,1 < i < 3,/(i,i) = O, if /(i - l,j) > fii + l,j) > O, then fii, j) = /(i - l,j) - 1, if fii -l,j) = fii + l,i) > O, then /(i,i) = /(i-l,i) = /(i + l,i). - For Vi,j,l < i < 7,1 < i < 7, if fii, j) = 1, for Vi',;', i < i' < 7, j < j' < 7, then - For Vi,i,l < i < 7,1 < j < 7, if fii,j) = 7, for Vi',i',l < i' < i, 1 < f < j, then fii',j') = 7. 4 AGUD and ASLSC In many methods, including the MFAM, it is necessary to know each universe of discourse of each fuzzy variable beforehand. However this is difficult, because we do not have a theorical method to advise us how to determine the universes of discourse of fuzzy variables, which are generally determined by experience and debugging [2]. Therefore, it will be very significant if a learning system can automatically determine the universes of discourse. We wiU present the following formulas to try to solve this problem, although it is also an experimental method. Xr = maxi à A PM PS ZE 00 10 15 20 25 30 times 35 40 Figure 8: The frequency trajectories of the four possible rules: (ZE, NS; PM), (ZE, NS; PS), (ZE, NS; ZE) and (ZE, NS; 00) is to "select the middle rule" which is explained in Section 2. Why don't we choose the rule which has the biggest weight or frequency? Intuitively, we consider the appearance of incompatible rules results from some perturbance. For example, we just simply define FAM-ceU [1] boundaries in the input-output product space X x Y x Z with the clear partition method. But in fact, FAM cells, which correspond to the cuboids mentioned in Section 2, should have overlaped, since contiguous quantizing fuzzy sets Ai and and Bj and Bj+i, and Ck and Ck+i overlap. So the FAM cells are fuzzy subsets of X xY X Z, and their boundaries should be fuzzy but not clear. Now, when we replace the fuzzy boundaries with the clear boundaries, of course, it wiU cause some perturbance. Obviously, this kind of perturbance diffuses in aU directions and diffusion probabilities are the same. Thus forms the incompatible rules, and certainly, the centroidal rule of a'group of incompatible rules is the "core". As for the frequency of the rule, we think it is not the most important piece of data, since it has strong randomness. So, we always choose the middle rule. Additionally, it is also an experimental conclusion [15]. For example, in simulation 1 on inver- ted pendulum reported above, equation (12) is a group of incompatible rules, if we choose the rule of the biggest frequency, then (NS, ZE; ZE) is selected. According to table 2, it is wrong. However, if we choose the middle rule, then (NS, ZE; PS) is chosen and it is right. For the AGCR, although we think it is a good method of recovering the original rules, we are not sure that it can generate the very same result in each time. Because randomness exists in random sampling every time, it also exists in the last learning result. Of course, the influence of this randomness is not very serious. For instance, the rule (ZE, NS; PS) is the most mutable, and most of the others are not mutable. To overcome such randomness, we have created a statistical method [15], which requires many times of leaning, and counting the number of times that each possible rule presents itself. Only the most-frequent rules are decided to be the last rules. For example, in 37 times learning, (ZE, NS; PS) is present 18 times, and (ZE, NS; ZE) is present 14 times, and (ZE, NS; PM) is present 1 time, and (ZE, NS; OO.is present 4 times. Therefore (ZE, NS; PS) should be chosen. Figure 8 describes the frequency trajectories of the four rules. ACCR does not play the most important role in this paper. ACCR is different from PENG Xian-Tu's function method [14]. Because ACCR is only for completing a rule table which has just lost some rules but not for making a whole rule table. But the function method may make a whole rule table. Obviously, ACCR may have other forms. As for AGUD, it is still an experimental result. Of course it may have other versions. We hope ASLSC will be able to generate membership functions in future, and we believe some better results on ASLSC would be obtained after further research and application. References [1] Bart Kosko, {1990)Neural Networks and Fuzzy Systems^ Prentice Hall, 1990. [2] C. C. Lee, Fuzzy logic in control systems: Fuzzy logic controUer -Part I, {l9m)IEEE Trans. Syst. Man Cybern, Vol. 20. no. 2, pp 404-418. [3] A. G. Barto, R. S. Sutton and C. W. Anderson, (1983) Neurolike adaptive elements that can solve difficult learning problem. IEEE Trans. Syst. Man, Cybern, vol. SMC-13, No. 5, pp 834-846. [4] Jyh-Shing R. Jang, (1992) Self-learning fuzzy controllers based on Temporal Back Propagation, IEEE TRANS, on Neural Networks, vol. 3, No. 5. [5] E. H. Mamdani and S. Assilian, (1975) An experiment in linguistic synthesis with a fuzzy logic controller. Int. J. Man Mach. Studies, vol 7, no. 1, pp. 1-13. [6] M. Sugeno and K. Murakami, (1984) Fuzzy parking control of model car, 23rd IEEE Conf. on Decision and Control, Las Vegas. [7] M. Sugeno and M. Nishida, (1985) Fuzzy control of model car, Fuzzy Sets Syst., vol. 16, pp. 103-113. [8] M. Sugeno and K. Murakami, (1985) An experimental study on fuzzy parking control using a model car. Industrial Applications of Fuzzy Control, M. Sugeno, Ed. Amsterdam:North-Holland, pp. 125-138. [9] M. Sugeno and G. T. Kang. (1988) Structure identification of fuzzy model. Fuzzy Sets Syst. , vol. 28, no. 1, pp. 15-33. [10] T. Takagi and M. Sugeno, (1983) Derivation of fuzzy control rules from human operator's control actions, Proa, of the IFAC Symp. on Fuzzy Information, Knowledge Representation and Decision Analysis, Marseilles, France, July, pp. 5560. [11] E. Czogala and W Pedrycz, (1981) On identification in fuzzy systems and its applications in control problems, Fuzzy sets Syst. , vol. 6, no. 1, pp. 73-83. [12] E. Czogala and W Pedrycz, (1982) Fuzzy rule generation for fuzzy control, Cybern. Syst., vol. 13, no. 3, pp. 275-293. [13] C. W. Xu and Y. Zailu, (1983) Fuzzy model identification and self-learning for dynamic systems. IEEE trans. Syst. Man Cybern. vol. SMC-17, no. 4, pp. 683-689. [14] PENG Xian-Tu, (1990) Generating rules for fuzzy logic controllers by functions. Fuzzy Sets and Systems Vol.36, pp.83-89. [15] Xiaozhong Li, (1994) Researches on a self-learning and adaptive fuzzy systems and fuzzy neural networks. Ph. D thesis, Beijing Univ. of Post & Telecomms. [16] H. Takagi, (1993) Fusion techniques of fuzzy systems and neural networks, and fuzzy systems and genetic algorithms, SPIE Proa, of Technical Conference on Applications of Fuzzy Logic Technology, SPIE's Symposium on Optical Tools for Manufacturing and Advanced Automation, Vol. 2061 pp.402-413, Boston, MA. [17] L. X. Wang and J. M. Mendel, (1992) Generating fuzzy rules by learning from examples, IEEE Trans, on Syst. Man Cybern. , 22-6, pp.1414-1427. [18] L. X. Wang and J. M. Mendel, (1992) Fuzzy basis functions, universal approximation, and orthogonal least-square learning, IEEE Trans, on Neural Networks, Vol. 3. No. 5, pp. 807-814. Performance Bounds on Scheduling Parallel Tasks with Setup Time on Hypercube Systems Jiann-Fu Lin and Sao-Jie Chen Department of Management Takming Junior College of Commerce Taipei, Taiwan, R.O.C. Keywords: heuristic algorithm, scheduling, parallel task, setup time, performance bound Edited by: Jerzy R. Nawrocki Received: August 15, 1994 Revised: May 5, 1995 Accepted: August 27, 1995 This paper investigates the problem of scheduling "parallel tasks" with consideration of setup time on a d-dimensional hypercube system, where scheduled tasks are independent such that each task can simultaneously require a subcube for its processing under the constraint that the dimension of a required subcube cannot be greater than the maximum parallelism dimension of a task. Whenever there is a switching of schedule from a task to another one, setup time is necessary. The objective of this problem is to fìnd a schedule with minimum finish time, such a scheduling problem is NP-hard. Therefore, in this paper, we will propose two heuristic algorithms for this kind of problem and derive their performance bounds, respectively. 1 Introduction The problems of scheduling tasks on multiprocessor systems have been extensively studied for a long time. Conventional approaches [1, 7, 12] were proposed for the problem of scheduling each task on only one processor at a time, which is referred to as the "conventional task scheduling problem". Finding a minimum finish time non-preemptive schedule for this type of problem on an m-processor system, where m > 2, is NF-complete [12]. Given a list of tasks with indices 1, 2, ..., n, the list scheduling (LS) algorithm proposed by Graham[7] assigns tasks in the order that they appear on the list. For any given task set, the performance bound of LS was shown as < (2 - , where So and Sls denote the finish times of an optimal schedule and that of a list schedule, respectively. Another heuristic studied by Graham [7] is the largest processing time first (LPT) scheduling algorithm, which states that tasks are selected to assign according to the nonincreasing order of their processing times, and whenever a task is selected, it will be assigned to the first free processor that it meets. If So is the finish time of an optimal schedule and Slpt is that of an LPT schedule for any given task set then it was shown that < (| - 3^). Note that the LPT scheduling algorithm is a special case of the LS algorithm, where tasks in the LPT list are ordered nonincreasingly by their processing times. Afterwards, the above "conventional tasks scheduling problem" has been modified to generate the "multiprocessor tasks scheduling problem" [2, 3, 8], where tasks can be processed on a different number of processors and are thus called "multiprocessor tasks". The latter problem considers a task set T = {Ti, T2, Tn} which contains n independent multiprocessor tasks to be processed on an m-processor system. Each multiprocessor task Ti in T is associated with a fixed number Pi to denote the number of processors required. For this problem type, a schedule is feasible if each task Ti can be exactly processed by pi processors simultaneously, and the performance of a feasible schedule is measured by its finish time such that a feasible schedule is called an optimal schedule if it has the minimum finish time. For this problem type, the complexity of obtaining a schedule with minimum finish time is NP-hard [3]. In solving the multiprocessor task scheduling pro- blem, polynomial time algorithms were proposed by Blazewicz, Drabowski, and Weglarz [3]. But these algorithms were only optimal for two constrained cases of independent multiprocessor task scheduUngs: one case assumed that aU multiprocessor tasks require one-unit of processing time;' the other one was that multiprocessor tasks can have arbitrary processing time, but they need to be preemptive. Algorithms proposed by Chen and Lai [4, 5], and Zhu and Ahuja [16, 17] for scheduling tasks on a d-dimensional hypercube system can be seen as a special case of the multiprocessor tasks scheduling problem. All their proposed algorithms, i.e., the Largest Dimension Largest Processing Time (LDLPT) [4] and the Largest Dimension First (LDF) [17] algorithms, have a same performance bound of (2 — Recently, the problem of parallel tasks scheduling [6, 9, 13, 14] has been introduced. This problem is a little bit different from that of multiprocessor tasks scheduling. In the parallel tasks scheduling problem, a set of n parallel tasks T = {Ti, T2, ■■■,Tn} are to be scheduled on an m-processors system, and each task T,- has its maximum degree of parallelism A,- and computation requirement ti. This implies that a task T,- may be scheduled to process on up to A; processors and this degree of parallelism, once decided for Tj, wiU not be altered during its processing. Suppose that a task Ti is scheduled to process on 6i processors, 1 < (5,' < A,, then di is called the scheduled parallelism of Ti and the processing time required by Ti wiU be For this problem type, a schedule is feasible if the scheduled parallelism 6i of each parallel task Ti is no greater than its maximum degree of parallelism A,-. To find an optimal schedule for such parallel tasks scheduling problem is NP-hard [6], here the optimal schedule means a feasible schedule with minimum finish time. Under the linear speedup assumption, Wang and Cheng [13] showed that the performance bound of Graham's list scheduling algorithm applied to this problem is (A + where m is the number of processor in a system and A = max{Aj|i = 1,2, ...,n}. Lately, Wang and Cheng [14] proposed an Earliest Completion Time (ECT) algorithm for scheduling parallel tasks and derived a performance bound of (3 — Recently, Lin and Chen [9] proposed an Modified Largest Dimension First (MLDF) algorithm for scheduling parallel tasks with communi- cation cost on a c/-dimensional hypercube system, which has a performance bound of (2-|-ln — In this paper, the problem of nonpreempti-vely scheduling independent parallel tasks on a d-dimensional hypercube with setup time in concerns wiU be investigated. Setup time for the processing of any parallel task on a hypercube system consist of the arrangement time, such as constructing a subcube structure, memory arrangement, loading parallel task. That is, if task Ti is a task prior to task Tj, then the start time of processing task Tj is not earlier than the finish time of task Ti- In this paper, the setup time will be considered as a constant. This problem is NP-hard, because scheduling independent nonpreemptive parallel tasks without considering setup time, a special case of this problem, was already known to be NP-hard [6]. The rest of this paper is organized as follows. In Section 2, a maximumparallel- dimension procedure, which is used to decide the scheduled parallelism of each parallel task, is proposed and the worst performance bound of the Largest Scheduled Dimension Fir-sti (LSDF) algorithm using the above maximum-paraUel-dimension procedure is analyzed. Section 3 presents another parallel dimension deciding procedure, called the co-relation procedure, and derived the worst performance bound of the LSDF algorithm using this co-relation procedure. Finally, some concluding remarks are given in Section 4. 2 Maximum Parallel Dimension Policy Consider a set of n independent parallel tasks T = {Ti,r2, ...,r„} to be processed on a d-dimensional hypercube in which each task T,- is associated with a maximum dimension of parallelism Aj- which is similar to the maximum degree of parallelism but must be power of 2, and a computation requirement ti. A task T,- may be processed on up to a A;-dimensional subcube and this parallelism dimension, once decided for Tj, wiU not be altered during its processing. If a task Ti is scheduled to run on a (^j-dimensional subcube, for 0 < di < Ai < d, then di is called the scheduled dimension of Tj. For this problem type, a schedule is feasible if the scheduled dimension di of each task Ti is no greater than its maximum dimen- sion of parallelism A;. Under the ideal assumption, previous parallel tasks and no overhead is required. That is, the setup time caused by switching from processing a task to processing another task needs not be included in their performance analysis. But in fact, the overhead of switching is high and must be taken into consideration. In this paper, the setup time is assumed to be sequence independent [10, 11, 15] and constant [15], i.e., the time taken to switch a processor to a new task is independent of the task last processed and is a constant s. Thus, the total processing time P{x,ti) required for processing a task Ti is equal to -H s), where 1 < a; < A^. By simple calculus, we then have: dPjxM) _ /ln2v. an^ _ (In2)'. Since < 0 and ^^^ > 0 for 1 < < d, P{x,ti) is a decreasing function which reaches its minimum value at A,-. Based on the above result, an intuitive strategy letting the scheduled dimension di of task Ti be assigned to its maximum dimension of parallelism A^ and we will have a minimum processing time P{di,ti) = 5). Procedure maximum-parallel-dimension Begin Assign Ai to the scheduled dimension di of each task T, for i = l,2,...,n. End. With the above scheduled dimension di for each parallel task Ti, a nonpreemptive scheduling algorithm, called the Largest Scheduled Dimension First (LSDF) algorithm for the parallel tasks scheduling problem is proposed. The major policy of LSDF, similar to the Blazewicz's algorithm [3] or the LDF algorithm [17], is that the larger scheduled dimension a task has, the earlier it will be assigned. Algorithm LSDF Begin Call the maximum-paraUel-dimension procedure; Arrange parallel tasks in nonincreasing order of their scheduled dimension; Assign parallel tasks to subcubes according to this nonincreasing order; End. Lemma 1: [8, 9] The number of free processors in a hypercube system will always be a multiple of the number of processors required by a task which is the next to be scheduled in the LSDF algorithm. Lemma 2: [8, 9] If a task T,- , 1 < i < n, is finished at time Sjj, then there will be no processor idle before {Sh — P{di,ti)), where Sh and ti denote the finish time of a task set T scheduled by LSDF and the computation requirement of task Ti , respectively. Theorem 1: Sh<{2- 1/2^)5o + (1 - l/2^)ns, where Sh and So denote the finish times of the LSDF using the maximum-paraUel-dimension procedure schedule and that of an optimal schedule of T, respectively. Proof: By Lemma 1 and Lemma 2, we can get: {2'XSh) = f2[2^^xP{Ai,ti)]+{2'-2^^)P(A^,t,) 1=1 SH< 2^ It is obvious that < So and 2^ + s) < So- We then have: Sh<{2- ^)So +-^- The performance bound derived in Theorem 1 is not tight, in the following, an example wiU be given to show that the worst case performance bound of LSDF using the maximum-paraUel-dimension procedure is at least (2 — + (2'' — Example 1: Let ti = t and Aj- = d for i = 1,2,...,2^- 1, and t2d = t and A2d = 1. Figs. 1 (a) and (b) illustrate that the finish times of an LSDF using the maximum- parallel-dimension J .-F. Lin et al. procedure schedule and that of an optimal schedule are (2i + - and {t + s), respectively. Thus, Sh = {2- l,)So + - 2 - = (2 -+(1- ^-« (2- + (1-where n = 2'^. K » s -»jtadl • ■ ■ I«- s -»|tad[»- s -»I«- (a) 1 1 i'* : (b) Figure 1: (a) An LSPF schedule using the maximum-paraUel-dimension procedure and (b) an optimal schedule. scheduled dimension di of task Ti if the setup time s is small enough. Therefore, either the required setup time s or the scheduled dimension di of task Ti have their respective effect to the speedup and the efficiency of task Ti. To determine the scheduled dimension di of a task Ti, our strategy is to find the largest possible dimension Xi of Ti such that the total reduction of time obtained from processing Ti on an (xi -f l)-dimension subcube and on an Xi dimension subcube should be less than k times of the required setup time s, where k is an arbitrarily chosen positive constant. The smaller kis chosen, the more speed and less efficiency a task Ti will have. From the above strategy, we have: P{xi,ti) - P{xi + l,ti) < ks ^ < ks Procedure co-relation Begin (3) 3 Co-relation Policy The performance of a task Ti is usually defined in term of a speedup factor S {di, ti) and an efficiency factor E{di,ti) as follows. E{di,ti) = P{di,ti) S{di,ti) ii + s (1) (2) From equations (1) and (2), we can observe that the larger dimension of a subcube allocated to a task, the higher speedup of a task will be obtained but the less efficiency wiU also be incurred. There will be a need to make a trade-off between speedup and efficiency of a task. It should be pointed out that the required setup time s also plays an important role in equations (1) and (2). Note that the speedup and the efficiency of task T,- wiU be dominated by the setup time s and little affected by the scheduled dimension di of task T,- if the setup time is quite large. On the other hand, the speedup and the efficiency of task Ti wiU have little influence on the setup time s and much on the Let the scheduled dimension di of task Ti be max{0,min{[log2(|^) - lJ,Ai}}, for i = 1,2,...,n. End. In application, we have simply to replace the statement "Call the maximum- paralleldimension procedure;" in LSDF algorithm by the statement "Call the co-relation procedure;". Lemma 3: P{dj,tj) < {2k -f- l)P{Aj,tj), where di is the scheduled dimension of a task T,- determined by the co-relation procedure. Proof: P{di,ti) = {^ + s) Consider the following two conditions about (i) If 0 < di < Ai, then according to the equation (3), we know that -rjf^ < ks. Then, P{d„U) < + s) That is, P{di,ti)Sh< By Lemma 3, we have Corollary 1: The least upper bound of the derived performance bound of the LSDF using the co-relation procedure is bounded by [2 -1- 2(2 - ' --^-J- (5) From the above two conditions (4) and (5), we conclude that P{di,ii) < 4- l)P(Aj,ij). Theorem 2: The worst case analysis of LSDF using the co-relation procedure is bounded by Proof: By Lemma 1 and Lemma 2, we can get: XS„) = X P{di, /,)] + -2^^ )P{d„ tj) => {2'XSh) = i=l ^Sh < 2^ 2d because ks < ^ < 2ks. It is obvious that < So and P{Aj,tj) < ^o, we have: ■5'// < (1 + i)5o -t- (1 -^)i2k + l)5o Proof: Let F{k) = {2 + 2k -fi) - By simple calculus, we have: F'{k) = 2 - ^ - ^ and F"ik) = Since F'(k) = 0 when k = (2 - and F"{k) > 0. Then, F(k) reaches its minimum value a.t k — Thus, we have: F(k) > [2 + 2(2-|^)^-f(2-A)^ 2d J- The above derived performance bound of LSDF using the co-relation procedure is not tight. Corollary 2: The behaviors of the co-relation procedure and the maximum- parallel-dimension procedure wiU be the same, if the chosen constant k is rarely small, say k < where T = min{i,-|i = 1,2, A special case of the above problem occurs when the setup time is negligible. In such a case, the scheduled dimension of each task Tf determined by the above two procedures, the maximum-paraUel-dimension procedure and the co-relation procedure, will be the same. The worst performance bound of LSPF wiU be reduced to (2 — no matter what the maximum-paraUel-dimension procedure or the co-relation procedure is used. Corollary 3: In case that the setup time is negligible, say s = e/n, the worst performance bound of LSPF win approach to (2 - 4 Conclusions In this paper, we have investigated an LSDF algorithm for the problem of nonpreemptively scheduling independent parallel tasks with setup time. We showed that each task is processed with its maximum dimension is not always the best choice and derived that S h < [(2 - + (1 -■^)ns], where Sh, So and n are the finish time of the LSDF using the maximum-paraUel-dimension procedure schedule, the finish time of an optimal schedule, and the number of tasks, respectively. Thus, another scheduled dimension decision procedure, the co-relation procedure, is proposed and showed that the performance bound of the LSDF using this procedure is [(2-f but this derived performance bound is not tight. The behaviors of the maximum-parallel- dimension procedure and the co-relation procedure will be identical if k is very small. Besides, in case that the setup time can be ignored, the above two scheduled dimension decision procedures will be the same and a tight performance bound of (2 - can also be derived. References [1] Baker, R. K., "Introduction to Sequencing and ScheduHng," New York: Wiley, 1974. [2] Blazewicz, J., Drabowski, M., and Weglarz, J., "Scheduling Independent 2-processor Tasks to Minimize Schedule Length," Information Processing Letter, vol. 18, no. 5, pp. 267273, 1984. [3] Blazewicz, J., Drabowski, M., and Weglarz, J., "Scheduling Multiprocessor Tasks to Minimize Schedule Length," IEEE Trans, on Computers, vol. C-35, no. 5, pp. 389-393, 1986. [4] Chen, G. I. and Lai, T. H., "Scheduling Independent Jobs on Hypercubes," Proc. 5th Symp. Theoretical Aspects of Computer Science, pp. 273-280, 1988. [5] Chen, G. I. and Lai, T. H., " Preemptive Scheduling of Independent Jobs on a Hyper-cube," Information Processing Letters, 28, voL 28, no. 4, pp. 201- 206, 1988. [7] Graham, R. L., "Bounds on Multiprocessing Timing Anomalies," SIAM J. Appi. Math., vol. 17, pp. 416-429, 1969. [8] Lin, J. F. and Chen, S. J., "Scheduling Algorithm for Nonpreemptive Multiprocessor Tasks," Computers and Mathematics with Applications, vol. 28, no. 4, pp. 85-92, 1994. [9] Lin, J. F. and Chen, S. J., "Scheduling Parallel Tasks on Hypercubes," Electronics Letters, vol. 30, no. 11, pp. 841-842, 1994. [10] Monma, C. L. and Potts, C. N., "On the Complexity of Scheduling with Batch Setup Times," Operations Researches, vol. 37, pp. 798-804, 1989. [11] Monma, C. L. and Potts, C. N., "Analysis of Heuristics for Preemptive Parallel Macliine Scheduling with Batch Setup Times," Operations Researches, vol. 41, no. 5, pp. 981-992, 1993. [12] UUman, J. D., "NP-complete ScheduHng Problem," Journal of Computer and System Sciences, vol. 10, pp. 384-393,1975. [13] Wang, Q-. and Cheng, K. H., "List Scheduling of Parallel Tasks," Information Processing Letters, vol. 37, no. 5, pp. 291-297,1991. [14] Wang, Q. and Cheng, K. H., "A Heuristic of Scheduling Parallel Tasks and Its Analysis," SIAM J. Comput., vol. 21, no. 2, pp. 281294, 1992. [15] Wonginger, G. J. and Yu, Z., " A heuristic for Preemptive Scheduling with Setup Times," Computing, vol. 49, pp. 151-158, 1992. [16] Zhu, Y. and Ahuja, M., "An 0(n log n) Feasibility Algorithm for Preemptive Scheduling of n Independent Jobs on a Hypercube," Information Processing Letters, vol. 35, no. 1, pp. 7-11, 1990. [17] Zhu, Y. and Ahuja, M., "On Job Scheduling on a Hypercube," IEEE Trans, on Computers, vol. 4, no. 1, pp. 62-69, 1993. [6] Du, J. and Leung, J. Y., "Complexity of Scheduling Parallel Task Systems," SIAM J. Discrete Math., vol. 2, pp. 473-487,1989. HLO: A Higher-Order Deductive Object-Oriented Database Language Mengchi Liu Department of Computer Science University of Regina Regina, Saskatchewan Canada S4S 0A2 Keywords: deductive databases, object-oriented databases, fixpoint semantics, least model semantics Edited by: Xindong Wu Received: February 13, 1995 Revised: June 19, 1995 Accepted: July 14, 1995 This pamper proposes a higher-order deductive object-oriented database language called HLO. This language is capable of directly and naturally supporting object-oriented features such as object identity, complex objects, classes, and multiple inheritance. It supports the separation of schema and instance but treats schema as meta data so that schema and inheritance information can be represented and queried in the same way as ordinary data. The language is given a firm logical foundation in the form of the Herbrand-like semantics. The main novelty of the language is the incorporation of the well-dehnedness and well-typedness constraints in its semantics. A number of interesting semantic properties are investigated. The intended semantics of an HLO program . is given by the least and justified model if it can be obtained by a bottom-up least fixpoint computation. The necessary condition to guarantee the existence of the intended semantics and the decidability of checking the necessary condition are also discussed. 1 Introduction To deal with complex objects naturally and directly, proper notions are needed for schema and Deductive and object-oriented databases are two inheritance, which normally lead to higher-order important extensions of the traditional data- logic [13], Unfortunately, higher-order unification base technology. Deductive databases extend the undecidable [12], Most of existing deexpressive power of the traditional databases by ' ^^^^^^^^ object-oriented database languages make means of deduction and recursion. Languages of "on-natural restrictions to avoid higher-order lo-this kind include Datalog [8], LDL [23] and CO- ^^^ ^^ ^^^^ Languages such as COL, OIL, RAL [24], Object-oriented databases extend the LOGRES separate schema from instance modeUng power of the traditional databases by ^^^^ non-logical languages for schema and lousing concepts such as object identity, complex languages for mstance. Languages such as objects, classes, and inheritance. Languages of ^-logic, mix the notions of class and object non-this kind include Iris [11], Orion [15], O2 [17], The naturally to get around high-order logic, integration of deductive and object-oriented da- This paper proposes a novel typed deduc-tabases has received considerable attentions over tive object-oriented database language called the past few years. A number of deductive object- HLO, which stands for Higher-order Language for oriented database languages have been proposed Objects. The rationale behind HLO is that certo combine the best of the two approaches, such tain kinds of higher-order features are natural re-as COL [1], IQL [2, 4], LOGRES [7], 0-logic quirements of deductive object-oriented databa-[20], revised 0-logic [14], C-Logic [9], OIL [25], ses and should be supported directly and natu-F-logic [13], LLO [19], LOL [6], L&O [21], Data- rally. The higher-order unification problem can log/method [3], and Gulog [10]. be effectively handled by a bottom-up least fixpo- int computation in which only ground substitutions are used as in [16]. HLO is capable of naturally and directly supporting object-oriented features such as object identity, complex objects, classes, and multiple inheritance. It supports the separation of schema and instance but treats schema as meta data so that schema and inheritance information can be represented and queried in the same way as ordinary data. The language is given a firm logical foundation in the form of the Plerbrand-like semantics. The intended semantics of an HLO program is given by the least and justified model if it can be obtained by a bottom-up least fixpoint computation. The necessary condition to guarantee the existence of the intended semantics of a program and the decidability of checking the necessary condition are also discussed. Compared with the related approaches, the main novelty of the language is the incorporation of the well-definedness and well-typedness constraints in its semantics. Because of these constraints, a number of well-known semantic properties held for traditional logic programs fail for HLO programs. We argue that these constraints are fundamental to the semantics of higher-order deductive object-oriented database languages. This paper is organized as follows. Section 2 informally introduces the language by several motivating examples. Section 3 describes the formal syntax and Herbrand-like semantics of HLO. Section 4 discusses how to compare different interpretations and models and defines the least model. Section 5 focuses on the fixpoint semantics, and Section 6 summarizes and points out further research issues. 2 Informal Presentation There are three different kinds of concepts in HLO which function at three different levels: a unique metaclass class, classes, and objects. The meta-class class denotes the set of classes. Classes denote sets of objects. One purpose of using three levels instead of two is to make the language as self-descriptive as possible, another is to be able to operate on classes and instances in a uniform fashion. For reasons of simplicity, we do not deal with metametaclasses here. Instances of a concept must be declared using instance-of atoms. For example, person : class smith : person specify that person is a class and smith is an object of the class person. Concepts in HLO can have properties. Two kinds of properties are distinguished: definitional and factual. The terms were first introduced in TAXIS [22]. The metaclass class can only have definitional properties, classes can have definitional properties and factual properties, while objects can only have factual properties. Definitional properties of a concept define attributes as partial mappings applicable to its instances, and the range of the attributes. If an attribute always maps an instance of the concept to an instance of the range, then it is called a single-valued attribute; if an attribute always maps an instance to a set of instances of the range, then it is called a set-valued attribute. In HLO, definitional atoms are used to define definitional properties of concepts. For example, person[spouse person, friends person] defines a single-valued attribute spouse and a set-valued attribute friends of person. Factual properties of a concept give the attribute values of the concept, and are specified using factual atoms. For example. smiih{spouse ^ friends mary, {bob, pam}] specifies that the value of the spouse attribute of smith is mary and the value of the friends attribute of smith includes bob and pam. If nothing else about the friends attribute of smith exists, then the value of the friends attribute is the set consisting of bob and pam. If the factual properties of a concept are constrained by the definitional properties of its class, that is, the attribute values of the concept are in the ranges of the attributes of its class, then they are said to be well-typed. For the above example, factual properties spouse and friends of mary are well-typed if mary, bob and pam are instances of the class person. A class may have subclasses, and a subclass may have more than one superclass. Instances of a subclass are also instances of superclasses. A subclass (multiply) inherits definitional properties from its superclasses, but may refine some of the inherited properties and introduce extra definitional properties local to itself. In HLO, such subclass relationship between classes may be represented by a user-defined set-valued attribute isa as follows. class[isa => class] student : class [isa {person}, takes course] employee : class [isa ^ {person}, salary integer] workStudent : class [isa —{student, employee}] The inheritance may then be represented by the following higher-order rules: 0:D^C[isa-^ {D}],0-.C. C[A =4> Q] ^ C[isa {£•}], D[A ^ Q] C[A => g] ^ C[isa {D}], D[A ^ Q]. These rules say that if C is a subclass of D then every instance of C is also an instance of D and every definitional property of D is also a definitional property of C. Note that here {D} does not mean a singleton set, instead it means a set of which the variable D stands for an element. In some way, it is similar to a set grouping variable of LDL [5], but can appear in the body of a rule. Based on the above examples, we can infer workStudent[takes course, salary => integer]. If we have mary : student, then we can infer mary : person. Rules of HLO are used to insert concepts into its classes, to conditionally define definitional properties of a class or metaclass, or to infer factual properties of objects or classes. Following are several further examples. mary : student person[likes ^ person] X : person mary[likes —» {X}] smith[likes —» {X} X[ancestors {5^}] ^ X[parents {!"}] X[ancestors ^ X[ancestors —» {Z}], Z\parents —» {5^}] X[descendants {5^}] ^ Y[ancestors —» {X}] The first rule inserts object mary into class student. The second says if there exists an instance in the class person, then person has a set-valued attribute likes. The third says mary likes everyone that smith likes. The next two rules define the traditional ancestor relation. The last rule defines the reverse relation of ancestor. Given a program of HLO which is just a set of rules, queries can be used to ask for the information about objects, classes, metaclass and their properties. Following are several examples. ?- X : person ?- mary[likes {X}] ?- smith : C[ancestors —» {X}] ?- C[isa —» {person}] ?- student[Ai Ci,A2 ^ C2] ?- C : class[A {£»}] The first query asks about the instances of the class person. The second requests people that mary likes. The third inquires about the classes as wen as the ancestors of smith. The fourth asks about the subclasses of person. The fifth requests single-valued and set-valued definitional properties of the class student. The last inquires about the classes and their set-valued factual properties. 3 Formal Presentation This section defines the formal syntax and semantics of the HLO language. The syntax is concerned with valid programs and queries admitted by the grammar of HLO. The semantics is concerned with the meanings attached to the valid programs and the symbols they contain. 3.1 Syntax This subsection introduces the formal syntax of the HLO language, i.e., its alphabet, terms, atoms, rules, programs, and queries. Definition 1 The alphabet of. HLO consists of the following pairwise disjoint sets of symbols: (1) a possibly infinite set Ö of object symbols, (2) a possibly infinite set C of class symbols, (3) a singleton set M containing the metaclass symbol class, (4) a possibly infinite set A of attribute symbols, (5) an infinite set Vo of object variables, (6) an infinite set Vc of class variables, (7) an infinite set V^ of attribute variables, (8) a set of improper symbols such as parentheses, arrows, etc. Definition 2 The terms are defined as follows: (1) an object symbols from O or an object variable from Vo is an object term, (2) a class symbol from C or a class variable from Vc is a class term, (3) class is a metaclass term, (4) an attribute symbol from A or an attribute variable from V.^ is an attribute term. A term is ground if it has no variables. An object is a ground object term. A class is a ground class term. An attribute is a ground attribute term. Definition 3 The atoms are defined as follows: (1) Let P be a class term and Q an object term. Then class : class, P : class and Q : P are simple atoms, called instonce-o/atoms. (2) Let P and Q both be class terms or both be metaclass terms, and A be an attribute term. Then P[A Q] and P[A Q] are simple atoms, called definitional atoms. (3) Let P, Q, Qi, ..., Qn all be object terms, or all be class terms, and A be an attribute term. Then P[A Q] and P[A —» {Qi, Qn}] are simple atoms, called factual atoms. (4) Let P : Q, P[Ai Pi], ..., P[A, {Qi,u-,Qi,iJ], P[Am Pm], P[An Pn]? •••, be simple atoms, where 0 < I < m < n. Then P[Ai ^ Pi, ..., Al {Q/,1, ..., Qi,iJ, ..., Am ^ Pm, ..., An^Pn,...] and P : Q[Ai ^ Pi, ..., Al ^ ..., A^ => Pm, ••• 1 An ^ Pn;---] are composite atoms, while P : Q, P[Ai ^ Pi], ..., P[Ai {Qi,i-,Qi,i,}], P[Am Pm], P[An Pn], are called constituent atoms of the corresponding composite atoms. An atom is ground if it has no variables. For a ground definitional atom c[f d], f is caUed a single-valued attribute of c. For a ground definitional atom c[5 d], s is called a set-valued attribute of c. Syntactically and semantically, it is allowed for an attribute symbol to be both single-valued and set-valued. But the specific arrows uniquely determine its kind in the context. Definition 4 A rule is of the form A ^ Al,..., An where A, Ai,..,An,n > 0 are atoms. A is called the head, and Ai,..., is called the body of the rule. A rule is safe if aU variables in the head are also in the body. A fact is a rule with empty body. Definition 5 A/jrogrraTTi P is a finite set of safe rules. Definition 6 A query is a sequence of atoms starting with ?-. We can view classes as unary relations and attributes as binary relations of mathematical logic. Since class and attribute variables are used in the language, it is therefore a higher-order language. 3.2 Semantics This subsection defines the Herbrand-like interpretations and models. These Herbrand-like interpretations bear important properties of the traditional Herbrand interpretations. Definition 7 The universe U of HLO is defined as follows: Uo = 0, Uc^C, Um = {class}, Ua = A, U = Uo U Uc U [/m U Ua- Definition 8 The Herbrand base B of HLO is the set of aU ground simple atoms formed from object, class, metaclass and attribute symbols in the universe. Note that tlie Herbrand base does not contain any composite atoms. Definition 9 Let 5 be a subset of B. A ground instance-of atom p : q is well-defined in S if both p and q are class or q : class G 5*. A ground definitional atom u[f v] or «[5 u] is well-defined in S if both u : class G S and V : class £ S. Definition 10 Let 5 be a subset of B. A ground factual atom p[J —g] is well-typed in S if there exist u and v such that p : u E S, u[f t;] e 5 are well-defined in 5, and for aU such u and v, q : v G S. A ground factual atom u[s q] is well-typed in S if there exist u and V such that p : -u e 5, m[s u] G and for all such u and v, qi ■. v £ S for each qi G q- By requiring well-typedness, we can therefore use the definitional properties of classes to constrain the factual properties of their instances. However, the weU-typedness constraint cannot guarantee that attributes are treated as mappings in S since an object may have more than one different value for an attribute. Definition 11 A subset of J5 is consistent if it does not contain a pair of factual object atom p[a ^i] and p[a —^2]? or p[a —» g^] and p[a ^2] s^ch that 52- Definition 12 An interpretation / of a program is a consistent subset of B. Definition 13 A ground substitution Ö is a finite mapping from the variables to U. It is extended to terms, set of terms and atoms as follows: (1) ifpeOuCUMUA, then pO = p, (2) = (3) \i E is an atom, then E6 results from E by applying 9 to every term, set of terms in E. Definition 14 Given in interpretation J, the notion of satisfaction, denoted |=, is defined as foUows: (1) For each ground instance-of atom p : q, I \= p : q if^ p : q is well-defined in I and p : q £ I. (2) For each ground definitional atom ip of the form p[a =;> g] or p[a g], I \= tp iS if) is well-defined in I and ip e L (3) For each ground factual atom p[f q], I \= p[f —^ g], iff p[f q] is well-typed in I, and p[f -q]eL (4) For each ground factual atom g], / |= p[s —» g], iff p[s —» g] is well-typed in I and there exists a p[s —» g'] G / such that q C q'. (5) For ground composite atoms ip, I -ip iS for each constituent atom (p of tp, I ip^ (p (6) Let r be a rule of the form A Ai,...,A„. Then / |= r iff for each ground substitution 0 such that 11= Ai6,...,I |= An& implies I [= A6. (7) For each program P, / |= P iff for each rule r G P, / 1= r. Definition 15 A model M of P is an interpretation of P which satisfies P. Example 1 Consider the following program: class : class[isa ^ class] person : class student : class[isa {person}] mary : student C[isa {P}] An interpretation Iq for this program is Iq = {class : class, class[isa class], person : class, student : class, student[isa —» {person}], mary : student, mary : person} Indeed, the interpretation /0 is a model of the program by the definition. The following interpretations /1 and /2 are two additional models: Ji = {class : class, class[isa => class], person : class, person[parents person], student : class, student[isa {person}], mary : student, mary : person, smith : person} /2 = {class : class, class[isa => class], person : class, student : class. student[isa {person}], student[classmates => student], mary : student, mary : person, john : student, john : person, john[classmates —» {mary}]} In Ji, person has an extra definitional property parents and an extra instance smith, whereas in I2, student has an extra definitional property classmates and an extra instance john with factual property value {mary}. As above example shows, a program may have many different interpretations and models, which means that it can be interpreted differently. What is the exact semantics of a program then? We discuss this issue in the following sections. 4 Comparing Interpretations In this section, we study how different interpretations and models of a program can be compared. We first introduce the following notion. Definition 16 The sub-atom relation between ground simple atoms of B, denoted is defined as follows. {!) p :q q], (3) p[a ^ g] d p[a q], (4) p[a-^q] d^p[a^q], (5) p[s qi] < p[s 92], if qi C q2. Proposition 1 The sub-atom relation is a partial order. Proof. Direct from the definition □ Proposition 2 The sub-interpretation relation between interpretations of a program is a partial order. Proof. Direct from the definition and Proposition 1. □ Definition 18 A model M of P is the least ifi for each model N oi P, M Q N. Definition 19 Let P be a program and Ii and I2 be two interpretations of P. The intersection I of /1 and I2, denoted / = Ji n /2, is defined as foUows: (1) if p:q e h and p : q £ I2, then p : q £ I, e /2, then (2) if p[a q] £ p[a ^q]el, (3) if p[a ^q] e p[a ^ q] e I, (4) if p[f q]£ p[f (5) if p[s G /1 and j)[s 52] € h, then p[s q] E I where = n 92 ■ Il and p[a smith] The following interpretations Ii and /2 are models of the program: /1 = {person : class, person[spouse => person], mary : person, smith : person, mary\spouse —smith]} /2 = {employee : class, employee[spouse employee], mary : employee, smith : employee, mary[spouse smith]} Their intersection is {mary[spouse smith]} which is not a model since the ground factual atom mary[spouse —>■ smith] is not well-typed in I. 5 Least-Fixpoint Semantics We proceed to show that if an HLO program has the least model and this model can be constructed by a bottom-up least fixpoint computation, then we can use it as the intended semantics of the program. Definition 20 Let P be a program and I an interpretation, the operator Tp over I is defined as foHows. Tp(I) = {# I V-isa constituent atom of A, there exists a ground substitution 6 such that I j= AiO, I < i < n, and is either well-typed in J if is a factual atom or well-defined in I if tp is an instance-of atom or a definitional atom} Here Tp is similar to the traditional immediate consequence operator but it incorporates the well-definedness and well-typedness constraints. It turns out that several important properties held for traditional logic programs fail for HLO programs. Definition 21 Let P be a program and S be a set of interpretations of P. The operator Tp is monotonie on S if for interpretations I £ S and J e 5, J C J implies that Tp{I) C Tp(J). In general, Tp is not monotonie because of the well-typedness constraint. Example 3 Consider the following program with just one fact and interpretations I and J. john[spóuse —> mary] I = {class : class, person : class, person[spouse person], john : person, mary : person} J = {class : class, person : class, employee : class, person[spouse person], person[spouse employee], john : person, mary : person} Then I C J. But Tp{I) = {john[spouse mary]} % Tp{J) = (H. Besides, Tp{I) may not be an interpretation. P: Example 4 Consider the following program class : class person : class[friends => person] marylfriends <= smith[s —» {X}] Let I = {class : class, person : class, person[friends person], mary : person, smith : person, john : person, bob : person, smith[friends —» {john,bob}]} be an interpretation. Then we have Tp{I) = {class : class, person : class, person[friends person], marylfriends —» {bob}], marylfriends —» {john}]} which is not consistent and therefore not an interpretation. Definition 22 Let 5 be a set of ground simple atoms. The compact operator C is defined as a partial mapping from i? to i? as foUows: = {p-.qeS}U {pia ^q]eS}U {p[a =^q]eS}U {pia ^ 5] € Ä-} U {p[5 q]lq= u{gi | qi] G S}} if this set is consistent; otherwise C is undefined. Here C compacts a collection of set-valued simple atoms into a single set-valued simple atom and checks the consistency of single-valued simple atoms. Continuing with the example above, we have C{Tp{I)) = {class : class, person, class, per soni friends person], marylfriends —» {bob, john}]} which is an interpretation. Proposition 6 The operator C has the following properties. (1) if I is an interpretation, then C{I) = J; (2) if J C /i' and C is defined on both J and K, then C(J) C C(A'). Proof. Direct from the definition. □ A set S of simple atoms is relevant to an atom tp iff for each tp' € S,'>p' < tp. For example, {b : p} and {bis {a}],i)[s {Ò}]} are relevant to b : p and ò[s {a, ò,c}] respectively. Definition 23 Let Tp and C be two operators as defined above and I an interpretation. Then I is a prefixpoint of Tp and C if C{Tp{I)) C J; J is a fixpoint of Tp and C if C{Tp{I)) = /; and I is the least fixpoint of Tp and C iff for each fixpoint N of Tp and C, if N Q I, then I = N. The following important property holds for HLO programs, which links the notion of model of P to that of prefixpoint of Tp and C. Proposition 7 Let M be an interpretation of the program P. Then M is a model of P iff M is a prefixpoint of Tp and C. Proof. Assume M is a model. Let ip £ C(Tp{M)). Hip e Tp{M), then there exists a rule A A\,..., An and a ground substitution 6 such that M \= Ai6, ...,M |= An9, tp is a ground constituent atom of A9 and ip is either well-typed or well-defined. Because M is a model of P, M ip. There exists ip' £ M such that ip ■< ip'. Thus, C{Tp{M)) C M. If ^ ^ Tp{M), then iP is of the form —» 5]. There exists a subset S o[Tp(M) relevant to ip such that ip is the result of applying C to S. For each p[s qi] € S, there exist a rule A Al,..., An and a ground substitution 9 such that M |= Ai9,...,M \= A^fi and -» qi] is a ground constituent atom of A9. Since M is a model of P, M 1= p[s qi]. Then there exists a set q' such that qi C q' and pis —» q'] 6 M. Obviously, q C q'. Let ip' be —» q']. Then ip < ip'. Again, C{Tp{M)) □ M. Suppose C{Tp{M)) C M. We prove M is a model. If M is not a model of P, then there exist a rule A <= A\,...,An and a ground siibsti-tution 9 such that M |= Ai9,...,Ad \= An9, but M ^ A9. Then there exists a constituent atom Ip of A such that M ^ ip9. On the other hand, ip9 e Tp{M). Assume ip9 e C{Tp{M)) as well. Since C{Tp{M)) C M, there exists a, ip' e M such that ip9 < ip'. Thus M \= ip9, a contradiction. Assume ip9 ^ C{Tp{M)). Then there exists z.ip' e C{Tp{M)) such that ip0 :< ip'. Since C{Tp(M)) C M, there exists a ip" G M such that tp' < ij". We have M [= ijj' as well as M |= 4)9, also a contradiction. □ Due to the well-typedness and well-definedness constraints, the reverse of the above proposition is not necessarily true for HLO programs. Example 5 Consider the following program: person : class We have = 0 and thus C(Tp(0)) = 0 C 0. Clearly, 0 is not a model of the program. Definition 24 A model M of P is justified if for each il> e M, there exists a subset R of rules of P such that tp is the result of applying the compact operator C to the following set: {i^'e I A^ Ai,...,Ane R, is a constituent atom of A, there exists a ground substitution 6 such that M |= Ai6,l < i < n, and tpe < i)} Proposition 8 A model M of P is justified iff M C C{Tp{M)). Proof. Suppose M C C{Tp{M)): We prove M is justified. For each ip £ M, there is a tp' e C{Tp{M)) such that tp < tp'. Then there exist a subset R' of P and a corresponding set S' of ground atoms such that is the result of applying C to 5'. Hence, there exist a subset R of R' and a corresponding subset S of S' such that ip is the result of applying C to S. Therefore, M is justified. Now Suppose M is justified. Let ip £ M. By definition there exists a set S of ground atoms such that ip is the result of applying C to S. For each if £ S, M if since M is a model. So is well-typed or well-defined depending on whether or not it is a factual atom. Hence, ip 6 Tp{M). Therefore, there exists a ip' e C{Tp{M)) such that ip mary] mary : person 2)erson[spouse ^ employee] mary : person The powers of Tp are computed as follows: Tp t 0 = 0 Tp t 1 = {class : class} Tp 2 = {person : class, employee : class} UTpTl Tp t 3 = {person[spouse ^ person], john : person, mary : person} U Tp t 2 Tp t 4 = {person[spouse => employee], john[spouse —^ mary]} U Tp t 3 Tp t 5 = Tp T 4 —{john[spouse —mary]} Tp T W = Tp T 4 However, Tp t is not a model of P since the fact john[spouse —mary] cannot be satisfied by it. Proposition 10 Let P be a program, ppose Tp t a; is a model of P. Then Su- ci) Tp(Tp T 0 C Tp(Tp T i + 1) for i e N. (2) Tp is monotonie on. {I}icTp-\uj- (3) For any model N of P, Tp{Tp j i) C Tp{N) for natural number i. Proof. (1) Let V G Tp(Tp T i)-Tp{Tp T ž+1). Then there exists a rule A <= and a ground substitution 9 such that Tp "I i \= Ai9, ..., Tp t i 1= and V* is a constituent atom of AO. Since ^ ^ Tp{Tp t i + 1), either there exists Ai for some i such that Tp t i + 1 ^ Ai6 or tp is neither well-defined nor well-typed in Tp t « + 1- For the first case, let tpi = Ai6. Then ipi G Tp(Tp t Ž) - Tp{Tp t ^ + 1). By repeating the above process we can find a sequence ip, ipi, ■■■, 4'n for some finite n such that ipn is a ground fact and is neither well-defined nor well-typed in Tp f i 1 which lead to the second case. For the second case, there exists a, tp' £ Tp u such that :< 'ip'. Therefore ip' is neither weU-defined nor well-typed in Tp "f u. This means that there exists a rule which cannot be satisfied by Tp I w, a contradiction. (2) Direct from (1) and Proposition 6 (2). (3) Straightforward from (1). - □ Now we present one of the major results of the theory. Theorem 1 Let P be a program. Suppose Tp t w is a model of P. Then (1) Every model of P contains Tp j w, i.e., Tp t w is the least model of P. (2) Tp t w is a justified model of P. Proof. (1) We first prove Tp j is least. Let iV be a model of P. We prove by induction on i that TpUQN (1) The basis is clearly true. Suppose the claim holds for i > 0. By Proposition 10 (3), we have Tp{Tp t i) C Tp(iV). By Proposition 6 (2), we have C{Tp{Tp T 0) E C{Tp{N)). By Proposition 7, Tp t i+1 = C(Tp(Tp t i)) Q C{Tp{N)) Q N. Therefore (1) holds for all i and we obtain TpIuCN. (2) Let M denote Tp f w. We now prove by induction on i that TpU^ C{Tp{M)) (2) The basis is clearly true. Assume the claim holds for i > 0. By Proposition 7, Tp ] i H C{Tp{M)) C M. By Proposition 10 (3), Tp(Tp T 0 C Tp(M). By Proposition 6 (2), Tp\ = C{Tp{Tp T i)) C C{Tp{M)). Therefore (2) holds for aU i and we have Tp j a; C C{Tp{Tp t w)). By Proposition 8, Tp | w is a justified model. □ Example 9 Consider again the program of Example 1: class : class[isa class] person : class student : class[isa {person}] mary : student O-D ^O-C^Clisa-^ {D}] The powers of Tp are computed as follows: Tp t 0 = 0 Tp t 1 = {class : class} Tp T 2 = {class[isa class]} U Tp T 1 Tp t 3 = {person : class, student : class} UTp T 2 Tp t 4 = {student[isa {person]], mary : student} UTp T 3 Tp t 5 = {mary : person} U Tp t 4 Tp T cu = Tp T 5 = /o which is a model. It is therefore the least and justified model by Theorem 1. Unlike traditional logic program, Tp j w is not always defined due to the consistency constraint. Even if Tp j w is defined, it may not be a model of P due to the well-definedness and well-typedness constraints. Example 10 Consider the following program. class : class person : class[spouse person] mary : person smith : person mary[spouse smith] mary[spouse mary] This program has no models since no interpretation would contain both mary[spouse -s- smith] and mary[spouse —^ mary] by definition. We have Tp T 0 = 0 Tp t 1 = {class : class} Tp t 2 = {class : class,person : class} Tp I 3 = {person[spouse person]} U Tp t 2 Tp t 4 = {mary : person, smith : person} UTp T 3 Tp(Tp T 4) = {mary[spouse —> smith], mary[spouse mary]} U Tp T4 Therefore, Tp t 5 and Tp ] u are not defined since C is not defined on Tp{Tp ] 4). The next example shows that it is possible for a program to have the least and justified model but Tp t w is not a model. Example 11 Consider the following program. class : class person : class john : person[likes —» {john}] person[likes ^ {person}] X[likes {y}] is: Tp t w is not a model of P since it cannot satisfy the fact john[likes {cat}]. Definition 26 A program P is well-written if Tp t w is a model. The program in Example 9 is well-defined, but the programs in Examples 10 and 11 are not well-written according to the definition. Proposition 11 Let P be a well-written program. Then Tp j w is the unique least and justified model. Proof. Direct from Theorem 1. □ The least and justified model of this program M = {class : class, person : class, person[likes =» {person}], john : person, john[likes —» {john}]} The powers of Tp are computed as follows: Tp T 0 = 0 Tp t 1 = {class : class} Tp t 2 = {person : class} U Tp t 1 Tp j 3 = {john : person} U Tp t 2 Tp t u; = Tp t 3 Thus, if a program is weU-written, then it has the least and justified model which can be obtained by a bottom-up least fixpoint computation. Theorem 2 It is decidable whether or not a program is weU-written. Proof. We compute the powers of the operators Tp according to the definition. As we compute Tp t n, if a rule is satisfied, we mark it satisfied; otherwise, we mark it unsatisfied. Since the number of objects, class and attribute symbols of a given program is finite, the possible ground substitutions for the object, class and attribute variables have to be finite. Therefore there exists an i, such that either Tp j i is undefined or Tp t i is a fixpoint such that Tp u = Tp i. If Tp j a; is defined and no rule is marked unsatisfied, then Tp t w is a model and consequently is the least and justified model of the program by Theorem 1. Otherwise, the program is not well-written. □ Definition 27 Let P be a well-written program. Then its declarative semantics is given by Tp^iv. Definition 28 Let P be a well-written program and ?- Al,..., An a query. Then an answer to the query is a ground substitution 6 such that Tp^u^ArO, ...,Tp]u\=Ar,e. Theorem 3 Let P be a program and Q a query. Then it is decidable whether or not there is an answer to Q. Proof. Direct from Theorem 2. □ This theorem says that even through HLO is a higher-order language, but the limited use of higher-order features in a deductive object-oriented database framework does not pose any problems. 6 Conclusion In this paper, we have presented a high-order deductive object-oriented database language which is capable of directly and naturally supporting object-oriented features such as object identity, complex object, classes, and multiple inheritance in a uniform framework. We gave the language a simple Herbrand-like semantics which naturally incorporates three kinds of powerful integrity constraints: consistency, well-definedness, and weU-typedness constraints. A number of interesting semantics properties of the HLO programs were investigated. We showed that incorporating the consistency, well-definedness and well-typeness constraints negates many important properties held for traditional logic programs. We then discussed the necessary condition for the most important property that should be held by HLO programs and the decidability of checking the necessary condition. Finally, we illiistrated that if the necessary condition is satisfied, we can compute a program bottom-up to obtain its intended semantics based on which the queries can be answered. We are currently considering extensions to the language to include set-valued variables, negation, and arithmetic and comparison operations. Besides, we intend to investigate how to incorporate update constructs into the language while maintaining the least model semantics and how to efficiently implement the language. Acknowledgments The work was partially supported by the Natural Sciences and Engineering Research Council of Canada. References [1] S. Abiteboul and S. Grumbash. COL: A logic-based language for complex objects. ACM TODS, 16(1): 1-30, 1991. [2] S. Abiteboul and P.C. Kanellakis. Object identity as a query language. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, 159-173, 1989. [3] S. Abiteboul, G. Lausen, H. Uphoff, and E. Waller. Methods and rules. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, 32-41, 1993. [4] Serge Abiteboul. Towards a deductive object-oriented database language. Data and Knoiuledge Engineering, 5(2): 263-287,1990. [5] C. Beeri, S. Naqvi, 0. Shmueli, and S. Tsur. Set construction in a logic database language. J. Logic Programming, 10(3,4): 181232, April/May 1991. [6] E. Bertino and D. Montesi. Towards a logical object-oriented programming language for databases. In Proc. Intl. Conf. on Extending Database Technology, 168-183, Springer-Verlag, March 1992. [7] F. Cacace, S. Ceri, S. Crepi-Reghizzi, L. Tanca, and R. Zicari. Integrating object-oriented data modeUing with a rule-based l^rogramming paradigm. In Proc. Intl. Conf. on Very Large Data Bases, 251-261, 1990. [8] S. Ceri, G. Gottlob, and T. Tanca. Logic Programming and Databases. Springer-Verlag, 1990. [9] W. Chen and D.S. Warren. C-Logic for complex objects. In Proc. ACM Symp. on Principles of Database Systems, 369-378, 1989. [10] G. Dobbie and R. Topor. A model for sets and multiple inheritance in deductive object-oriented systems. In S. Ceri, K. Tanaka, and S. Tsur, editors, Deductive and Object-Oriented Databases, 473-488, Phoenix, Arizona, USA, December 1993. Springer-Verlag Lecture Notes in Computer Science 760. [11] D.H. Fishman, B. Beech, H.P. Cate, E.G. Chow, T. Connors, J.W. Davis, N. Derrett, e.G. Hoch, W. Kent, P. Lyngbaek, B. Ma-hbod, M.A. Neimat, T.A. Ryan, and M.C. Shan. Iris: An object-oriented database management system. ACM Trans, on Office Information Systems, 5(1): 48-69, January 1987. [12] W.D. Goldfarb. The undeddability of the second-order unification problem. Theoretical Computer Science, 13: 225-230, 1981. [13] M. Kifer,' G. Lausen, and J. Wu. Logical foundations of object-oriented and frame-based languages. Technical Report 90/14, Dept of CS, SUNY at Stony Brook, 1990. [14] M. Kifer and J. Wu. A logic for programming with complex objects. J. Computer and System Sciences, 47: 77-120, 1993. [15] Won Kim. Introduction to Object-Oriented Databases. The MIT Press, 1990. [16] R. Krishnamurthy and S. Naqvi. Towards a real horn clause language. In Proc. Intl. Conf. on Very Large Data Bases, 252-263, Los Angles, USA, 1988. [17] C. Lecluse and P. Richard. The O2 database programming language. In Proc. Intl. Conf. on Very Large Data Bases, 411-422, Amsterdam, The Netherlands, 1989. [18] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 2 edition, 1987. [19] Y. Lou and M. Ozsoyoglu. LLO: A deductive language with methods and method inheritance. In Proc. ACM SIGMOD Intl. Conf on Management of Data, 198-207, 1991. [20] D. Maier. A logic for objects. Technical Report CS/E-86-012, Oregon Graduate Center, Beaverton, Oregon, 1986. [21] Francis G. McCabe. Logic and Objects. Prentice Hall., 1992. [22] J. Mylopoulos, P.A. Bernstein, and H.K.T. Wong. A Language Facility for Designing Database-Intensive Applications. ACM Trans. Database Systems, 5(2): 185-207, June 1980. [23] Shamim Naqvi and Shalom Tsur. A Logical Language for Data and Knowledge Bases. Computer Science Press, 1989. [24] R. Ramakrishnan, D. Srivastava, and'S. Su-darshan. CORAL: Control, relations and logic. In Proc. Intl. Conf. on Very Large Data Bases, 238-250, 1992. [25] Carlo Zaniolo. Object identity and inheritance in deductive database —an evolutionary approach. In W. Kim, J.M. Nicolas, and S. Nishio, editors. Deductive and Object-Oriented Databases, 7-21, Kyoto, Japan, December 1989. North-Holland. On the Balance of the Informational Exchange, Its Flow, and Fractional Revealing Large Informational Quanta, in the 'Hot' Living Systems (T < 0_) Ji'fi Sleclxta Member of New York Academy of Sciences 18 Lidgett HiU Leeds 8, LS8 IPE, U.K. Keywords: 'hot' living systems (T < 0_), informational exchange, informational quanta Edited by: A.P. Železnikar Received: February 1, 1995 Revised: July 14, 1995 Accepted: August 4, 1995 It is discussed the case of the informational 'saser'in the 'hot'living systems (T < 0), for T < 0_ (the absolute negative zero), and explained why the large quanta of information, like that stored and developed by a genius, or a voluminous new discovery, or a marital love, spread less easily, except for T s; 0_, than the smaller quanta, like a random love. A way how to improve this property is to design a sparse set of smaller quanta which span the large quantum (e.g. a kind of teaching the large issue, or policy making about it). It is discussed how to design such a set. In the balance of the equivalence of the various forms of the spanning, a generalized equation of the conservation 'energy' ßgures the relative, and not the absolute, precisions. There is provided a formalized framework of the intercommunication among n persons. On the basis of it there is also given the first exact explanation, in existence, why the 'two house' sex is superior to any other form of it, why an offspring of higher animals needs two parents, the theory of measurement of the objective reality, the relation between the theory and experiment, the difference between working of the brain of the people with associative and verbatim memories, and modern and underdeveloped societies, etc. The theory presented here is important for the design of an artificial intelligence [the logic of the real self-organizing systems—(fuzzy) physical logic], and methodology of teaching, the theoretical design of the optimal society, etc. 1 Introduction bers of the given society (further SMs) [2, 7-9], which are both excited relatively to their surro- In [1, 2] there were formulated theoretical foun- undings. dations of two kinds of the self-organizing hving Though the detail properties of these systems systems, the brain [1], on one side, and the sod- are different their theoretical descriptions have a ety [2], on the other side. They have in common lot in common, they consist of sparsely distributed members of these systems which are, relative to their surro- Because of this it is to be formulated, here, a Undings, informationally charged by an informa- theoretical core common to both of these systems, tional quantum Eq. ^^ These members are either the memory traces The results of this study are then applied to (further MTs), in the brain [1, 3-6] or, the rela- the special cases, parallels, in each of these two tively, against their surroundings, informed mem- systems, in particular. J. Šlechta 2 A Unitary Description of the Brain and Society as 'Hot' Living Systems Within such a general core the members of a self-organizing living system, of which these two kinds of living systems are specific examples, will be called the informed members of the given living system (further IMLSs). In [6, 7] it was shown that to such a kind of a living system, further called a generalized living system (or GLS), there may be ascribed the absolute temperature T given by the formula ([6, 7]) T 2eo In (1) dS = T (2) where S is its entropy, E its internal energy and T its absolute temperature. In [7,13] it was shown that for a two component GLS consisting of: a) a continuous system I with T/ > 0 and, b) a finite discrete system II with T// < 0, it holds dS = dEiji ^ 1 ;7r + 1 (3) where iV_ + iV^ = N. Here, N is the total number of the members of the living system (further MLSs) capable to be excited, N_ is the number of the unexcited MLS, and N^ the number of the excited MLS, or IMLSs, T is the absolute temperature of a saser in a society [2, 7], or of a generalized laser in the brain [1, 3, 6], and £o is the energy of the excited level of MLSs, relative to the surroundings [1, 2, 4]. As it is known from the theory of the lasers [1012], in the case of the so-caUed inverse occupation of these discrete excited levels, when Nt > iV_, that is, when the number of IMLSs is higher than the number of the unexcited MLSs, for the absolute temperature T it holds that T < 0 [1, 2]. This is a property having the physical meaning for the discrete systems only [10-12]. In [1, 2] this concept was applied and generalized for the thought processes in the brain, and the group of organizers and information processors in a society (e.g., the managerial group in a plant, the scientists and politicians in a society, etc.) When the total number of MLS exceeds 1525 the cooperative GLS starts to have macroscopic features, so the thermodynamics [1-10] can be applied to it. It holds \Ti ' abs(r//) where Ejji denotes the energy of the mutual exchange between I and II and for dEiji > 0 the energy flows from II to I. Therefore, because dS > 0 is always true, the energy in the system is bound to flow from II to I, providing that in / a receiving resonance needed [7] can be found . The equation expresses the fact that a system with T < 0 is 'hotter' than any system with T > 0 (an ordinary continuous system [13-15]). 3 The Case of T <> 0 In detail, in [6, 7], mainly the case close to the negative absolute zero 0_, when all the MLS capable to do so are excited, was discussed. One kind of the limiting case, for T « 0_, was the case of a 'genius' [2, 7] and other singular situations, like a mother, or a father to their child, etc. [7], to both of which the same formulae can be apphed. This paper deals, in more detail, with cases of T < 0_, where T is considerably different in regard to 0_. While in case T « 0_, the temperature depends on how close the situation is to the hundred percent inversion, only in case T <> 0_ it depends also upon the size of fo [Eq. (1)]. In the latter case, for the same degree of inversion, that is for the same value of the ratio N jf^ <> 0 in Eq. (1), the larger £o is, the larger abs(T) will be, that is, for T < 0, the lower temperature (on the temperature axis, with the temperature arranged with a growing degree of the inversion, or the internal energy) the system wiU have. It means, for the same degree of the inversion, the more voluminous message (e.g. large original works or strong love, especially the marital and parental ones, etc.) has a smaller temperature gradient relative to its surroundings than a shorter message (e.g. short texts, like letters, or occasional short love affairs, etc.). This causes the former ones to spread less easily, more slowly, more cumbersomely. By this a weU known fact is described that the larger works happen to be more 'static'. It is for them more difficult to become known. For this reasons the scientific papers, or magazine articles, as kinds of the published form, are a necessity among letters and books. In case of the brain, the long term MTs are more voluminous: they possess either a large £o of the knowledge of 'a virgin' type (a kind of a new background knowledge [2]), or messages gained by a relatively small to projected against the large background knowledge, already present in the brain (a sudden release of this explains the power of jokes, or the poetry, and why it is difficult to be gained by foreigners). When an event is sampled by a field of random small probes, for example, in the form of a short interview of a bigger personality, it may result in a Brownian type result [14] for the appreciation of his/her uniqueness, that is in a zero appreciation and the degree of understanding, and acceptance of his/her message. Because of this the voluminous works have lesser 'irradiability' than the short ones. To improve their acceptability, or even to prove their uniqueness, requires more extra efforts, often unwilling to be inserted by other people and thus remaining entirely out the horizon of their capabilities. The voluminous knowledge is more 'calm' and stable (e.g. already formed marriages, relative to 'testing pairing'). The static feature of the voluminous £o may be enhanced by the unease to find for it a fuU resonance [7]. This can have a practical consequence for the real top people and even those who are not entirely unique and absolute, can appear often relatively 'static'. So it takes time for them to become recognized in comparison to people of fast short wits of specks of obvious uniqueness (often 'tested' locally only). However, in a long term run, according to the thermodynamical results in [7], the top people of the voluminous knowledge are eventually bound to be accepted, to win, and then they are impervious to be 'scattered' from their course by 'petty' attacks (here the theorem works on the opposite parameters which control the statements like 'nothing is wrong with his/her [their] work', 'his/her [their] work has been really best [in the world, or a given region], in a direction', etc., which stabilizes the gained results). The transition between these two states may be dramatic and up to a catastrophic strengths for some individuals involved. However, to describe this mathematically has been beyond the thermodynamical framework of [7] and the related works [2, 7-9, 15, 16]. Even the works on time scales in economy [17], and thought processes [18], are still not kineti-caUy detailed enough as they lack the nonlinear coupling between the processes at the individual level of IMLSs and the macroparameters (especially the phase transformation in them) of the given hving system, within its surroundings. 4 On a Fractional Spread of a Voluminous Piece of Information As pointed out in [7], a larger £o can be passed by smaller portions ea, such that = £o (superfuzzily) (4) Here, the superfuzzy 'equal' means it is not necessarily so that the sets of the lessened portions Soi are crisply defined in an unique way. Their choice can be from a fuzzy superset [19] of aU such sets, each of them with a fuzzy character, which fulfills these spanning properties. Each portion £oi < (or even <) Sq, and therefore, according to Eq. (1), the absolute temperature Tqj- ascribed to it, is for the sanie degree of inversion for the given sqì as for £o higher than To of the original quantum of information £o, and closer to 0_. ^ Moreover, to generate the inversion for Sqì is, in principle, easier than for £o, because it is easier to find SMs capable to absorb them resonantly [6]. It makes the set of the SMs with the index i 'hotter', relative to the temperatures of the set of the other SMs to whom it is to be passed, than the original voluminous quantum eq. Therefore, the latter SMs are to be able to receive it more easily and more readily. Because of this it is likely there will be more members of GLs ready to receive the partial in- formation Eìq than the original complete information So- This makes possible that the number Ni of these can be much higher than N (often zero) of those able to receive Eq. This, however, makes the portion eoi less unique because relatively more many of GLS members, able to receive the fractional sqì remain unexcited, initially, which lowers the temperature Toi relative to Tq—an opposite tendency to that due to the smaller size of partial eoi- This is enhanced further due to the fact that N- to achieve a partial fraction ä 0 (an absolute inversion for sqì) to increase Toi [Eq. (1)] to gain a larger gradient with the relevant receivers, may take a considerable effort, which decreases the gain achieved by suitable 'biting' the original message Sq. Nevertheless, as pointed above, it is in principle practically more readily possible and is rather the question of a supply of the energy to the teaching, propaganda, or activities, while it was virtually impossible for £o, to enhance the 'mass' receptivity of the total geniality within the same period of time, well nigh impossible. However, on top of these two competing tendencies, the conservation sum (4), inclusive its particular fractionating, makes it again very unique, with the summary effect of shifting the whole sum towards 0_ (the situation 'genius') of the measure of its uniqueness equal to 1, thus achieving the goal: the total result of the fractio-nalization is both not less unique than the original message Sq and it has the improved capability to be perceived (received) by the society (per partes). Even when each £,o is also 'genially' unique, the number of MLSs resonating with these shortened quanta is likely to be much higher than 1, which guarantees a success of the social spread of the knowledge of £o. To produce such a fractionalized communication is one of the skills of politicians. Such a situation happens also in teaching of any subject in schools in smaller units of individual lessons (a kind of a sparse control of knowledge [7, 15, 16]). The role of the publisher is to provide the resonance [6] to the authors and provide a way of dissemination of it, and making for them the coefficient of efficiency 77 > 1 [8]. Otherwise, this is a daunting task for any individual. Historically, it has been evidence the lack of a plenty of publishers leads to a stagnation of the given intellectual area. To provide for a publishing freedom has been, therefore, a nobel duty of any government. 5 On the Relative Precision Let us present a brief generalization of the theory of the evaluation of the precision of the measurements like it is done in physics [17]. When d A is the precision of the measurement, or contribution of or to a quantity A, the ratio rpA = clA T (5) is the relative precision or contribution. For example, an absolutely small, but nonzero, contribution dB to an area B about which there has been no knowledge, that is 0 = 0, has its rpi? infinitely large (e.g., the case of a 'genius' [2]), while rpC of even a large volume dC added to a well developed field C may be rather small (here, it depends upon the structure of the contribution of dC related to C ; the more abstract and general dC is the larger the related rpC caii be). Let us apply this to the precision of the satisfying Eq. (4). Let res(£o) mean the imprecision of the balance of Eq. (4); then the ratio rres(£o) = abs 'res(£o) V £0 (6) may be called the 'relative residuum'. The balance equation (4) for two original quanta is satisfied comparatively to the same degree of precision when the two relative residua related to them are of approximately the same value. To use, for such a comparison, the absolute precision of the balance of the original quanta of very different sizes is practically incorrect for the larger one, because the situation, related to it, is likewise more 'coarse'. When comparing the fulfillments of the given two different balance equations (4) it is more correct to compare the related relative residua because to compare the absolute precisions of such fulfillments is unfair to the equation with the larger £oi. Such an equation may be fulfilled, in absolute terms, rather coarsely, that is less finely. This may be scoffed upon, yet, in relative terms it is equally sufficient. For example, it is sufficient to balance the plans and estimates of budgets in millions pounds, to thousands pounds, while, budgets in hundreds pounds need to be made to the last penny. Especially, to forecast the large budgets more precisely, in the absolute terms, is, by and large, practically impossible and has no economical sense. Rather the opposite is true because the impossibility of the forward predictability may waste vast sums of money, and it is mostly futile, anyway (this is true, however, for the forward planning only, while in the case of the real accountancy 'backward', a recursive usage of Eq. (4) makes possible, and desirable, to balance it to the last penny). 6 Informational Balance During a Fractional Compound Pass of an Informational Quantum Let Isi be the informational background of the SMi and IFsi the information passed by the receipt ofsoi; then ([2]) ■ IFsi - Isi - £oi (superfuzzily) (7) To achieve the fractional pass of the original informational quantum So? in Eq. (4), by spanning it by IPsi, it should be that J^i^^Si contains Eq superfuzzily, that is. ^ IPsi D £o (superfuzzily) (8) If J5j = 0 then eoi must be considered for a 'virgin' piece of information, and not to be judged [2]. This happens, for example, in the case of a formal schooling, when the students do not have, at the beginning of their course, any background in its direction. Also two experts should consider this to happen when communicating with each other. This was studied in details within the concept of the 'spinning top' [21]. The process of fractional spanning can be recursive. This is practiced during the formal education from the primary to the higher education. In scientific papers the references are given which span the necessary background against which, in the mind of the author, the given paper was written, and against which it should be read, too. This property is recursive until the reader reaches the level where he already reads everything with understanding. From such a level he can return 'up' to the initial paper of his interest. Often, within the life situations, except the scientific papers, the relation expressed by Eq. (7) is not taken into an account because of the lack of the awareness of its existence, and of the underlying informational processes and effects, which make the compound spread of a voluminous piece of information unreliable. For example, it is commonly forgotten or abandoned the check whether the integral fractional message, represented by the left-hand side of Eq. (4), represents sufficiently adequate the original message at the right-hand side of the equation, and what kind of misimpression, and how large, is created by this. A special case of such a situation is the lack of a check how precise are the collected personal data about a person in the cadre material files. This makes such a kind of the formation of the personal information unreliable, even socially dangerous (e.g. the known erroneous cadre politics in the former communist block of the East Europe). In many cases the smaller quanta eoi related to the message £o, in Eq. (4), are meant to advertise £o to be studied more comprehensively, rather than to replace it. ^^ This is an important technique of sketching new voluminous, medium and long term projects, both by leading politicians (from Form 3 and 2, to Form 2 and 1 [2]) and scientists (from Form 3 to 3, and 2). 7 On Intercommunication between n Persons Let us sketch briefly a linear theory of the intercommunication between n people. Let Ai be the total knowledge of the i-person. Then, in a linear approximation, it may be writ- ten in the form Ai = ^ Aij (superfuzzily) j (9) where Aij is the partial well defined j-area or j-fleld of the knowledge of the i-person, noninte-racting with other areas of the same person (the property of the linear approximation). It means that these are well defined, distinct areas or fields of a person's knowledge. However, the superfuzzy sense of the relation (9) caters for a situation when the components Aij and Ai are determined by a practical observable kind of procedures, like psychological or sociological experiments, consisting of a series of separate sessions or events (the fuzzy part), within a series of various situations or circumstances (the 'super'-fuzzy part over it), selected at random patterns. The informational contents of the area Ai, the quantity also needed in Eq.s (4) to (8), may be defined by the Mod(Ai). Then the set product AiDAk J^AijHAkt it (superfuzzily) (10) defines the common part of the total knowledge shared by the i- and j-persons (mutually determined, for example, by two lovers within repetitions [the fuzzy part] of various [the 'super'-fuzzy part] shared events). The members of the set of the shared partial pieces of knowledge Aij,M = Aij n Aki (superfuzzily) (11) are, if they exist, rather smaller, narrower, than the members of the set of the two compound sets Aij and Ake- The spectrum of the perception of the new piece of information A by the t-person is given by the set product A n Ai = ^ A n Aij (superfuzzily) (12) J where the set Bij — An Aij (superfuzzily) (13) is an analogue of the spectral 'lines', or 'colors' of A perceived by the i-person. Nothing else of A is recognized by the person. The shared perception of such a new area A by the i- and j-person is given by the set product A n Ai n Aj = ^ A n Aij n Ake (superfuzzily) je (14) The shared set Bijki = An Aij f) Ake (superfuzzily) (15) consists, again, of mostly much narrower members than the compound set AH Aij. It is often even all empty (those two people have nothing in common to share about the area A). The structure, relative to the total knowledge, insets of the persons involved, given by the subtractions Cij = Ai - Aij (superfuzzily) (16) determines the quality of the perception of the area Aij by the i-person, for example, a sense of its beauty. The set Di = Y^Bij (superfuzzily) (17) i defines the integral sense of beauty the i-person feels about his total perception of the world. The set product Dij = jDi n D j (superfuzzily) (18) provides then the total mutually shared beauty by the i-person and j-person, for example, their mutual love at the first sight [4], etc. Sometimes, some of the elements Aij^ke, in Eq-(11), form a crystalline grid, for example, a party sharing the same well-defined and rather short, or/and relatively (in contrast to the whole 'teaching') simple doctrine. The narrower they are, the more rarely this happens, however, the sti-fFer such a grid is. It may become then, due to the le Chatelieu principle, a source of the possible oppressive and morbid effects [2] (e.g., the oppression by the Nazi, or Communist parties, or simple nationalism). 8 Further Consequences 1) On the relation of the experimental results Roi to the 'objective' (total observable) reality R Eq. (4) written here in the form y^ Roi = R (superfuzzily) (19) where the summation is to be taken for a Stiltjes integration, expresses sufficiently how the objective reality can be (is) extrapolated by the set of the measurements (observations) Rqì. Eq. (7) can be written in the form IProì = Cr,, - Roi (superfuzzily) (20) where Cr,, is the context within which the i-experiment is carried. IPr,, expresses the meaning, the informational yield of (the message received by) and Rqì represents an experiment within such a context. Within the first laboratory measurement of the given kind ever, Cr^- = 0, and the experiment Rqì is the message per itself. Only any further repetition of it yields a new extra differential message. Then the inequality IProì D R (superfuzzily) (21) conveys that the total message in aU the measurements contains also R. 2) On the relation between the theory and experiment The theory iZmod of R represents a theoretical description, an image of R, inclusive the way of how it is accessible by the set of experiments Äoimod-It gives the prescription how to evaluate ižoimod- When Roimod = Roi, the theory of R is said to be a proper one. If no other equivalent or better theory is designed, then ižmod is considered to be the (only) proper one. Within the progress of the development, the exploration of R by the extrapolation of iž, defined by Eq. (19), is enlarged. Historically, such an extrapolation process had started by naive observatory results, a kind of naive experimental data which, then only after, were theorized upon. Here it can be said that the art of philosophy includes a nonmathematical way, the first stage of theorizing. Professionally, the theorizing preceded professional experimenting because this includes a theoretical design of the experiment itself, based upon the preceding theory, at the beginning a naive one. From this stage what is 'at first and the next' has reverted the order. The professional theorizing opens a new way of evaluation the experimental data inclusive the theoretical design of new experiments to be theorized upon. In this way, in the present, the theory precedes the experiment. In details, a new field of study starts with the first phenomenological data, an analogue of the naive way of the past, and then it progresses as described above. 3) More on the spanning a large information quantum by a set of smaller, partial ones—on properties of their grids The partial messages Eqì, each of them, form more easily, than the original quantum Eq, a crystalline grid, which can both: a) form a grid of reference for an acceptance of or b) cause a refusal of eo- For example, if the set of soi? about the habits, or knowledge, of a person is chosen, even deliberately, viciously, simplified, stressing the negative points, then the person's special features are taken for a nuisance and not accepted. Although such a person may be refused on the basis of his/her more comprehensive integral personal properties eo, he/she may be found a good person and as such accepted [e.g., any personal interview of a senior published person(ality) may easily go berserk]. The negative 'grid' may happen to be formed by either a spontaneous overlook or vicious change, by the phenomena described by Eq. (7). This must also be taken into account in case of using phone (cellular), because the issues propagated by phone networks may be far from the truth about the bulk of the reality. Moreover, the crystal-like grid of the erroneous smaU messages, created like this, may repel any real managing of the reality. It is because it sex' can be formed actually of very sharp, impressively sharp points, because the set product of the lack of the understanding expressed deliberately in the opposite 'light' (expressed like 'this, we aU agree, needs to be understood') produces them as such. However, when an expert is found for such a problem, the problem needs not to be reaUy soluble or well defined on the set of aU known things. This may lead to the futile engagements. For this it is best to declare the problems on the most general level possible and leave it to be considered by the whole set of the most top experts, each of them trusting individually, that is not to be bossed, or supervised by anybody [2]. 4) On the superiority of 'two-house Eq. (4) of fractional revealing explains why the bisexual 'two-house' (when male and female sex is located in two bodily different partners) reproduction is superior to any other form of the sex 'software'. This is because the parents form a nucleus of a 'crystalline' kind of a 'virtual grid' in the direction of rearing [creation—(re)production], and guarding, their offsprings. Its memory traces are deposited during the time flow in the space by the (wild)life around the parents in focus. These memorize their guarding and feeding actions. The crystaUinity character of this nucleus expels most of the (substantial) danger to their offsprings, though it may attract the predators. This case of 'guarding parents couple' includes also the social rules of the ethics of the formation of marriages. The grid of these rules provides the coherency conditions for the self-regulating genetic selection of the required properties of the next generation (self-developing the population to the future needs of the society) according to Eq. (10). In the overcrowded conditions the grid of the elements Aij^ki [Eq. (11)] prevents the breeding because its elements collide with the availability of the 'society' slots of prospective people's aspiration [22]. One-house sex or child care does not have this property. That is why the children living with one parent only, are so much less protected relative to the children from a complete, two-parent family. However, in the overcrowded or difficult conditions the one-house sex may provide freer rules for breeding, because the conditions of a free copulation (a kind of a modern matriarchate) are less tough than any formal rules of the parentship within a (e.g. Christian) marriage (a possible source of the population explosion [22], with a week genetic coherency, making the population time static, nonadjustable to the technological and other needs and changed in underdeveloped nations). They are however, less coherent, that those of two-house sex and this decreases the speed of the genetic progress of the development of the given community (spice). This kind of improving of a breed may be improved by the type of relations spanned by Eq.s (10-15), which is a hallmark of a pedigree breeding (e.g. of dogs, while in the case of cats the man-controUed 'logic' is much weaker). This includes a record of it aU (e.g. family trees)—a necessity of any kind of coherency. On the other hand, to have more than two guardians does not improve the offspring security, because in the case when the offspring is, at any given moment, with one of its parents (guardian) only, which is often so in the real situation out of their home (nest, den, family house), while the second partner is around to be available in case of further needs, inclusive the provision of the food for the family, the danger to the offsprings decreases exponentially only, with any additional guardian (in a way, a secured family dwelling is a kind of a virtual [third] guardian [22]). Due to this the increase of the safety of the offsprings by the third guardian is already relatively small, which makes the provision of it not economical enough justiiied. The filter of a recognition of a danger is also fikely to work on the principle of Eq. (10), when instead of n persons there is considered a set product of n events, the returns of the parents to their nest, by which there is selected (amplified) sharply the smeU, and other traces, of a possible intruder or a danger. 5) On the safety aspects of a friendship By a similar pattern, any kind of a strong friendship works, especially in dangerous and risky situations, or love, and in the sense of affinity. 6) Further on problems of fractional revealing and feedbacks According to the 'spinning top' [21]), a detailed revelation of the working of Eq. (7) (and its sim- pier form in [2]), development of the fractiona-lizing (which includes any partial) revealing by phone, is correct either for the 'virgin initiation' of the matter, by short calls, or on top of a large volume of a body of information only. In both cases the informational yield is high. Between these two cases, however, there must come written forms, or real personal inspections. If this is not upheld this may lead to a creation of paradoxes, spreads of social phobias, prejudices, etc. These are mostly caused by nonuse of the correct feedbacks to test the minimal necessary relative precision (and also what this means) of the satisfaction of Eq. (4). This includes testing of the convergence of the choice of a set of the experiments Rqì to satisfy the 'equal mark' in Eq. (19). Often the one-step decision technique is used when the saser of IMLSs in focus is considered as a small system with a fully defined informational chart [23], rather than a part of a big system (i.e., the core saser being embedded into th'e rest of the society [2, 7]) which requires using a negative feedback technique [23]. Best to realize this is by the three-way technique: 1) to announce the decision, 2) to check how precisely it is corresponding to the intention, or being fulfilled, and to define the way of correcting it, if this is not minimally relatively precise, and 3) to check the workings of the corrective measure. If the minimal precision is not fulfilled in the sense to progress in a recursive manner, repeating the point 1) again and defining new corrective measures, tiU the minimal relative precision is reached, or being concluded the further attempting, it is not realistic. In the way of discriminating it should be used the minimal possible number of negative criteria, of an elimination, as an example of these are the Ten Commandments of the Holy Bible, rather than a long list of those cases which are considered [8, 21]. In case of the published matter it should be passed everything possible [for example in the case of a 'virgin' text on a new subject the relative precision—see Eq. (6)—is high nearly in any case having a sufficient form], and the referee should be forced to define as precisely as possible the reasons (like further references to be considered), be- cause the set of the mutually shared background experience Aij^u of the referee and the author is bound to be narrow (this may cause a controversial and not too much, relatively precise referee's judgement). Only reaUy provable erroneous papers should be rejected. Otherwise, even a controversial paper is better to be published (because the relative precision of the saser of its referees need not to be representative within the rest of the world science) and let it to be evaluated by the whole mankind—its scientific part. Any other way of dealing with it causes the creation of an extra entropy, and costs, due to it ([8]). 7) On a comparison of the 'lexicographic' and associative kinds of memorizing The brain of the people who memorize easily a controlled amount of information beyond the common short-term memory working pattern [1, 3] form easily the long-term MTs of a large £q. These, however, do not recoil easily in cooperation with any of their surroundings, and this explains why such people, for example linguistically talented people, are likely to lack the associative skiUs, and are not apt to mathematics. On the contrary, the associative brains seem to form easily associations of a short lifetime, which create the long-term memories along a complex dynamic path. This is, however, suitable, for abstract thinking (of a mathematical kind), which is carried upon the eigenvalues of the arrays of short-term data, which needs a fast diagonalization [24]. 8) On the role of informational Forms for the properties of the given society In a parallel analogy, in the direction of the application of the general core to the society, the nations which prefer the published works (Form 3— [2]—the mode of science, and arts) only, because of underdeveloped phone, and other electronic ways of communication and information processing, tend to be heavy, and less short-term creative, though with a permanent memory. This makes them only long-term creative, though cumber-somely, while many detailed correlations are lost (a property of underdeveloped nations, especially the large ones, of old cultures). While the nations with the preference of the Form 1 are very creative in short-term scale (folklore), while having no permanent records left (they are long-term Brownian)—the property of the nomadic nations ([25]). The best is cultivating aU three Forms, with minimal number of taboos and compulsory "do's" and "not-to-do's", functionally unjustified (the condition for optimal, non-noisy cellular automaton [7]). The Form 2 provides the intermediate coupling in the society [9, 13] (modes of management and government). This is performed by the really talented nations (often of a smaller size). They both create long-term memories, and are optimally socially associative, at any required speed, with necessary acceleration. Within this point it is good to realize the role of the private car in the society. It made possible the society 'shake' off the relatively large, and cumbersome, steps of the coherency of the public transport, suitable for medium and large distances, only, which causes a lot of mistiming (entropy) within the everyday life, and replace it with the possibility of any size of the transportation step (within the scale of the personal private everyday life). This has made the modern society the 'talented' one. 9) On the role of the fractional revealing for the understanding among nations The hatred between nations or religions, is created by the projections of any local events and issues, upon very different backgrounds of different integral cultures, in Eq. (7), within the people of different nations or creeds. They project the messages on their particular encounters. It can be applied for this situation the case of interaction between n persons, with n — 2, etc. Namely, this implies without the awareness of the workings of Eq. (7) it can happen to be build a grid of mutual hatred in the form of a 'crystal' of simple mutual prejudices, see Eq. (11), which then expel traces of any in their mutual tolerance. This may result in large scale national hysteria, as known in the history. Such a 'crystal' of prejudices is the sharper the more mutually distant the cultures of those two given nations involved, are. The role of the cultural and political workers is then to make this crystal less sharp, by making the members of the set, defined by Eq. (11), broader, even each its member different, thus the grid amorphous. 10) On the role of publishing The published matter provides the energy to the people of the sasers near to T « 0_. This makes possible to understand the kinetic reason for the efficiency coefficient i] > 1 [15]. Any way of publishing is a form of a fractional revealing of the integrity of the author of the published matter. A given set of published matter has to compete with the pool of the similar matter, and other forms of the dissemination of information in a free style. Any way of making it to be known compulsory to the whole public, and declaring it to be the winner by the definition of the state like, for example, books and public speeches of political leaders of the communist regimes in East Europe, is bound to create dictators with known consequences (due to the closeness of such a system, ending with maximal entropy as possible within the set of constrains of the system). On the political scene, the competition of various political styles in a Free World style must be done only through multiparty system [12]. 11) On the fractional revealing and leadership The leaders create their disciples each of whom grasps and propagates, as his career, a smaller fractional message of his leader teaching. The set of the disciples, by their professional skiU, as enrolled is bound to be seen more 'genial', with T closer to 0_, than their leader, who is more static, even when individually totally more absolutely more unique. He runs his disciples, as 'kites' [16], by which he provides the necessary support (informational energy), as if 'from below' (making it to self-organize, improve and develop his teaching further), to the saser consisting of those of his disciples who have developed his teaching in the particular direction more than he himself, that is those who are talented and independently creative ones on the basis of his teaching (an ad-hoc-gracy arrangement [2, 7, 26]). A leader of the resistance has a high probability to be undiscovered. 12) On the fractional revealing, its physical implementation, and the artificial intelligence The theory presented here is significant for the understanding of the working of the brain and society, and it is a contribution towards the design of the artificial intelligence. It provides for the first time, the foundation of the 'physical logic' for it, a kind of a special representation and realization of the principle of the duality of energy and information [27]. The social design of the system of the institution of a society is also a kind of an artificial intelligence (see the similarity between the structure of the theory of the brain [3-6, 10], on one side, and the scientific sociology [2, 7, 15] and economy [9, 17], on the other side). References [1] Slechta, J., On Quantum Statistical Theory of the Brain—Brain as Generalized Laser. In the Proceedings of the 7th International Congress of Cybernetics and Systems: The Way Ahead, ed. J.Rose, (1987) 919-924. [2] Slechta, J., Ethical Aspects of Expert Systems. In the Proceedings, of the 12th International Congress on Cybernetics, Namur, Belgium, (1989) 58-68. [3] Slechta, J., On Thermodynamics of Thought Processes within a Living Body which exchanges both Energy and Matter with Its Environment. In the Proceedings, of the 12th International Congress on Cybernetics, Namur, Belgium, (1989) 886-898. [4] Slechta, J., On Molecular Foundations of Thermodynamics of the Thought Processes in the Brain. In the Proceedings, of the 12th International Congress on Cybernetics, Namur, Belgium, (1989) 870-877. [5] Slechta, J., On Thermodynamics of Thought Processes within a Living Body in a Changing Environment. In the Proceedings, of the 12th International Congress on Cybernetics, Namur, Belgium, (1989) 878-885. [6] Slechta, J., Brain as a 'Hot' Cellular Automaton. In the Proceedings, of the 12th Inter- national Congress on Cybernetics, Namur, Belgium, (1989) 862-869. [7] Slechta, J., Society as a 'Hot' Cellular Automaton. In the Proceedings of the 13th International Congress on Cybernetics, Namur, Belgium (1992) 405-409. [8] Slechta, J., On Cybernetic Theory of Democracy. In the Proceedings of the 13th International Congress on Cybernetics, Namur, Belgium (1992) 904-908. [9] Slechta, J., On Thermodynamics of 'Hot' (T < 0) S elf-Organizing Processes in an Environment in a Changing Environment. In the Proceedings of the 13th International Congress on Cybernetics, Namur, Belgium (1992) 935-939. [10] Kubo, R., Statistical Mechanics. North-Holland Pubi. Co., Amsterdam, 1965. [11] Kittle, C., Elementary Statistical Physics. John Wiley & Sons, London, 1960. [12] Fain, I.M. and J.I. Canin, Quantum Radi-ophysics. Soviet Radio, Moscow, 1965. [13] Slechta, J., On Thermodynamics of the Brain. In the Proceedings of the 7th International Congress of Cybernetics and Systems: The Way Ahead, ed. J.Rose, (1987) 914-919. [14] Balescu R., Equilibrium and Non-equilibrium Statistical Mechanics. John Wiley & Sons, New York, 1975. [15] Slechta, J., On Cybernetic Theory of the Democracy. Presented at the 13th Int. Congress on Cybernetics, Namur, Belgium (1992), to be published. [16] Slechta, J., On Cybernetic Theory of the Global Knowledge System. Presented at the 13th Int. Congress on Cybernetics, Namur, Belgium (1992), to be published. [17] Slechta, J., On the Theory of Time Scales in Economic Activities. Presented at the 13th Int. Congress on Cybernetics, N.amur, Belgium (1992), to be published. [18] Slechta, j., On the Molecular Theory of the Biological Time (Circadian Rhythms, Psychological Time). Presented at the 13th Int. Congress on Cybernetics, Namur, Belgium (1992), to be published. [19] Gupta, M.M., Regade, R.K., Yager R.R., (Eds.), Advances in Fuzzy Set Theory and Applications. North-Holland Publishing Company, Amsterdam, 1979. [20] Madelung, E., Die mathematische Hilfsmittel der Physik. Springer-Verlag, Berlin, 1957. [21] Slechta, J., On Informational Approach to the Problem of 'Seeded' Experts and Its Ethical Aspects. Presented at the 13th Int. Congress on Cybernetics, Namur, Belgium (1992), to be published. [22] Slechta, J., On the Importance of the Acceleration Term for the Population Dynamics. Presented at the 14th Int. Congress on Cybernetics, Namur, Belgium (1995), to be published. [23] Ashby, R., Introduction to Cybernetics. Chapman, London, 1956. [24] Slechta, J., On Spectral Properties of Neural Networks: Their Relation to Psychological Properties of an Animal. Presented at the 1990 Principle James Williams Congress, Amsterdam (1990), to be published. [25] Bronowski J., The Ascent of Man. BBC, 1973. [26] Tofler, a.. Future Shock. Pan, 1971. [27] Slechta, J., On Quantum-statistical Theory of Pair Interaction between Memory Traces in the Brain. Informatica 17 (1993) 109115. ELEMENTS OF METAMATHEMATICAL AND INFORMATIONAL CALCULUS Anton P. Zeleznikar An Active Member of the New York Academy of Sciences Volaričeva ulica 8, SI 61111 Ljubljana, Slovenia Keywords: axioms of parallelism, serialism, circularity and spontaneity; catalogue of informational rules; decomposition axioms, decomposition theorem, deduction theorems, implicative axioms, inference rules; informational calculus, predicate calculus, prepositional calculus; substitution rule; various axioms and theorems (implicative, conjunctive, disjunctive, equivalent, negatory, etc.) Edited by: L. Birnbaum Received: November 4, 1994 Revised: January 11, 1995 Accepted: February 3, 1995 This article deals with problems pertaining to the elements of axiomatics in traditional (mathematical, symbolic, philosophical) logic and to the problems of newly emerging axiomatics in informational logic. Informational axioms can be derived from propositional and predicate axioms and then, particularized and universalized within the informational domain. Traditional axiomatic formulas of the propositional and predicate calculus can become a rebounding cause for the construction of essentially different axioms in general informational theory. It is shown how propositional and predicate axioms and rules can be informationally extended for the needs of the general informational theory. 1 Introduction Which are the basic and inferential informational axioms^ which govern the derivation of formulas (theorems, consequences), that is, their proving procedures (proofs) in informational theories? This question is significant for the consciousness of that what scientific theories do outside of theories themselves, in their—from theories themselves separated—metatheories. On the other hand, informational theories are always unions of object theories and metatheories, where the last have the role of being the producers of theories in the sense of informational arising, that is, spontaneity and circularity. 2 Fundamental Figures of Syllogistic Inference Syllogistic inference can be interpreted in different ways, for instance, in the scholastic (philosophi- ^This paper is a private author's work and no part of it may be used, reproduced or translated in any manner whatsoever without written permission except in the case of brief quotations embodied in critical articles. cai), informational and traditional-mathematical manner. 2.1 An Informational Interpretation of Syllogism Syllogism (avAXoji], in Greek, means gathering, collecting, assembly, concourse and avXAajtConaL means to reckon, consider, think, reflect; to infer, conclude) (in German, das Zusammenrechnen, der Schluß, die Folgerung) is a valid (e.g., true) inference in a syllogistic form. Syllogistics (in Greek, avXXojiarLKff réxi^i] the art of inferring, concluding) was founded by Aristotle and developed in scholasticism as teachings of (correct) inference in syllogistic form. This technique became the keystone of the traditional logic ([4], pp. 407-409). The inferring in a syllogistic form proceeds from two premises to one conclusion. Thus, the valid inference, the so-called syllogism, with true premises, delivers a true conclusion. In parallel to the traditional logic, as premises of syllogisms, only the following forms of 'equivalent' informational formulas are allowed: 1. "AU X are F(a;)." Formula a; Nva; is a universal affirmative judgement and reads, informationally, x Informs for all x the property (entity) F{x). 2. "No a; is f(x)." Formula is a universal negatory judgement and reads, informationally, x does not inform for aU x the property (entity) F{x). 3. "Some x are F{x)." Formula a; i=3x F{x) is a partial affirmative judgement and reads, informationally, x informs for some x the property F{x). 4. "Some x are not F(x)." Formula a; F(x) is a partial negatory judgement and reads, informationally, x does not inform for some x the property (entity) F(x). The connections among these four formulas can be presented by the logical quadrate in Fig. 1. , ^ contrary , , ^ a; Nv:. F(x)-xl^V:. F(x) sub-aJ-ternate CD sub-alternate a; ha:. F(x) contrary F(x) NcuNb^Nc^ Na^^iha^} The position of the so-called middle entity /.i is decisive and it must appear in both premises in the following manner: (FFl) (FF3) H |=a tt; q- Nb . 0" h=c tt / I \ M Fa tt; ß\=b ((5C)(AC)) II. Axioms of conjimction 1) aab^A, 2) AAB^B, 3) (A-^B)-^ ((A ^ C) ^ (A B AC)) III. Axioms of disjunction 1) A-*AyB, 2) B-^A\/B, 3) (A^C)- {{B C) ^ (AW B ^ C)) IV. Axioms of equivalence 1) (A = B)^{A^B), 2) {A = B)^{B^A), 3) (A S) {{B A) ^ (A = B)) V. Axioms of negation 1) (A-.J)-.(5^1), 2) A^A, 3) A The presented system of propositional axioms is not the only possible. For instance, Novikov [5], p. 75, chooses the group I of implication axioms in the form 1) a^{B^A), 2) (a^(A^C))^((A^5)-(A^C)) Various axioms can be useful for the interpretation of basic informational cases of phenomenalism, as we shall see in one of following subsections. 3.3 Inference Rules of the Propositional Calculus Inference rules of propositional calculus are constructed on the basis of propositional axioms in the preceding subsection. It is hard to say which "rules" are the primary, the axiomatic or the inferential. However, it is clear that inferential rules must strictly consider the primitive axioms of propositional calculus which are, for example, implicative, conjuctive, disjunctive, equivalent and negatory. Which is the general philosophy of making (constructing) a rule, precisely, the inference rule? Irrespective of the theory, for which rules are constructed, these are always implicative, although they express something more than a pure implication, because they concern the so-called derivation procedure. The role of a rule in the derivation procedure is the following: taking a rule in which several premises are logicaEy connected in one or another way, some of them can be detached in the form of the so-called conclusion and, thus, between the respective premises of the rule and its conclusion a special operator, marked by h is used in propositional and predicate calculus while in the informational calculus we use operator -» for marking derivation and an operator |-for marking the circular form of iirforming. Let us settle the general form of an inferential rule for deriving propositional formulas from axioms or from already derived formulas. The first rule is substitution. Let us mark propositional formulas which depend on various propositional variables by the capital Fraktur letters, for example, as 2t or, in more detail, 2l(Ai, A2, • ■-, A„). Let S mark the operator of substitution (in informational terms, the function of substitution). Let us introduce where Q5i, 5B2, • • •, Sn are propositional (identically true) formulas. Thus, the substitution ride has the form 2t(Ai,A2,---,A„) The second production rule is applied to a formula which is structured as a parenthesized sequence of implications, that is, and is expressed in the following manner: if formulas 212, • •-, 2l„_i and are true then formula 2l„ is true in the prepositional calculus. The complex rule of Inference (modus ponens) is 2ln In general, we have the following scheme of inference, where are true premises and are true conclusions too: Cl, 0:2, ■ • -, Cn Deduction Theorem. If formula iB is derivable from formulas 2li, ' • •> then -(SI«-»)•••)) is a true formula. □ By induction it is possible to prove the following: if then 2li, 2I2, ■ • -, 2t„-i h © In case m = n, the senseful inference scheme becomes Ci, C2, • •-, where conclusions til, 0:2, • •-, are detached from premises Cl), 0:2), • • -, "^niÙn, C«) and, according to the convention of derivation formulas, there is Ol h Cl, £J2 h- C2, • • -, Qn Va; »(x) where x must not appear in iB(a). The next inference scheme which comes out is, for instance. respectively, where A is a variable proposition, F a variable predicate of n variables; formula • • •j'fn) includes among their free variables specially marked variables ^i, • • •, in? the number of which is equal to the number of variables of predicate F, that is, n. Rules connected with quantifiers are the following: 1. If ^ 2l(a;) is a true formula and ?8 does not include variable x, then ® —s- Va; 21(.t) is a true formula too. 2. If 2l(a;) ^ is a true formula and 5B does not include variable x, then 3a; 2l(a;) ^ iB is a true formula too. The basic inference scheme (rule of modus po-nens) of the predicate calculus remains 21 2l-> iB 21 21- 21^ (»^ilA This scheme can be extended by a transition from a two-part conjunction to the value domain of a variable a, that is, 21 ^ (» ^ (t(a)) 2i («B _ Va; ^(a-)) where in the premise x must not appear. Analogously, for the existential quantifier, the scheme »(a) ^ 21 »(a;) 2( can be derived. This scheme corresponds to the disjunction scheme 21» C C 2tV £ etc. The listed inference schemes will be used for comparison with schemes of informational calculus. 3.7 Theorems of Deduction within the Predicate Calculus The basic theorem of deduction in the predicate calculus is similar to the theorem in the propositional calculus. But there are several theorems concerning formulas with quantifiers. Deduction Theorems for Predicates. If formula is derivable from formula 521, then formula » is derivable in the predicate calculus, that is, h 58 Further, for formulas including universal and existential quantifiers, there is h \fxF{x) ^ 3xF{x), \/x\/yF{x,y) = \fyyxF{x,y), 3x\^yF{x,y)^yy3xF{x,y), H yx{F{x) ^ G{x)) ^ (yxF{x) ^ yxG{x)), 1- yx{Flx) ^ G{x)) ^ ^ 3xG{x% I- Va;(F(3;) = G{x)) ^ {yxF{x) = ^xG{x)), 3xF{x) = yxF{x), 3xF{x) = yxF{x), 3xF{x) = yxF{x), 3xF{x) = yxF{x) where 21 = *B represents the formula (21 ») a (25 21) □ Proofs for the listed theorems can be found in [5]. 4 Axioms within an Informational Theory 4.1 Introduction The question is how could the axioms of the pro-positional and predicate calculus be turned over to informational calculus. The main difference seems to be between the realm of truth in the traditional logic and realm of information in the informational logic. The informational realm is substantially broader and within it the truth appears only as a very particular case. Instead to say that formulas in the traditional logic are true or false, in the informational logic formulas can inform in one or another way, truly and falsely, particularly and universally, in parallel and serially, straightforwardly and circularly, algorithmically and spontaneously, programmingly and intelligently, routinely and creatively, logically (consistently) and controversially, etc. Informational logic becomes an active part of any informational system, the theoretical and the practical one. 4.2 Axioms of the Informational Calculus Axioms of informational calculus can find a logical support in axioms of prepositional and predicate calculus (Subsections 3.2 and 3.5, respectively). At the first glance, the axiom designer can behave in a withholding way, considering the traditional axioms as much as possible. But, thereupon, when getting the appropriate experience, the designer of an informational theory can go his/her own way, considering the entirety of the possible informational realm. Within this general scope, the true as a particular situation can be replaced by the informational as an extreme attitude of the informationally possible. The discussion in this section will follow the traditional way of axiom construction as much as possible. In the next section the most general and informationally open way will replace the traditional thinking. First, let us classify the informational axioms according to the tradition in the propositional and predicate calculus. This way of interpretation wiU give us the necessary feeling of difference and informational generality in respect to the usual understanding of "logical" axioms. It will be possible to recognize the essential difference which governs the informational realm in its universality in comparison to the classical logical (propositional, predicate) realm. It certainly does not mean that the particular axiom, situation in logical calculuses does not fit the informational principles—it fits them in a particular manner. 4.2.1 "Implication" Axioms of the Informational Calculus In case of implicational axioms, we are concerned with two basic possibilities. At the beginning of the axiomatizing process we are concerned with the so-called informational phenomena-hsm for which we have to design particular axioms giving us the certainty of our initial steps into a general theory of the informational. This means, we have to explain in a formally consistent way the arising of initial axioms themselves. For instance, we must induce the primitive axioms of externalism, internalism and metaphysicalism, which constitute the very general axiom of informational phenomenalism. A.P. Železnikar In Subsection 3.2 we listed the group of axioms of implication. In informational calculus, we have a broader definition of the so-called informational implication, discussed in [10]. The question is where to begin the process of axiomatization in informational calculus. We are confronted with the principal difference existing between the truth in logical calculuses and the informing in informational calculus. In the traditional logic, propositions and predicates inform in a true or false manner. In the informational calculus, informational entities— precisely informational operands—inform and are informed. Thus, we can choose the operand— informational entity—as the point from which one can begin the process of axiomatization. We shall see how different initial axioms wiU become possible and how they wiU be circularly interwea-ved. This axiomatic analysis wiU deepen the understanding of the informational phenomenalism, that is, the phenomenalism of the informational entity. According to Subsection 3.2, axioms I. 1-3, in informational case, the following is obtained: I. Axioms of informational implication 1) 2) (a=^ia=^ß)) 3) 7) ^ (a 7)) where a and ß are informational operands (entities) and represents the operator of informational implication (in the most general and complex form [10]). Prior to the informational systemization of implication axioms, let us look at examples which bring to the surface the logical sense of the listed implication axioms within the informational realm. An axiom of the form (I.l) a ((a h) ^ «) (1) seems to be regular. It means that an informational entity a simply implies that entity a is implied by informing of the entity, that is, by a |=. Theoretically, it seems to be impossible to oppose such an initial principle because the informational nature of an entity is circular in respect to itself and its informing. If introducing a's informing in the form 3a, the last axiom can be expressed in the form a a) (2) This form of the axiom is more general then the preceding one since it presupposes also the phenomenon of informational internalism, that is. a ((h a) a) (3) However, there is not an equivalence between the first (1) and the third (3) axiom on one side and the second (2) axiom on the other side. A resulting system of axioms concerning informational phenomenalism in the sense of the pro-positional axiom (I.l) in Subsection 3.2 is a); e {« i=> N a N (tt N; N ")} or informationaUy explicitly a // ße w N«, a 1= a, h« a or simply and evidently a a In this formula, the essential difference between "informational operators" comma and semicolon must be distinguished (the alternative and the parallel operator, respectively). An extension of the discussed axiom system is evidently the following: a; «N, h«, a\=a, \\ // // \\\ a; a\=, ha, a 1= a, a h; // w a; h«, a 1= a, / I \ 'a N; 1 N« w // An example of this system is not only the axiom (a h) ==> ((h «) (« H) which fits the general axiomatic scheme (I.l), but also (a h) ii\= a)) if arbitrary items of alternative array (a, a |=, 1= a, a 1= a, (a |=; 1=: a)) are chosen. It is to stress that cases of non-informing, that is, a It^, It^ a, a I/ a, etc. are understood as particular cases of informing. Informational axiom (1.2) offers other significant formulas (basic informational implications) which are used, for instance, in informational modus ponens and modus toUens. One of the most important informational axioms, following the scheme (1.2), seems to be which delivers the necessary conclusion a (a 1=) needed in various rules of inference. A resulting system of axioms concerning informational phenomenalism in the sense of the pro-positional axiom (1.2) in Subsection 3.2 is {a=>{a=> ß)) (a /3); or informationaUy explicitly / / / 'a h, \\\ N", a =J> a aha, /ah;^ V V V III / j \\ h", a => a h a. / 1 N ( a h; 1 \ V // a a 1= a. \\\ a 1= a, / I ^ a |=; ha III a /ah, |=a, a h ah; \\ \ = a // The most general extension of the discussed axiom system could evidently be the following: U, a; a h, h«, aha. a h; wv ha // a; "h, ha, aha, a h; wv ha a; ah, N«, a h a, WV ha a; a h, ha, ah", a h; \\\ // a, ah, h aha, a h; ha //// w ha ill One can imagine what happens if the first ß and the second ß in the last formula are chosen as different entities which, in the last scheme, is possible in several ways. Appearances of ß within the alternative scheme (set) are legal independently of the randomly chosen element in each concrete case. It is to mention that some alternative informational schemes concerning the axiomatic attitude wiU also be discussed in Subsection 4.2.2. This particular axiomatic situation can now be transformed simply and evidently into a more general axiomatic scheme of the form A characteristic and progressively diverse form of the last axiom system would be, for example, (a ((a h) (h "))) ((aha)=^(ah;h«)) which shows a phenomenalistic sequence extending in a straight implicative manner from informational entity a over its externalism a h and internalism \= a io its metaphysicalism ah" and phenomenalism a h; N Axiomatic scheme (1.3) delivers a very fundamental property of informing of two entities concerning the third entity. Such axiom is, for instance, . (a (a h)) ^ or also the pair of axioms ((a h) (h ")) (((h a) (a h a)) ((a h) ((a h) ^ (h ")) (((ha)=^(ah;h")) (a h; h "))) ((" h) The general scheme for the implicative rule (1.3) becomes (a ^ /?) ((/3 7) (a j)); ß,i e {a h,t= 1= l=;l= «)} etc., in the sense of the previous examples (I.l) and (1.2). Thus, the informational version of the last system becomes / / '«K \\ N«, a =i> iöe ■ a 1= ft, / , \ ft \ V j // 7€ a K a\=a, w // / / \\\ N a, a 7G - a h ft. ■ V I /// The most general axiomatic version of the last system would be (a (a g\= a) ^ (a h a)) ^ {{a «) «)) This formula is in no way an iiiipossible speculation since all operands are only different phenomenal forms of one and the same informational entity a (with exception of the first and the last operand which are equal). 4.2.2 Another Form of "Implication" Axioms of the Informational Calculus Informational calculus bases on the informing of entities and not solely on the logical truth. As the reader can observe, the discussed propositi-onal and predicate axioms are always identically true logical formulas. We can show how other informational axioms which do not base on proposi-tional and predicate axioms can be derived intuitively, trivially and formally in the same manner as the preceding informational axioms. So let us take the syntactically rearranged axiom (I.l) in the form (a^ ß)=> a instead of a mula (A B) iß a). Propositional for- A is not an identically true formula and its value is A. Axiom (I.l) is called the axiom of the consequent determination. What could the rearranged axiom mean at aU? Let us check its meaning by some basic examples. Let us look the semantic difference between formulas a (ft 1=) a) and (a (ci |=)) a Evidently, from this axiomatic scheme, a "complete" implicative circular formula proceeds: If the first formula says that any informational entity a implies its externalistic informing a |= as a reason of itself, the second formtda stresses that any informational entity a is implied by an implication in which entity a implies its externalistic informing a |=. The reader will agree that it is practically impossible to argue against this argumentation. In informational cases we do strictly distinguish between circular and serially non-circular cases. As soon as a |= appears within the cycle a ((a |=) ==> a), the transition a (ft 1=) represents a part of the "whole history" of the cycle and, therefore, can or must be considered within the form (a {a |=)) a. 4.2.4 Thus, another substantial implication comes to the surface: (a ^ ((a h) a)) ((a ^ (a h)) a) Possibly, this fact becomes evident by the formula (a ^ O^a) a where 3a expresses the entire phenomenalistic nature of a's informing, that is, its hermeneutics (a kind of regular interpretation of a's history) which considers not only the history of both appearing components a and but also transition a Ja (or 3a a in the first case). 4.2.3 "Conjunction" Axioms of the Informational Calculus Let us draw an informational parallel to the pro-positional conjunction axioms (II. 1-3) in Subsection 3.2. What could be the conjunction in an informational sense? How could it be generalized? The logical "and", represented by operator a, means also "and simultaneously" or "in parallel". Informational operator of parallelism is ||= or, commonly, semicolon ';'• Thus, for the first axiom of conjunction (ILI) there is, informatio-naUy, (a \\= ß) a or / \ a; [ß. ==> a and for the second axiom of conjunction (II.2), (a Ih/3) =>/3 or a;' ß For the third axiom of conjunction (11.3) there is (a^ß)^ ((a 7) ^ (a ^ (/3 |h 7))) or, in a common informational form, / / (a =^7) \ a \ a; (« N) "Disjunction" Axioms of the Informational Calculus The sense of parallelism axioms is significant in cases of the so-called informational decomposition (see Section 7). Two characteristic cases are, for example. Disjunction axioms (III. 1-3) in Subsection 3.2 introduce the meaning of informational formula «1, «25 • • • J where commas are used instead of semicolons. What does, in an informational formula, a comma mean at all? InformationaUy, propositional axiom (III.l) can be interpreted as Instead of propositional formula Ay B there is in-formationally, simply a,ß where the last formula just lists two alternatives which are a and ß. Alternatives are informational entities which can be chosen by an informational system. From which point of the philosophy could the discussed alternativeness come from? In an exter-nalistic case, a |=, intuitively, a presumption a \= ß exists, otherwise the externaUsm of a would not perform meaningfully. One can agree that from the process represented by formula a \= ß operands a and ß can be listed. Thus, {a^ß)=>{a,ß) and (a (=) (a,/3) Through this demonstration the step towards the "disjunction" axiom in informational calculus becomes evident. According to propositional axiom (III.2), there is which is another form of the first disjunction informational axiom. It is not meant that the list a, ß is ordered. Finally, according to propositional axiom (III.3), we have (a=>j)=^ iß 7) («,/? 7)) In the last axiom we have to explain formula a,ß 7 additionally; the meaning is the following: (a,/3 = («,/3) {«,/3} a .ß 7; ^ 7 and Thus, a list a,/3 connected with an operator in a formula results into a parallel system. In general, A.P. Železnikar and This short discussion rounds up the possibilities of construction to the propositional disjunctive axioms parallel informational axioms. 4.2.5 "Equivalence" Axioms of the Informational Calculus The reader might observe that we have never defined a rigorous informational formula by which informational operator of implication, would be defined once for aU. In [10], only verbal possibilities of the informational contents of implication have been listed. On the other hand, propositional implication, —is defined by a kind of logical table once for all. Does it mean that the contents (not a rough definition itself) of informational implication changes (arises) from case to case? The answer might be the following: operator is a regular informational operator which, from case to case, can (must) be particularized and universalized, according to the involved operands. So, it must be interpreted only to thè sufficient informational extept. The reader can imagine how cogiplex and never ending interpretation of informational implication would proceed from the basis of its verbal (dictionary-like) determinations. This fact does not restrict the discussion of informational equivalence in which informational implication plays an essential role. Thus, we can put the question of informational equivalence in parallel to the existing notion of propositional calculus. According to the axiom group (IV.1-3) in Subsection 3.2, the adequate informational ,axioms concerning informational equivalence are the following: (a <= ^ß) ^(a (a^ (a- ^a) (« ^ ß)) can (a ß) ^Def ((a a)) Thus, in each particular case, when particularizing operator this particularization depends on the particularization of implicative operator 4.2.6 "Negation" Axioms of the Informational Calculus Informational operator of equivalence, 4 be defined dependently on informational implication, that is, according to deduction theorems of predicate calculus in Subsection 3.7. In this sense. The purpose of the negation of a statement in pro-positional calculus is to obtain the true negated statement, that is, the true otherwise false statement. In informational calculus, an entity informs or can be informed in a certain manner, but not in another one. This last situation can be discussed in the framework of an entity's non-informing. Thus, an informational equivalent to the prepositional situation A is, for example, a and a which reads a does not inform (in a certain manner) and a is not informed (in a certain manner), respectively. Additionally, operator represents only a particular case of operator |=. For a double negation A it is possible to distinguish different cases of double non-informing, for instance, (ab^)l^; a) ^ a) Considering the axiom group of negation (V.1-3) in propositional calculus (Subsection 3.2), there is, informationally, (a^ß)^ iß /?) (a a)); However, to these axioms, characteristic informational axioms concerning the phenomenon of non-informing can be adopted. For example, (a (a h)) (a (a (a (h a)) a)); (ö (« h a)) (« (a a)); (a (a h; ^ a)) (a (a b^; a)) etc. concern operator particularization in the processes of decomposition. 4.2.7 "Predicate" Axioms and Theorems of the Informational Calculus The universal and existential quantifier do not play a significant role in the informational calculus. They are rather very uncommon entities within the informational realm. For instance, operator |=va' reads informs (is informed) for all a's and formulas a |=for_all.a Or « |=Va; Nor-ail_a a or |=VaO;; a |=for^l_a a or. «NvaO; a |=for_all^; |=for^U_a « Or a |=Va; |=Vq: « are very special cases since it is not clear to which informational realm the 'all' could refer. A similar, problematic situation occurs in the case of the existential quantifier where formulas a |=exist_a or a\=3a; Nexist^ a or \=3aa-, a |=exist_a « or a\=3cxOi\ a |=exist_a; |=exist^ OL Or « ]= 3«; |= 3« " Analogously to the predicate axiom group (VI. 12) in Subsection 3.5, the adequate informational axioms could take the form (^(/3) ^ (a 1= 3a («)) The reader can imagine how the operator attribute for all a's- in an informational realm causes that the informational function (f is informatio-nally impacted by ß which is within the realm of all a, etc. On the other hand, informational function f{ß) (as determined in [9]) implies the existence of function (p being dependent on ß, etc. In parallel to the deduction theorems for predicates in Subsection 3.7 it is possible to derive "similar" informational theorems for informational entities. Decomposition Theorems of Informational Entities. If formula ß is informationally derivable from formula a, then formula -^((a l=Va (a j= 3a ((a ^va ^(a)) ^ (a hva "^("B; (a Naa ^ (« ^Va (^(a) (alT^Va (a haa Ma) 9(«))) (a Nva V'H) □ These theorems can cause a retrograde and logically more critical understanding of the predicate theorems listed in Subsection 3.7. 4.3 The Variety of Informational Axioms of Inference One of the basic questions concerning the inference schemes in different calculuses is in which manner inference rules are constructed and accepted by scientific communities. Obviously, the way to various inference rules leads through the understanding of the basic axioms treated in the preceding subsections. An inference rule is nothing else than a means for the derivation (deduction) process where it is used for a constructive transformation of theory-legal formulas into new formulas. The next step concerning axioms and inference rules is the introduction of the so-called replacement rules by which formulas can be transformed automatically, e.g. in a machine-like fashion. Informational rules of inference function like axioms and only by them it is permitted to conclude in a theory-consistent manner. E.g., rules of substitution and modus ponens belong to the most obvious and widely accepted rules for formula transformation within a deduction process. On the other hand, informational inference rules can cover informationally unlimited possibilities and they can come into existence together with specific and particular informational problems. The so-called modi informationis [6] can.be grouped and expressed in several possible ways. We have the following possibilities: 1. Modus ponens is the most obvious inference rule in mathematics in the realm of truth. Informational modus ponens foUows the general (phe-nomenalistic) principle of informing where the mathematical to be true is replaced by the informational to inform. This does not mean that the true is excluded, it only appears as a particular case of the informational. In this sense, informational modus ponens as an inference rule retains the basic logical form which is ß and where the implicational operator has a broadened meaning in comparison with the logical implication operator —determined, for example, by a logical table. Implicit informational operator of parallelism ';' which simultaneously performs as a formula separator replaces the logical operator A (also, a comma in the traditional inference rule). Particularizations of modus ponens can appear as special rules called, for example, modus proce-dendi, modus operandi and others. 2. Modus tollens is a rule of a reverse inferring in respect to the implication formula of its premise. There is a truly substantial difference between the mathematical and informational modus tollens. In the domain of truth, the falsity is the only essential counterpart to the truth and, so, the operator of negation of a formula becomes truly essential. Through the introduction of negation it becomes possible to express the falsity of a statement as its truth (e.g., identically true falsity). In informational modus tollens the negation is replaced by the operator of noninforming (in a certain way), denoted by The reader can now feel the dramatic difference existing between a static state of negation and the dynamic state of noninforming concerning a logical and an informational entity, respectively. Thus, the informational modus tollens in comparison with the logical one keeps the form with already mentioned differences concerning the modus ponens. 3. Modus rectus is not a mathematical inference rule and its origin can be searched in the analysis of the Latin speech. The aim of this rule is the filtering-out (detaching) of the intention marked by imtention(o^)> hidden in entity represented by a through the informing of a, e.g. to an entity represented by ß. It is understood that this intention is an informational function of a which is reflected in ß to which a informs intentionally (or in an intending manner, that is, 'intendingly'). In this sense, a possibility of informational modus rectus becomes o; ((« Nintend ß) ^intentionC«)) (iintention(ö) N)" N ''intention(«)) C ß One can certainly construct 'intentional' rules where the intention or an intention-like entity (functional operand) performs in a certain manner, so, its detachment becomes possible. 4. Modus obliquus belongs to the most contentious inference rules because it usually proceeds from an absurd situation where the inference from a contradictory situation suggest to use the rule for an achievement of the logically consistent result. From a deceitful situation just the absurd inference should help to reach a firm conclusion. In fact, modus obliquus belongs to the so-called discursive informing where through a discourse (as communication, informing, reasoning) by all possible logical tricks, including absurd, contradiction, controversial informing, a valuable conclusion should be detached. In this sense, modus obliquus becomes a discursive filter delivering a useful result. In this sense, one of its possible schemes could be "absurdia) C a; (aabsurd(a) N; h Ö!absurd(")) ß) («absurdC«) aabsurd(a)) C ß where aabsurd(ö) marks an absurd component of entity a hidden in a which phenomenalistically informs /9, so that its informational phenomenalism can be identified in ß as the observer. The presented example of modus obliquus shows how other inference schemes would be possible and how, by further decomposition of the rule and its components, more complex and se-mantically concrete inferential schemes could be developed. 5. Modus procedendi is a mood by which a goal informational entity 0goal(a) wiU be detached from the informing entity a. An example of modus procedendi is (flgoal Cgoal Q^); (« =^goal flgoal) . a Ngoal (Sgoal Ngoal where implication operator is particularized to =4>goai, causing a consequent goal-like informing (operators Cgoal and |=goai)- The conclusion of the inference rule can certainly be extended, bringing other components of the goal structure to the parallel interpretative surface, for instance, Ö hgoal (flgoal Ngoal a); (« Ngoal 0goal) Ngoal 0goal N (Ögoal N flgoal); (ögoal N Ögoal) h 0 goal i To this goal system within entity a other interpretative formulas can be added. 6. Modus operandi discovers the inside of an entity, its modus operandi. The inside structure of an entity a is its metaphysicalism in the form of informing 3a-, counterinforming and informational embedding (Sa, together with counterin-formational entity Ca and embedding entity ta-Thus, the consequent inference rules are nothing else than circularly structured modi ponens, for example, % ' ((((e^ C (Sg) C c^) C (tg) C Jg) C a) ''a 1 7. Modus vivendi is certainly an informational case, for instance, how to infer in an (extremely) critical situation. Modus vivendi does not necessarily consider an extremely logical intention, so it can extend from an uncertain situation, e.g., modus possibilitatis, modus obliquus to modus ponens, as the most certain, approved and standard rule of inference. Informational modus vivendi of an informational realm concerns inference in situations of life and surviving compromises happening under entity's environment, individual, populational and social circumstances [6]. Let the sensory information a„(/3) of entity a observing entity ß inform the a's metaphysicali-stic structure, marked by a ^metaphysicaiistically where the metaphysicalistic structure of a is something represented by the circular formula a H ^ ((£, ^ (c. N ((He N (ea N «))))) and other formulas belonging to the a's metaphysicalistic gestalt [9] of length £ = 6. Thus, \ \ $ N [<^a{ß) N (a NmetaphysicalisticaUy «)) The last formula is nothing else than an informational decomposition of transition ß a where the essential operator frames [9] in this formula are ß \= {(^aiß) \= (a Nmetaphysicalistically «) ) and ß 1= {<^a{ß) N (a NmetaphysicalisticaUy a These cases of transition ß \= a can be interpreted in the form of the so-called operator composition ß o \=a a, that is, ß\=ß ° l=CTa(/3) NmetaphysicalisticaUy ") and ß \=ß ° ho-a(/3)|=metaphysicalisticallya By observing of ß by a, the so-called behavioral information ßheha.vioi{oi, ß) produced by the a's metaphysicalistic structure, through its sensory information Ug^ß) and, dependent on environment /?, has to be detached, where /3behavior(ö, ß) is on the way to assure the survival of a depending on environmental information ß (in the sense of modus vivendi). Within this discourse, the following rule of modus vivendi arises: A.P. Železnikar ((o'aC/?) 1= (a NmetaphysicalisticaUy «)) = /3behavior(a;,/3)) /5behavior(Q:, Senseful other examples of informational modus vivendi can come to the surface in more concrete informational situations and attitudes. 8. Modus possibilitatis roots in the philosophy of modal logic [1]. Instead of ^A which means possibly A (exactly, A is possibly true), we can introduce a |=possibly which reads a informs possibly. A shortcut would be aO- Thus, a<0'/3 is read a possibly informs ß or also ß is possibly informed by a. Sometimes, a |=<> /? is an appropriate notation for a case of possible informational transition. The question is, for instance, which are the possibilities of ^an informational entity a's arising. How can a possibly arise? The possibihty of a's arising dépends on the possible informing of a itself ai/d on informing of an exterior entity, say ß, which could possibly impact a informationaUy. Thus, the basic situation is a double transition a,ß 1=0 a with the meaning (a,ß 1=0 a) / i_ N a ^0 appropriate notation for a case of possible informational transition. In modal logic, the interplay of possibility and necessity becomes the essential point of formula derivation. Thus, in modal logic, a schema embodying the idea of that what is possible is just what is not-necessarily-not is given by the formula <}A ^ (or DA) An informational transcription of this modal formula would be (« ^o) ^ (« 1^) IT^D with the meaning 'a informs possibly' is informationaUy equivalent to 'a does not inform, does not inform necessarily'. The question is again, which are the necessities of an informational entity a's arising. How can a necessarily arise? The necessity of a's arising depends on the necessary informing of a itself and on informing of an exterior entity, say ß, which could necessarily impact a informationaUy. Thus, the basic situation is a double transition a,ß |=a a with the meaning / I \ a !=□ a; /3 No a j \ Let xo mark a structure of informational possibilities, where tti, 7r2, ■ • •, 7r„ C tto- These components can be detached transitionaUy by modus possibiUtatis in the form (a,/?,7ro);((a,/? |=o a) tto) 7ri,7r2, • • • ,7r„ c tto TransitionaUy means, that the conclusion has to be unfolded in the sense of the operator C definition [8]. In general, by informational modus possibilitatis it is possible to infer about possibi-Uties of informing of interrelated entities. 9. Modus necessitatis, also, roots in the philosophy of modal logic [1]. Instead of □ A which means necessarily A (exactly, A is necessarily true), we can introduce a |=necessariiy which reads a informs necessarily. A shortcut would be aO. Thus, aOß is read a necessarily informs ß or also ß is necessarily informed by a. Sometimes, a !=□ /3 is an Let ua mark a structure of informational necessities, where vi,V2, - ■ • -.^n C ua- These components can be detached transitionaUy by modus necessitatis in the form {a,ß,iya);((a,ß \=a a) i^n) TransitionaUy means, that the conclusion has to be unfolded in the sense of the operator C definition [8]. In general, by informational modus necessitatis it is possible to infer about necessities of informing of interrelated entities. 5 Cenerai Schemes of Informational Axioms Up to now we have discussed the nature of informational axioms rooting to some extent in the tradition of mathematical logic. This tradition has its foundation in the groups I-V of propo-sitional .axioms dealt with in Subsection 3.2 and the two predicate axioms in the group VI in Subsection 3.5. The critical question is if these axioms can be generalized in a more radical way as they have been changed in an informational manner through a slight universalization of proposition al operators when replacing implication conjunction A, disjunction V, equivalence = and negation ~ by informational implication , parallel operator (semicolon), operand separator (comma), informational equivalence and operator of a (certain) noninforming respectively. In case of predicates, the predicate expressions Va and 3a representing the appHcation of the universal and existential quantifier, must be replaced by informational operators of the form j=Va and |=3a, respectively, where the concerned entity a had appeared in the operator subscript. At this occasion, the question of the informational nature of logical (predicate) quantifiers had come to the surface as a reflection which, possibly, may demand a deepened (more critical) informational treatise. 5.1 Informing versus Informational Implication Implication belongs to the most significant traditional logical concepts. In this respect, the role of implication is revealed or hidden practically in any logical axiom and inference rule. Implication is the basis of the traditional logical calculus. In informational calculus, the role of implication can be generalized. By generalization, the operator of informational implication, is replaced by the most general informational operator (joker), |=. In this case, the concluding from one true situation to the other can be replaced by informing from one informing situation to the other. In the uttermost situation, this kind of the concluding informing can be comprehended as a general type of inference in which the traditional if-then-ism (implicativeness, causality, consequentiality) is replaced by the most general informational impacting in the sense of informing (informational externalism) and observing (informational inter-nalism), that is, in a form of informational transition occurring (happening) between the informing entity (emitter) on one side and the observing entity (receiver) on the other side. The informational transition between the informer and observer can be discussed in the form of an infor- mational operator decomposition where one part of this decomposition belongs to the informer and the other part of decomposition to the observer. This kind of transitional decomposition between the informer and observer can be understood as the operator composition between two operands. Let us discuss the axiom groups I-V in Subsection 3.2 and the group VI in Subsection 3.5 under the most general informationarcircumstances. There is: I. General axioms of informing • 1) 2) (a ^ (a h/?)) 1= (« H/?); 3) (ah=/3)N((/?N7)N(«N7)) II. General axioms of parallelism 1) (a;/3)h«; 2) {a-,ß)\=ß; 3) ia\=ß)^ ((ah7)l=(«l=(/3;7)) III. General axioms of alternativeness 1) ah«,/?; 2) 3) (a h /5) h ((/3[=7)N(«,/3h7)) IV. General axioms of equivalence 1) 2) {a^^ß)\=iß^ay, 3) (a h/3) h ((/?!=«) h V. General axioms of noninforming 1) (ah/3)N VI. General functional axioms 1) 2) These axioms can be commented in several ways. Axiom (I.l) is evidently a satisfactory one. It says that entity a has, in general, its informer ß and that this fact is informed by a itself. If one takes data Ó, (I.l) becomes Data informs as a fact and cannot be informed. Operator ^ is nothing else than a particular informing, that is, non-informing. Comments to other axioms can become not only very challenging but also provocative, controversial and novel for the usual understanding. 5.2 Generalized Initial Informational Axioms The very initial informational axioms wiU always remain within the scope of the informationaUy possible (the informationally arising). Which could be the most universal (initial, original) informational axioms? To answer this question one must certainly consider the specific informational phenomenalism with its four basic phenomenal forms which are the externalism, internalism, metaphysicalism and phenomenalism. These axioms have not the usual implicative form but the universally informing one. Some of the most general Informational axioms are those concerning an informational entity's basic phenomenalism. For instance, axiom a h ((a h) N «) can be read in the following way: "Operand a informs in such a way that it is informed how does it inform." Axiomatic formula a h ((^ a) h «) can be interpreted as: "Operand a informs in such a way that it is informed how it is being informed." Axiomatic formula a N ((a 1= ") h a) can be read as: "Operand a informs in such a way that it is informed how does it inform and how is it informed within itself." At last, axiomatic formula Ö N ((" |=; 1= a) h a) can mean: "Operand a informs in such a way that it is informed how does it inform and how is it informed as such." The listed four general initial axioms, proceeding from (I.l), are structured in a strictly observer situation when the main operator |= directly follows the leftmost operand a. The other possibility would be a strictly informer situation when the main operators precedes the rightmost operand. For this case, the listed four general axioms become (a h (« h)) N (a h (N «)) N (a 1= (a i= a)) ^ a; (a 1= (a |=;h a)) |= a The point of informer philosophy is that, within the informational transition between a as informer and a as observer (an a-circular case), the entire additional information [a |=, a, a |= a, and (a |=; |= a)], is on the informer side. 5.3 Generalized Inferential Informational Axioms In a similar way as the basic axioms, it is possible to generalize the well-known inferential axioms, e.g., modus ponens, modus tollens, modus rectus, etc. A list of such generalizations of informational inference axioms would be the following: GMP. (a; a 1=^)^/3; GMT. OMR. (a; (a |=intend ß) N '■mtention(a))) |= ((iintention(a) Ni 1= '•intention!o)) C /3); OMO. f Ì U \ («absurd!«) N; 1= «absurdC«)) i= ß J (aabsurd(a) b^; b^ Ö;absurd(tt)) C ß; GMPr. (ßgoal C a;a 1= ßgoal) 1= (a h (ögoal h ")); N Q^) N «a; (C; e:« ^ Ca) 1= c„; (c«; Ce, h N ^a; (<£a; "n C a have the possibility to become informers and observers in informational forward and backward loops of lengths i+1, etc. So, rj^^aj) and are the corresponding gestalts. 7.6 Rules of Alternative Decomposition Rules of alternative decomposition embrace aU discussed rules in this section if the general informational operator (joker) |= is replaced by the general alternative operator (alternative joker) =|. By this replacement, forrnulas' informing(ness) operator becomes the informedness operator, that is, the operation of the Inform(s) is replaced by the operation of the Is/Are Jnformed. The deduction of alternative informing originates from two different sources. The first one comes from regular informing, where the basic rule of informational transition could be oM ß^a This rule determines nothing more than that formula a \= ß can be read alternatively as ß is informed by a, that is, ß =\a. On the other hand, the alternative informing originates in the informational phenomenalism (Subsection 7.1), where a a a a are the principled alternative rules. The basic alternative transformation rules can be systematically inverted regarding to the exter-nalistic, internalistic, metaphysicalistic and phe-nomenalistic case, respectively. There is =|a=|o; =ja =|a a ' a=|' a;=|a' =|a;a=|' Q;=|_a=|_ 0!=|. a =\ a a ^ a a =\ a a =\ a a ' H*^' a=|'=ja;a=|' =1 a; a =1 =| a; a =| =| a; a =| =| a; a =| a Ha a=| a =\ a By these alternative rules, premises can be replaced by the corresponding conclusions of the rules. As an example, the informational alternative-ness enables the following implication: (a h/3) //3 H «; o =1 observe ß't ß |—observe O;; ^ |—observingly ß'i ß H impact o: =|q;' a=|' a=|a' =|a;a=| The meanings of parallel formulas on the right side of are not only informationally significant (logically instructive) but also various in a semantic manner and are the following: - /3 is informed by a; - a is observed by /3; - ß observes a; - a informs observingly ß; - ß is informationally impacted by a; - etc. 8 Conclusion One of the aims of this paper is to show that the construction of an informational calculus is possible in a sufficiently (technically) rigorous way by a similar axiomatic approach known in the propo-sitional and predicate calculus. The difference is certainly obvious: informational calculus covers much wider realm of informational possibilities which may lie beyond the prepositional and predicate philosophyWhat could such assumption mean at aU? The author is aware that the presented construction of the informational calculus is preliminary and that stiU many theoretical concepts must be developed prior to a satisfactory final result. But it becomes also evident that a sufficiently developed theoretical approach builds up the fundament for something called the informational machine [11]. The main problem as seen by the author on this way is the so-called problem of informational arising which is the basic property of any informing entity. This basic property must be supported by the machine hardware and its operating system, that is automatically, when an entity begins to inform as an informational entity of the machine. And, as we have experienced during the reading of the paper, a strong support to the informational arising of any kind lies in the decomposition phenomenality of entities informing serially, in parallel, circularly, metaphysicalistically, and causally. A great deal of the problems pointed out already in this paper wiU be unfolded in the context of the ongoing studies concerning: 1. informational frames and gestalts, 2. informational transition of the form a\= ß, 3. causality of the informational, 4. understanding and interpretation, and 5. informational memory. By these studies, various cases of informational philosophy and formal theory wiU be presented and thematicaUy rounded up with the aim to enable the concept and implementation of the informational machine. 'a good example of axiomatic informational possibilities is a derived axiom which considers the axioms of type 1.3 in the mixed informing-implicative form, that is, References [1] B.F. CheUas: Modal Logic. An Introduction. Cambridge University Press, Cambridge, 1988. [2] M. Heidegger: Sein uad Zeit. Sechzehnte Auflage. Max Niemeyer Verlag, Tübingen, 1986. [3] D. Hilbert und P. Bernays: Grundlagen der Mathematik. Erster Band. Die Grundlagen der mathematischen Wissenschaften in Einzeldarstellungen, Band XL. Verlag von Julius Springer, Berlin, 1934. [4] G. Kwiatkowski (Ed.): Schüler-Duden: Die Philosophie. Dudenverlag, Mannheim, 1985. [5] n.C. Hobhkob: dacmenrim mamemamuueckou AOzuKu. FocyziapcTBeHHoe HsaaTeicbCTBO (|)h-3HKO-MaTeMaTIMeCKOH JIHTepaTypbl (#H3MaT- THs), MocKBa, 1959. [6] A.P. Železnikar: Informational Logic IV. Informatica 13 (1989) No. 2, 6-23. [7] A.P. Železnikar: Verbal and Formal Deduction of Informational Axioms. Cybernetica 37 (1994) No. 1, 5-32. [8] A.P. Železnikar: Informational Being-in. Informatica 18 (1994) No. 2, 149-171. [9] A.P. Železnikar: Informational Being-of. Informatica 18 (1994) No. 3, 277-298. [10] A.P. Železnikar: Principles of a Formal Axiomatic Structure of the Informational. Informatica 18 (1995) No. 1, 133-158. [11] A.P. Železnikar: A Concept of Informational Machine. Cybernetica 38 (1995) No. 1, 7-36. (» N ß) (ß\=7) (« h N 7) This axiom is very useful and causes the so-called gestalt and causal development of formulas. Nonlinear Adaptive Prediction Algorithm and Its Parallel Implementation Ryszard A. Wasniowski New Mexico Highlands University, Las Vegas, NM Phone: (505) 271-1288 E-mail: rwasniowski@acm.org Keywords: parallel computing, gmdh algorithm Edited by: Jerzy R. Nawrocki Received: April 10, 1994 Revised: August 10, 1995 Accepted: September 7, 1995 This paper discusses and shows how computation intensive engineering problems can be modeled on parallel-like simulators and computed efficiently on massively parallel computers. Designed with tens of thousands of processing elements, these machines now offer substantially improved computation times, improved cost performance, and allow rapidly reach higher performance levels. Networks of workstations and software packages such as PVM is another attempt to provide a unified framework within which large parallel programs can be developed on a collection of heterogeneous machines, and make easy transition from sequential processing into parallel processing. The ease of developing parallel algorithms for systems identification using gmdh algorithm will be discussed. 1 Introduction In recent years, parallel and distributed processing have been considered to be the most promising solution to the computing requirements of the future. Significant advances in parallel algorithms and architectures have shown the potential for applying parallel computation techniques for real-time systems. Relatively less attention has been given to software development environments or program construction techniques that are required to translate algorithms into operational programs. This aspect is becoming more important as parallel processing progresses from the research laboratories to carrying out parallel processing at various levels of practical applications. This study approaches nonlinear system identification by using parallel algorithms to form layers of a polynomial network in order to model an unknown nonlinear system. System identification problems have been examined for decades. A substantial amount of work has been done in the identification of systems when outputs are known to vary as linear function of inputs. However, the identification of nonlinear systems remains a difficult problem. Many practical problems in signal processing, control, and machine learning can be cast as system identification problems, where one must gather data from a system whose structure is initially unknown, and build a model of the system's structure. The resulting model can be used for predictions and control of the initially unknown system. This problem compounds when no initial information is available about the system's structure. Once we assume the structure of the system, the problem reduces to a comparatively trivial job of identifying parameters. Identifying and modeling the structure of potentially nonlinear, black-box systems is a problem of particular significance to control engineering and machine learning research. Our approach is motivated by group method of data handling (gmdh). The gmdh is a procedure that attempts to model an unknown system by iteratively connecting layers of nodes that compute polynomial functions. Unfortunately, this method suffers from huge computational overhead. This paper suggests improvement of the gmdh by using parallel computing. This technique was tested in the identification of continuous and discrete time forecasting systems. 2 The GMDH Algorithm The design of a successful control system depends on the ability to predict its response during the given operating conditions. The deterministic approach to complex plant modeling and control often fails because the dynamics of the subsystems and their interconnections are not easily understood. The information available is not enough to construct differential equations for the system, so a different approach based on predictive polynomials is tried. The group method of data handling (gmdh) based on the principle of heuristic self-learning belongs to this group. This approach is intended for the solution of diverse interpolation problems in engineering, such as identification of the static and dynamic characteristics of plants, prediction of random processes and events, optimal control, pattern recognition, etc. The evolution of the gmdh development is easy to follow. It is sufficient to look through the volumes of the journal Avtomatika beginning from 1968. Almost every issue contains papers related to gmdh problems. In a publication (Ivankhni-enko 1969), an appendix is devoted to the new method. In the early stages 1968-1971, the gmdh algorithm was applied to the solution of pattern recognition, identification, and short-range prediction problems. The challenge of noisy data and incomplete information was met in the period 1972-1975. Two ways to handle noisy data in the gmdh algorithm were proposed: multicri-teria choice of the model with a special form of the selection criteria, and the use of additional a priori information (combined method). In the period 1976-1979 it was shown that many multilaye-red gmdh algorithms have a multilayerness error, which is small but sometimes essential. This error is similar to the statistical error in control systems. It was shown also that multilayered algorithms, like statistical control systems, converge to an equilibrium point. Types of convergence were studied more thoroughly later. Many interesting results were found during 1980-82 period. It became clear that physical models (with noise) cannot be used for long range predictions. The stronger the noise, the simpler the models chosen by the gmdh algorithms. So physical models are obtained only for use in identification and short-range prediction. In the period 1982-1983 the various estimators were obtained to deal with mul-ticollinearity of gmdh. Literature surveys show continuous interest in using gmdh for various scientific and engineering applications. To make the ideas about gmdh algorithm clear, suppose that the input consists of N observable Xi, X2, ..., Xjv. It is assumed that the output y may be considered as the estimate of some property of the inputs. In general, y will be some nonlinear function as follows: y = fixi,X2,...,XN) The problem is to find out the unknown structure y=f(.). In solving this problem, a general relationship between output and input variables is built in the form of a mathematical description, which is also called a reference fuiiction. Usually the description is considered as a discrete form of the Volterra functional series or Kohnogorov-Gabor polynomial (Ivankhnienko 1971): m mm y = 0.0 + ^ aiXi + ^ ^ aijXiXj-{- i=l m m m t=l i=l i=l j=l k=l where a is the vector of coefficients or weig-ths. Components of the input vector x = (xi,x2-, -■jXn) could be independent variables or functional terms or finite difference terms. However, the determination of the correct terms and coefficients for this expansion is a difficult task. For a practical use the prediction algorithm should have simplicity, need a small amount of computation time, be well suited for real-time operation and applicable to a small amount of available data. Let us assume that /(.) is represented by a polynomial of a certain order with respect to Xi. The application of Kolmogorov-Gabor polynomial will require a large amount of data with computation of high-dimensional matrices. Iva-khnienko suggested the gmdh procedure for finding out the appropriate polynomial for a given set of input/output data by constructing simple computational networks. In the first step gmdh creates the network first layers by assigning an input node to each independent variable Xj . Subsequent layers are created iteratively as follows: Figure 1: A typical gmdh network. construct n^ - n nodes for the new layer, where n is the number of nodes in the. previous layer; connect the outputs of pairs of nodes from the previous layer to nodes in the new layer, each new node receives output from one of the v? -n pairings of node outputs from the previous layer; find out the output of each node in the new layer by fitting an elementary function of the node's inputs to the y data; remove nodes with high-error from the new layer. (The original gmdh uses the mean-square error as a basis for node elimination.) One possible elementary function mentioned above is a quadratic of the nodes input signals: y = A + Bxi + Cxj + Dxj + Ex] + Fxixj To find these type of polynomial (the coefficients A, B, C, D, E, and F) it is sufficient to have only six data points at our disposal. Repeated solution of the quadratic polynomials above enables us to construct the complete polynomial of any complexity using only these six points. This process continues until performance stops to improve with the addition of new layers. Figure 1 shows a typical gmdh network. Nodes are labeled with their output variable names. Each node computes its output as an elementary function of its input variables. (Note: In this simple example (xikxs) produces no output.) The gmdh can be realized by many algorithms that diflfer with respect to the construction and the complete description. The gmdh algorithm gives us in fact an alternative to deal with matrices of large dimension, and makes it possible to solve complex problems when the data sequence is relatively small. Versions of the gmdh have been applied with some success to engineering, economic and environmental problems. However, the technique suffers from two major drawbacks: the huge computational overhead associated with enumerating all the possible nodes in each layer, and the typical iUs of local search techniques. The limitations implied by the selection of elementary functions are also a target of criticism. Tenorio and Lee ( Tenorio & Lee 1990) have used multiple elementary functions and other modifications to improve the performance of the gmdh. However, the use of multiple elementary functions only increases the computational difficulties associated with gmdh. One can also criticize the comparison of nodes in intermediate layers with the optimal final output. Discarding nodes at an intermediate layer based on a final-output criteria could mislead the system to a suboptirrial network. A more suitable approach could be to maintain several nodes in each layer based on an intermediate measure of their relative merit in that layer. The following section introduces a parallel polynomial network construction algorithm, and attempts to correct the computational overhead deficiency of the gmdh procedure. 3 GMDH Algorithm and Parallel Computing Different systems identification methods based on gmdh with specific ranges of applicability have been invented and well documented. A common feature of most of such methods is the fact that they are realized as sequential computer programs that significantly increases the computer running time. In constructing the multilayer gmdh, aU independent variables in one layer are combined, two at a time, to predict the local polynomial. This offers wide possibilities of parallelism for the information processing operations required in the construction of its models. These combinations can be considered as separate independent blocks performing the same task on different iriputs. The gmdh algorithm could be made more efficient with an array of processing elements (PE), where each block is calculated by a different PE, Such an approach should significantly reduce the computer running time. In order to code the parallel gmdh algorithm the main algorithm should be divided into a number of small processes. Each LAYER 1 yi Xl X2 X2 LAYER 2 ya X3 Xl LAYER 3 yg X3 Figure 2: Ali combinations of variables are independent and can be executed in parallel. process is independent and communicates with other processes by channels. For example, if we have three independent variables in the first layer, three combinations result in estimating three local polynomials as shown in Figure 2. In the second layer, another set of local polynomials should be figured out in a similar manner. In fact, in order to make the algorithm more efficient, a coordinator (host) and an array of processing elements (PE) are needed. The process to calculate the polynomial from the combination of two independent variables is transmitted from the host to the three processing elements and each is provided with a different input. The three processing elements perform their work simultaneously and calculate the required polynomials. These calculated values are transmitted back to the host and further calculations are performed, before moving to the next layer of the gmdh algorithm. The basic steps in constructing a gmdh algorithm are as follows: — the original set of data is divided into training and checking sequences, by separation rule being a heuristic one. Usually the training and the checking sequences are taken alternately. - quadratic polynomials are formed for all possible combinations of x; variable taking two at a time. — for each polynomial a system of normal gaussian equations is constructed using all the data points in the training set. By solving these equations, the values of the intermediate variables yi are determined. - the models are used to predict the system response in the training set data region. The predictions are passed through some form of selection criteria, the most widely used being the mean square error. - the models yi, are ordered with respect to the smallest mean square error. The models with mean square error less then specified thresholds are allowed to pass to the next level of gmdh. The number of functions selected at this level is arbitrary. - at the next level the independent variables for the new training and checking sets are found by mapping the original training and checking sets through the single layer that has been formed. - new polynomials are formed and the above steps are repeated for each layer. As each new layer is formed, the smallest mean square error is stored and plotted as a function of layer number. - the procedure is terminated when the smallest overall mean square error is reached at any level. The global minimum is the point of optimum complexity for this choice of network heuristics. 4 Algorithm Implementation Traditionally, groups of workstations are used as a resource for a series of sequential jobs, but with the development of message-passing software systems a cluster could also work, together on a single problem. While this use of clusters is formally less efficient than running the jobs in a serial fashion, increased throughput can be obtained for time-critical applications. In addition, workstation clusters are an attractive and cost effective parallel software development platform. An application can readily be developed on a group of workstations and ported to moderately parallel machines by only making changes to the software that are inherent to the different FORTRAN and/or C compilers. The two programming tools used for parallel implementations of gmdh were Parallel Virtual Machine (PVM), an Network Linda (LINDA). All the work was done on a Cluster of DEC workstations networked with an Ethernet. These two tools were selected because they were based upon UNIX rather than a proprietary operating system; they are available on a wide range of machines, and they are sufficiently high-level programming tools. LINDA grew out of research work done at Yale University. Scientific Computing Associates is the company formed to bring the product to market. LINDA consists of six operations that access an object called "tuple" space. Tuple space is basically shared memory that is "global" to all the workstations in the network. The PVM (Geist et al., 1993) system is a programming environment for the development and execution of large parallel applications that consists of many interacting but relatively independent components. It is intended to operate on a collection of heterogeneous computing systems interconnected by one or more networks. The participating processors may be scalar machines, multiprocessors, or special- purpose computers. PVM provides a straight forward and general interface that permits the description of various types of algorithms while the underlying infrastructure permits the execution of applications on a virtual computing environment that supports multiple parallel computation models. PVM is a software package being developed by Oak Ridge National Laboratory. It enables a heterogeneous collection of Unix computers linked by a network to operate as a single large parallel computer. Thus, large computational problems can be solved by the aggregate power and memory of many computers. PVM supplies the functions to start tasks and lets the computers communicate and synchronize with each other. It survives the failure of one or more connected computers and supplies functions for users to make their applications fault tolerant. Users can write applications in Fortran or C and parallel them by calling then PVM message-passing routines. By sending and receiving messages, application subtasks can cooperate to solve a problem in parallel. PVM applications can be run transparently across a variety of architectures. The PVM source code and user's guide are available from netlib@ornl.gov. The source has been tested on various types of workstations and parallel computers. In addition, several vendors such as DEC (ALPHA) supply PVM software optimized for their systems. While PVM provi- des a solid programming base, it does not give many options for debugging PVM programs. To help the user in the development of PVM programs, Xab, a run time monitor (also available from netlib) can be used to learn about the PVM programs performance. In developing software, the programmer often designs the initial specifications graphically. Designers can visualize the problem's overall structure far more easily from this graphical representation than from textual specifications. With the Hence graphics interface (also available from netlib) implemented on a workstation, a user can develop a parallel program as a computational graph. The nodes in the graph represent the computations to be performed and the arcs represent the dependencies between the computations. From graphical representation, Hence can generate a lower level portable program, which when executed wiU perform the computations specified by the graph in an order consistent with the dependencies specified. Such a representation enhances the quality of the resulting software. Real-time debugging, visualizing and monitoring are particularly important in a heterogeneous multiprogramming environment where differences in computation and communication speeds result from both heterogeneity and network loads. We have tested parallel gmdh algorithm using various programming tools and architectures, including simulators such as Parallaxis (Braunl 1992), networks of workstations and PVM, also real massive parallel processors. As testing set of data we have selected data from our previous research ( Wasniowski & Wilk 1988). The detailed results of testing the parallel gmdh algorithm can be found in (Wasniowski 1993). In Figure 3 we present an example of output produced by gmdh algorithm. 5 Conclusion Several methods of self-organizing algorithms relating to the system identification and design have been developed, and a common feature of most of them is that they are computationally intensive. To provide an acceptable speed of response for such algorithms the exploitation of inherent parallelism via parallel computing is possible. For the gmdh algorithm the heavy burden of arithmetic 450 7 8 9 10 11 12 13 14 15 Days real values gmdh values Figure 3: Example of output produced by gmdh algorithm. processing can easily be implemented on parallel computers. There is a wide variety of distributed computing tools available both in the commercial marketplace as well as the public domain. We have chosen, implemented, and evaluated two of the more common tools (PVM, and LINDA). These tools provide the user with great flexibility in the manner in which parallelism can be exploited. The tools differ in their implementation as well as their utilization. It should be pointed out that probably the most heavily used and implemented of all the tools is PVM. We have shown that cluster of workstations can be effective supercomputers for implementing gmdh algorithm when combined with appropriate software tools and implemented in a parallel fashion. References [1] Barto A.G., Sutton R.S. , Anderson C.W. (1983) Neuron Like Adaptive Elements that Can Solve Difficult Learning Control Problems. IEEE Trans, on Systems, Man and Cybernetics, Vol. SMC-13, No 5. [2] Benner R.E., Harris J.M. (1991) Applications, Algorithms, and Software for Massively Parallel Computing. AT&T Technical Journal, November/December, p. 59-72. [3] Bramii Th. (1992) Simulation System for Massive Parallelism. International Journal in Computer Simulation , 2, p. 231-250. [4] Duffy J.J. , Franklin M.A. (1975) A Learning Identification Algorithm and its Application to an Environmental System. IEEE Transactions on System, Man and Cybernetics, 5(2), p. 226240. [5] Geist A., et al, (1993) PVM 3.0 User's Guide and Reference Manual, Oak Ridge National Laboratory, Tennessee, February. [6] Heath M., Etheridge J. (1991) VisuaUzing the Performance of Parallel Programs. IEEE Software, Vol. 8, No.5, p.29-39. [7] Ikeda M.O., Sawaragi Y. (1976) Sequential gmdh Algorithm and its Application to River Flow Prediction. IEEE Transactions on Systems, Man and Cybernetics, 6(7), p. 473-479. [8] Ivakhnienko A.G. (1969) Self-Teaching Systems of Recognition and Automatic Control, Tekhnika. [9] Ivakhnienko A.G. (1971) Polynomial Theory of Complex Systems. IEEE Transactions on Systems, Man and Cybernetics, 1(4), p. 364378. [10] Madala H.R.(1991) Comparison of Inductive Versus Deductive Learning Networks. Complex Systems , 5(2), p. 239-258. [11] MuUer J.A.(1990) Macroeconomic Modeling by Means of Self-organizing Methods. 11th IFAC, Tallinn, Vol. 12, p. 50-55. [12] Nishikawa T., Shimizu S. (1985) An Analysis of the Generalized Ridge Estimator in the Adaptive gmdh. J. Soc. Sys. Eng. , 9, p. 53-66. [13] Tenorio M., Lee W. T. (1990) Self-organizing network for optimum supervised learning. IEEE Transactions on Neural Networks , 1(1), p. 100-109. [14] Wasniowski R, Wilk T. (1988) An Algorithm' of Forecasting in Active Systems. Scientific Papers of the Forecasting Research Center, No.10, p. 31-44. [15] Wasniowski R. (1993) The gmdh algorithm and its parallel implementation. Research Report NMHU-RAW 2-93. Termination Conditions for Parallel Shape Recognition Zbigniew M. Wojcik and Barbara E. Wojcik Smart Machines, 13703 Morningbluff Dr., San Antonio, TX 78216, USA. Keywords: parallel shape recognition Edited by: Jerzy R. Nawrocki Received: February 28, 1995 Revised: July 30, 1995 Accepted: September 6, 1995 Elementa.ry features are detected by calculating the number of objects inside-partly overlapping windows fixed in an image plane. Each window's contents is processed by a separate processing element (PE) on a SIMD grid or pyramid architecture. Two neighboring feature chunks are merged by adjacent PEs, and the merged feature chunks are joined in each next Ith parallel step by every 2'th PE possessing complementary and adjacent feature. The shape recognition terminates if a complete set of features (such as curve bounds, endings, corners, segments, regions forks and junctions) making a whole object meet together on one PE. This complete set is proved to he sufficient to terminate the shape recognition. Hierarchy of elementary features for a merging process is established to recognize object bounds and more primitive features first to have a complete feature set -adequate for the consideration by the termination condition at a given level of parallel image recognition (i.e., primal sketch, sketch and 3D world model). The approach has the property of mapping of image segments directly into phrases and English sentences. 1 Introduction a grey level looked for. All adjacent pixels with the same gray level will assume that label in each Many present day computer vision systems ana- ^^^ iteration. The final label is the smaUest la- lyze shapes sequentially. Can a computer see the ^el of any of the connected members. Execution entire picture at once? If so, how one proces- complete when there are no more label changes, sor analyzing one smaU image fragment will know propagation labeling is completed, it is not about the processing performed by many other ^nown which label is the minimum (i.e., perma- processors attached to all other image fragments? Labehng of a spiral (the worst case) will The first pyramid computers process in parallel [8, take iV steps. 16, 19] pieces of contours detected by template Propagation component labeling does not pro- matching. We approach parallel shape analysis vide any information about shape. It is also using a SIMD grid architecture by merging eie- sensitive to accidental discontinuities. The re- mentary features detected during the calculation assignment of the labels in each new step is time of the number of objects within a window. consuming. One improvement would be to record Propagation component labeUng [2] determi- addresses of all pixels tentatively labeled (i.e., in nes, in parallel, the connectedness of pixels of the ^^^ previous step), and then to propagate the new same gray level (assuming that each pixel has its minimum label to the known addresses of PEs. own processor). Given an N x N image, the row- Howevèr, very long strings of addresses would major label Ni+j with i,j = 0,1,..., N-1 is assi- ^^^^ .t« ^^ broadcast to PEs together with the gned to each image pixel. Two neighboring pixels l3,bels. (or subregions) of the same (or similar) gray le- It wiU be shown in this paper, that shape codes vel receive the same (the smaUest) label. Initially, can be handled more efficiently than by recording only the pixel at (0,0) has its own label if it is of and broadcasting the addresses of pixels. Shape can be recognized directly from window gray levels. Our algorithm for shape recognition is faster than the propagation component labeling: it does not waste time re-labeling pixels and broadcasting addresses of individual pixels. Instead, shape codes (representations) are transmitted carrying all the necessary information about the shape components. Information about individual pixels is involved implicit in shape code. SoUin's component algorithm for graphs [6] uses a divide-and-conquer strategy. This algorithm is based on a quadtree decomposition of shapes on the image plane. The image is divided into quadrants. Each quadrant (greater than 1 pixel) is labeled recursively (i.e., by dividing each subsequent quadrant into quadrants up to 1 pixel quadrant). Minimum label is passed through the adjacent quadrant boundaries in each recursive step. The divide-and-conquer strategy is of a logarithmic complexity, but each re-labeling step is very long, as in the propagation component labeling. Re-labeling takes place at iixed quadrant boundaries. Some PEs can specialize in broadcasting labels: single pixel quadrants communicate with single pixels, 4-pixel quadrants with 4-pixel quadrants, 4"-pixel quadrants with 4^-pixel quadrants. Broadcast of addresses of pixels having uniform labels can be efficiently organized, e.g., incorporating a pyramid architecture. But addresses of aU individual pixels carrying the same label must stiU be handled. Methods for finding extreme pixels in each quadrant may ignore a discontinuity inside a quadrant and as a result may merge two or more disjoint objects into one entity, a drawback of the all-components extreme point approach [20, 21] Improving this approach, extreme points of separate objects in a quadrant should be found as a result of segmentation by the divide-and-conquer strategy or by propagation component labeling. Extreme points of individual objects can be found sequentially by an effective algorithm in a contour tracking process [25]. Neither the divide-and-conquer strategy nor the propagation component labeling are capable of recognizing shapes. Even the improved version (suggested above, by propagation of addresses for re-labeling) can handle only addresses of individual pixels, because shapes of re-labeled blobs are not coded. The approaches count adjacent pixels of a similar gray level only and extract them from an image: in addition, they must be followed by a shape approximation process if a shape representation is required. A pyramid technique for parallel detection of smooth curves [8] depends on a bottom-up analysis of the adjacency of elementary curve elements in neighboring blocks (windows) by a higher-level pyramid cell. Each cell of the pyramid records the position and slope of a curved strip and positions of endpoints of the strip. Higher-level cells record more distant endpoints (since a larger block of input image is covered by a higher-level cell). Some higher-level cell will be a root recording a consistent smooth curve. The pyramid architecture designates certain cells in advance to identify many possible occurrences of features. The coordinates of endpoints go directly up the pyramid making a computational burden for some higher level pyramid cell if several curves are detected in the same large field belonging to the cell. The time complexity for such computations is 0(number-of-curves). For instance, two nearly parallel curves must be handled by the same cell at some level. This higher-level cell wiU be a bottleneck for more lines found in its field. A search is needed to match endpoints of strips found in adjacent subfields at a lower level. Doubling back of the same curve wiU also require the same cell at some level for identification. In a process of collecting features such as forks, junctions, regions, corners and curve bounds connected through edges, a node is capable of making a decision whether to look around for some missing features in the image or to complete the image recognition. Classes of objects are composed of some specific numbers of these features. For example, a polygon has only one region. A corner view of a cube has three regions, four forks, nine edges and three corners. The termination condition for a recognition process may be based on the graph theory concepts using some relations between object components. Filler's Theorem [5, 15] defines relation between the number e of edges, the number v of vertices in a planar graph, and the number r of regions (including one unbounded region external to the graph), using the equation: r — e — v -\-2. The Handshaking Theorem 2e — expresses the relation between the number of edges e and the degree deg of all vertices V making a graph. The above two Theorems can be used in computer vision as a termination condition after disregarding an unbounded region and assigning a meaning 'corner' to a vertex of degree 2, 'fork' to a vertex of degree 3, etc., and 'object edge' to graph edge, and 'image region' to the graph region. Euler's Theorem does not classify vertices (i.e., does not distinguish between corner, ending, fork, junction, etc.), and the Handshaking Theorem does not consider regions, which would be disadvantageous for a termination condition of recognition procedures in computer vision. Combination of them both treats all vertices as equally significant. However, in computer vision the hne endings are the least meaningful and should be easily disregarded if a contour is blurred in the image. In general, recognition levels called primal sketch, 2|D sketch and 3D world model are distinguished in literature [3, 14, 18, 22, 23] and should be considered by termination conditions in shape processing. We describe relations between the numbers of lines (i.e., straight sègments or curves) and corners, forks, junctions and regions for computer vision purposes in a way different than used in the literature [3, 10, 14, 18, 22, 23], Tips are not considered explicit in our termination conditions, but any line is constrained as delimited by either endings, or corners, or curve bounds, or forks, or junctions or by combinations on them. In this way endings are implicit in the number of lines in our termination conditions. As in [8], the merging of adjacent features is performed by the nodes one level higher. The image plane is divided into quadrants. We propose a SIMD architecture similar to [8], with the following differences: a) We use special termination conditions for every node to know whether the parallel shape recognition is completed when having some set of features. For instance, the resulting approximation is sent one level up if a complete set of features has not been found yet. b) A few termination conditions are set up, each appropriate for making the primal sketch, sketch and 3D world model in parallel, c) The termination condition for the primal sketch has the highest priority. The sketch has a lower priority, and the lowest priority is for the 3D (3-dimensional) world model, d) The detection Figure 1: Window approximation by mapping of window gray levels into feature name using the number of window objects and the number /<, of window background parts. The symbolic window approximations are: a) segment, b) two segments; c) interior; d) ending; e) fork; f) junction of the elementary features is done by calculation of the window objects instead using the template matching, e) The approach has the property of mapping image segments directly into words and phrases. 2 Feature Detection and Feature Merging Elementary features are detected in a, window using the numbers of window objects [24-26]. Different combinations of the numbers are characteristic to specific image features (as segment, fork, ending, junction, discontinuity). For instance, the name "segment" is achieved if the number of objects equals 1 inside the window and the number Io of background parts is 2 (Fig. 1). For a junction, /iu = l and Jo=4. For a fork, /^,=1 and Io—3. The same numbers are obtained for all possible rotations of the same feature inside the window and for variable thicknesses of the feature. Only one single analysis of window contents (gray levels) is necessary in our method. Elementary features, especially segments, detected in parallel by PEs of a grid or a pyramid net are merged into chunks by higher level nodes. When merging, every two consecutive nodes are where: rA(X*Y) - AX = AY = A{X»Y) « segment "if SXÄSY and AJT« AY » segment. sx ÄSY <=> 1SX-SY! r denotes the reducüon; ^s is an admissible tolerance lor s (slope). rA(X+Y} = AX + anributes • parameters » » ^ + (mass,position,length,slope)-(m,(x,v),l,s), if sx —SY and AX » AY = segment where: m = mx*mY * = 1XX**Y>/2 y = I = Ix^lY s = (sx+sy)/2 No reduction: rA(X+Y) = AX + AY, if AX ^ segment or AY ^ segment Figure 2: Symbolic approximation A{X U Y) of two partly overlapping windows containing segment and approximation A(X U Y ) of the reduced two-window segment involving both the symbolic and a required quantitative window approximation replaced by one node when the corresponding segment slopes are similar. Reduction of elementary segments to a straight line or to a curve is performed in this way (Fig. 2). The merged chunks are united in turn into greater pieces, and so on, until the entire shape has been coded in parallel [9]. Maximum of 2"''" merging operations can be done in each subsequent /th parallel step for a linear feature occupying 2" = iV contiguous PEs. In order to know where to look for some missing chunks, slopes of the possessed feature pieces are used. The missing feature chunks are looked for in the expected directions. Knowledge on the maximum size of the pieces looked for is also available at a given stage of parallel processing: feature size does not exceed the quadrant size belonging to the node at a current level of processing. In our method, names of features and their parameters (including the count of pixels of the same property) are handled instead of propagating a label having nothing in common with the shape name. In particular, a rough set composed of elements consisting of feature names with attached attributes and parameters [24] is broadcast to fixed-address nodes (PEs). The receivers identify more complex features, based on feature adjacency, expectations and constraints. A rough approximation of larger pieces of shapes is done to reduce to a minimum the amount of information representing an object. The rough approximations deal both with symbols (names of features and objects) and with quantitative representations (e.g., with positions, slopes and dimensions of features). Instead of a long process of re-labéling of many pixels, merging of features is performed. A rough grammar [29, 30] can be applied to support the divide-and-conquer strategy. A data-driven execution can guide the parallel shape recognition: every leaf PE wiU wait until the window gray levels wiU become available for the detection of elementary features. 3 A Parallel Recognition of Edges and Regions A rooted tree structure is used. At the bottom level of parallel processing, the leaves are the contents of the windows fixed in the image plane, and then the nodes are the ancestors of the lower level sub-trees. Data received from the 4-children is used for merging of segments, endings, curve bounds, forks and junctions, if the object approximation is not complete. A complete shape approximation is transferable to a host. At the bottom (first) level, all the nodes (PEs) detect their elementary features in parallel by calculating the numbers of window objects [2426]. Each window (Fig. 3) is under the control of a separate PE. Feature name and its particular quantitative parameters (e.g., segment coordinates, slope, length, mass and thickness) are detected by each PE. The same pixels will belong to a number of overlapping windows. To prevent a single object fragment from multiple processing by several PEs, each overlapping window sends its feature approximation to its neighbors in the directions different from the slope of the possessed segment. Among the selected neighbors sharing the same object fragment, one window is chosen Figure 3: Overlapping windows for parallel shape-recognition having the highest (the number of objects). From among a few overlapping windows with the same (highest) I^-, a window is chosen with a feature of the mćmmum mass. Any PE staying active sends its feature approximation to its parent. This feature approximation is merged by the receiver to feature chunks received from other children. The result of merging is sent to the ancestor examining its four children, provided recognition of the entire object was not completed yet. Getting a full set of the features, a parent completes the object recognition. Example 1. PEs#(4,ll) and #(5,10) send their elementary features to their parent PE#(5,11) at the first level of parallel processing of OBJECT 5 in Fig. 4. The PE#(5,11) does not have two endings of the possessed chunk, so it does not announce recognition of a whole object, but sends its approximation to its ancestor, PE#(7,11). Example 2. PE#(2,8) in Fig. 4 sends its ending approximation to the parent PE#(3,9). At the 3rd level of parallel processing, the PE#(3,7) merges the ending detected by the #(1,6) (and received through 2nd level #1,7)) to the segment 'detected by PE#(2,7). The merging of the three element curve (OBJECT 1) involves 5 levels of parallel processing on a pyramidal architecture, because OBJECT 1 is located on the border of different quadrants. The 4th level PE#(7,7) stiü will not receive the ending detected by #(2,8), but the 5th level PE#(15,15) wiU announce reco- gnition of OBJECT 1, because one segment continuous with two endings constitutes a full set of features for the simplest object. In general, the results of merging are sent to a nearest doubly odd PE # (2'i-l, 2'j-l), (2^i-l, 2'i - 1) e {{l,2,...,iV - l},{l,2,...,iV - 1}}, iV = 2", on a grid configuration, where merging is done on any couple of adjacent segments (Fig. 2) by execution of a{fo-wn U fneighbor, s}, where s is a merging operation, / is a feature approximation [24], a is a requested approximation of merged features (qualitative A or quantitative A, see Fig. 2), and I is the level of parallel processing. Merging is skipped if two feature chunks do not match each another symbolically. Example 3. At the third parallel processing level (Fig. 4), the ancestor PE#(7,7) merges three feature chunks received from its children PEs#(3,3), #(3,7) and #(7,7). The chunks involve two endings and make a fuU set of features, so PE #(7,7) announces identification of the entire curve (OBJECT 3). Example 4. On the second level of parallel processing, the nodes #(13,1) #(13,3) and #(15,3) send approximations of their chunks to their parent PE#(15,5). The 3rd level PE#(15,5) and PE#(15,7) send their features to 4th level PE#(15,7) which performs merging and having two endings and a one line announces identification of the curve (OBJECT 2). A formal specification of the termination condition for parallel shape recognition is helpful for appropriate control of execution of programs by nodes (e.g., to know, when segmentation of a single object is completed when having several distinct objects). THEOREM 1. Parallel recognition of shapes involving only endings, straights, curves and corners (without regions, forks or junctions) is completed, if: L^C + 1, (1) where C is the number of corners or curvature bounds (such as upper, lower, left and right bounds), L is the number of curves or segments with two endings (e.g., connecting: corner - corner, bound - bound, corner - ending, bound - ending, corner - bound, ending - ending). PROOF (inductive). Consider Figs. 4 and 5.a as examples of simple drawings. Having no cor- 10 13 14 -x X X OBJ lECT X X 01 JBC r X ÜDJ ECT X '5 i • X f X X X X • X « •. • X X X- X ODJ 1 ECT X ■ « a X fl ■ X X X • t X X • -X X X X • X X 1 X fl 1 X Xii X X • • X X OBJ 3cr fl • fl 4 « ■ Figure 4: Examples of simple drawings on a grid configuration. Each square represents a PE. To involve the functions of a pyramid, some selected grid nodes are assigned also the functions of nodes of higher level pyramid nodes. Squares with one dot represent both the leaves and the second level nodes of a pyramid, squares with one dot and circle represent both the leaves, the second level nodes and the third level nodes ners nor curvature bounds we have i = 1 (i.e., in the basis step there is only one ending - ending connection). When incrementing L by one, the first and the last segment (or curve) must have a ending (because in this THEOREM a drawing is assumed to be without forks, junctions and regions). In the inductive step let us notice, that any new single corner or curvature bound (denoted by C) increments L by one, and then the true equation (i + 1) = (C + 1) + 1 reducing to Eq.(l) is achieved when assuming the truth of the inductive hypothesis (Eq. (1)). • Any element which does not have the entire object (i.e., with a complete set of endings, cur-/ature bounds and lines (THEOREM 1)) sends the possessed object approximation one level up to its ancestor. Exa,mple 5. OBJECT 5 in Fig. 4 has one corner (or right bound represented by PEs #(10,6) and #(10,7)) two endings and two lines, so Z = 1-f-l = <3 7 (a) (b) Figure 5: A few simple drawings satisfying: a) Eq.(l); b) Eqs.(2) and (4) (the last 3D object with shading having: L=24 Unes, C=5 corners, R= 7 regions, F=9 forks, J = \featuresi\ = 1 junctions and \features5\ — 1 and yielding: L = 24 = \features5 |*4-FJ*34-F*2-fC*5-M-7 = l*4-|-l*3 + 9*2-f 5-1-1-7 2. The 5th level ancestor (root), PE#(15,15), receives two endings from 4th level children, PEs #(7,7) and #(7,15), and detects one right bound based on approximations received from 4th level PEs #(15,7) and #(15,15). The 4th level \ a; b) \ J d) B\ Figure 6: Different type endings A, B of a fiat segment: a), b) non-homogeneous signify no curve bound; c), d) homogeneous endings signify a curve bound PE#(7,15) does not announce identification of an entire object, because it has only one ending. The 5th level PE#(15,15) has a complete set of features, hence it announces recognition of the entire OBJECT 5. Many horizontal or vertical segments do not form object bounds and then they do not affect the counters C and L in, Eq.(l). Any horizontal segment ended by a non-homogeneous ending (e.g., either by a left-lower and right-upper bounds (Fig. 6.a), or by upper-left and lower-right bounds (Fig. 6.b)) does not form curve bounds and as such does not increment L nor C. LEMMA 1. Any flat segment (horizontal or vertical) delimited by a nonhomogeneous ending (see Fig. 6) can be taken apart from a curve bound. PROOF. Let A and B be nonhomogeneous endings of a flat segment. Approximations of the two nonhomogeneous endings meet at some level of parallel processing contradicting a bound of a horizontal segment (Fig. 6.a) or a bound of a vertical edge (Fig. 6.b). Only homogeneous endings (i.e., either lower-left and lower-right, or upper-left and upper-right (Fig. 6.c), or upper-right and lower-right (Fig. 6.d), or upper-left and lower-left) meeting at some node of the processing tree and delimiting the same segment form a curve bound. • LEMMA 2. Complexity of the detection of a flat nonhomogeneous segment or a curvature bo- und is log2 (flat .segment Jength) or log^ {curve -bound Jength) steps. PROOF. Endings of the same flat segment (hypothesized bound) occur to be contradictory after log2 {flat ^segment Jength) steps, and information about this contradiction is utilized or transferred up instantly. Information about non-contradictory segments is processed in the same way. • Any horizontal or vertical segment may be coded in parallel according to the method presented in [28] (see Fig. 7). The described above parallel processing associated with the primal sketch goes through levels until the entire continuous linear object has been collected (i.e., until Eq.(l) is satisfied), accessing the children distant by 2' or by nodes in each /th level of pro- cessing. Any fetched feature chunkl is merged with the matching possessed feature chunk2 by executing a{chunkl U chunk2, s), where a denotes the symbohc or quantitative approximation of the operands listed in the parentheses (compare Fig. 2), and s is the merging operation. THEOREM 2. Parallel recognition of shapes involving endings, straights, curves, corners and regions and without forks or junctions is completed, if: L = C + 1-R, (2) where R is the number elementary regions, L and C have the same meanings as in Eq.(l). PROOF (inductive). For an object without regions, forks and junction the Eq.(2) reduces to Eq.(l). For an object consisting of one region only (i.e., for a circle) we have L=4, C=4 and R=l, so the basic step is proved. For the inductive step observe, that any new single region decrements i by 1 changing the inductive hypothesis (2) to L - 1 = C + 1 - {R + 1) and satisfying directly Eq.(2). Example 6. There are no endings in the OBJECT 4 in Fig. 4. In the 2nd level of processing, the PEs #(15,11) and #(13,11) send their approximations to 3rd level PE #(15,11), and PEs #(15,13) and #(13,13) to 3rd level PE #(15,15). These 3rd level PEs detect the upper and lower object bounds, but they do not have the fuU sets of features. The 4th level PE#(15,15) detects the region and two bounds more: left and 386 Informatica 19 (1995) 379-389 Z.M. Wojcik et al. 10 11 12 14 IS -1.2.3 4.«. 9. IO.lt. •U.I4- (b) -l.J.3 4. S. «. » -1J.14- (c) -13,14 •l.IJ, 4.S.(, 10.11. Figure 7: Stages of parallel shape recognition of two disjoint horizontal (or vertical) segments on a two-dimensional array of PEs [28]. Dots represent presence of elementary segment detected by a PE, arcs show the transfers of messages containing feature chunks, mark '-' denotes a segment bound or ending: a), b), c) merging at the second, third and fourth levels of the parallel processing. PE#15 receives full set of the short segment in the third stage of parallel processing, and the long segment in the fifth stage (d) right. It has the full set of features satisfying Eq.(2), so it announces recognition of the circular object. 4 Involving Forks and Junctions Endings are given the highest priority in merging to adjacent features, because endings are not counted by Eqs.(l, 2). Somewhat lower priorities should be assigned to curvature bounds, corners and horizontal or vertical nonhomogeneous segments when merging them with oblique segments when making the primal sketch when collecting patches or blobs using Eq.(l). When detecting regions from patches, the patches are expected to be reconstructed already from bounds, corners and curves. Patches should have a lower priority than regions when making the sketch using Eq.(2). One approach in processing shapes is to assume that the priorities of processing forks and junctions are lower than those for regions and patches, because forks and junctions form 3D objects from the 2\D sketch. Then any regions and patches are merged to forks and to junctions. Forks and junctions incur more complexity. Shapes involving forks and junctions are also amenable to a rule checking a full collection of primitive components of 3D objects as shown below. THEOREM 3. Parallel recognition of shape involving forks and junctions is completed if the following terminations condition is satisfied: L = J*3 + F*2 + C + 1-R, (3) where J is the mumber of junctions; F is the number of forks; L, C, R have the same meanings as in Eq.(2). PROOF (inductive). We assume the truth of Eq.(2) for the basis step. Let Eq.(3) be the inductive hypothesis. Any single fork increments L by two giving L + 2 = J*3 + {F + 1)*2 + C+1-R and reducing to Eq.(3), and any single new junction increments L by three giving L + 3 = (J + 3)*3 + F*2 + (:;' + l- ižand reducing to Eq.(3). The lines L, bounds C, forks F, junctions J and regions R (i.e. delimited by closed curves) are counted by ancestors on each level, of parallel processing. Because of a higher complexity and lowest priority of forks and junctions, Eq.(3) can be checked only at nodes detecting forks and junctions. Partial approximations of object fragments adjacent to the forks and junctions will be sent to these nodes. THEOREM 4. Parallel recognition of shape involving any elementary features detectable by the numbers Io and of window objects (Fig. 1) is completed if: L= \featuresf\* f + 1- R (4) featuresf where \featuresj\ is the mumber of features of the order /. The feature order f is defined by the number Io of window background parts minus one, i.e.: f = Io-1 (5) For example, lfeaturesf\ = for / = 2 is the number of forks, and \featuresf\ = C for / = 1 is the number of corners or curve bounds. PROOF {inductive). We assume the truth of Eq.(3) for the basis step (i.e., when having 0 features of orders / > 2). Let Eq.(4) be the inductive hypothesis. Assuming the presence of only the features of one selected order / > 2 and junctions J, forks F, corners of bounds C with possible regions, any new single /-order feature, / > 2, increments X by / yielding L + f = {\featuresf\*f+l) + J*3 + F*2 + C + l-R and reducing to Eq.(4). The same is true for features of any order /. ' • DEFINITION 1. An object is said to be recognized if the numbers L, C, F, J, \featuresj\, R satisfy one of the Eqs.(l), (2), (3) or (4), and if each of its lines contains two endings, such as ending-ending, or ending-bound, or bound-bound, or ending-fork, or bound-junction, etc. THEOREM 5. When object shape recognition is terminated, the root of the parallel computation has a complete set of features (i.e., one of Eqs.(l), (2), (3) or (4) is satisfied at the root). PROOF. In each step of parallel processing the number of branches of any computation tree decreases because of the merging processes. Because of different priorities, Eq.(l) is checked first to detect aU 2D drawings and patches. If the drawings are part of regions or are adjacent to regions and planes, then Eq.(l) is not satisfied because it does not consider regions. If image regions are considered, then the regions may be a part of 3D objects or adjacent to them, and then Eq.(2) is not satisfied because it does not consider forks and junctions formed by regions or planes. Hence, Eq.(3) must be used, or even (4). Only two cases are possible: a) A node processing one object contains a partial set of features (e.g., the shape recognition is not completed yet or an object is only partly located in the image plane), or b) a node is a root and has a complete set of features. • THEOREM 6. Any feature or object merged and collected by a node in the last step of a completed parallel processing is continuous. PROOF. If there is a full set of features collected by the node then aU the features must make one entity. Any disjoint set of features (in the image plane) has its own fuU set of features (satisfying one of Eqs. (1) to (4)). • LEMMA 3. The complexity of the parallel shape recognition is 0{log2{objectjmaximumJength)) parallel stages. PROOF. When collecting (and merging) features of an object of the maximum length N, < N < 2', each new step involves 2 times nodes less, where I is the level of parallel processing. • 5 Conclusions The step of parallel shape recognition entails collecting adjacent feature segments and merging them together according to partly known object chunks. In general, the parallel shape recognition creates a topological graph of the absolute or relative positions of features and their particular parameters. The graph nodes are labeled by feature names, and arcs represent relations on the features. Thus, the feature names and their parameters are determined and localized through the object shape. The approach follows the cri tenon of simplicity: a generalization of the Gestalt laws saying that the least information is more likely to be the best [18]. The least information becomes representation of the most regular shapes derived from the picture and assumes the names for the shapes. The least information must be on the symbolic level, because only symbolic information is independent of possible orientations of the pattern in the field of observation [24, 26]. The symbolic representations of features is shown to be invariant in the space of observation. The approach has the property of mapping an image fragment directly into words and phrases. Mathematical calculus for the proposed parallel shape recognition can be based on the concept of the rough sets [24, 12, 29, 30]. Template matching (see [18]) is a time consuming, rotation-dependent and ambiguous. Hong, Shneier, Hartley and Rosenfeld [8] merge in parallel small feature pieces into entities on a pyramid architecture, to speed up the recognition of image edges from matched templates. They exploit good continuation of adjacent window edges to remedy the ambiguity in interpretation of edges matched by single (separate) templates. The proposed parallel shape recognition method is less ambiguous when compared to template matching (because feature names are detected in a deterministic, and not in a statistical way) and when compared to chain coding (because is resistant to variable thickness and discontinuities of objects). Parallel relaxation [17, 13] can improve the algorithms to cope with the problem of discontinuities in the analyzed figures. Our symbolic and quantitative evaluation of window contents and merging of elementary features into wholes is also a remedy to the problem of ignoring feature continuity by pure clustering methods. For example, the Hough transform [4] in some cases may lose the track of good continuity of edge by treating collinear strips far away from each other as proximate segments. The good continuity is not lost, however, if a separate Hough transform is made for different window contents (extremely helpful when the number of background parts is 1). Our termination conditions of shape recognition is applicable not only to the 'block world', but also to objects with curved surfaces. The up-to-date experience with the sequential implementation of the shape detection method [24-26] prove the following: there is much less ambiguity in interpretation of elementary and complex features, when compared with template matching. The method is resistant to variable thickness and discontinuities of edges. Is not sensitive to a variety of disturbances. A window is analyzed only once. Particular parameters of features are determined with great precision. Underlying subroutines have already been tested on complicated patterns consisting of lines, arcs, corners and forks, and with very good results [24-26]. The termination conditions has been successfully applied for sequential shape recognition, too. References [1] D.H. BaUard, C.M. Brown, Computer Vision, Prentice Hall, 1982. [2] W.T. Beyer, Recognition of topological invariant by iterative arrays, Ph.D. thesis, MIT, 1969. [3] P.R. Cohen, E. Feigenbaum, The Handbool< of Artificial Intelligence, Addison - Wesley, 1982. [4] R.O. Duda, P.E. Hart, "Use of the Hough Transformation to Detect lines and Curves in Pictures", Communication of the ACM, Vol. 15, No. 1, pp. 11-15, 1972. [5] R.P. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, 1989. [6] D.S. Hischberg, A.K. Chandra, D.V. Sarwate, "Computing connected components on parallel computers". Comm. ACM, 22, 1979, pp461-464. [7] T.H. Hong, M. Shneier, "Extracting Compact Objects Using Linked Pyramids", IEEE Trans, on FAMI, Vol. PAMI-6, No;.2, March 1984, pp229-237. [8] T.H. Hong, M. Shneier, R.L. Hartley, A. Rosenfeld, "Using Pyramids to detect Good Continuation", IEEE Trans, on Systems, Man and Cybernetics, Vol. SMC-13, No.4, July / August 1983, pp631-635. [9] K. Hwang, F.A. Briggs, Computer architecture and parallel processing, McGraw-Hill, 1984. [10] G.F. Luger, W.A. Stubblefield, Artificial Intelligence and the Design of Expert Systems, Benjamin / Cummings, 1989. [11] R.S. Michalski, J.G. Carbonell, T.M. Mitchell, Machine Learning: An Artificial Intelligence Approach, Morgan Kaufmann, 1986. [12] Z. Pawlak, "Rough Classification". International Journal of Man-Machine Studies, 20, 1984, pp469-483. [13] J.M. Prager, "Extracting and Labeling Boundary Segments in Natural Scenes", IEEE Trans. PAMI, v.2, No.l, ppl6-27, 1980. [14] E. Rich, Artificial Intelligence, McGraw-Hill, 1983. [15] K.H. Rosen, Discrete Mathematics, Random House, 1988. [16] A. Rosenfeld, "Some pyramid techniques for image segmentation", NATO ASI series, Vol.F25, in: Pyramid Systems for Computer Vision, Eds. V. Cantoni S. Levialdi, "Springer-Verlag, 1986, pp261-271. [17] A. Rosenfeld, R.A. Hummel, S.W. Zucker, "Scene Labeling by Relaxation Operations", IEEE Trans. Syst., Man, Cybern., v.SMC-6, pp420-433, 1976. [18] A. Rosenfeld, A.C. Kak, Digital Picture Processing, Acad. Press, 1982. [19] M.O. Shneier, "Extracting Features from Images Using Pyramids", IEEE Trans. Syst., Man, Cybern., v.SMC-12, No.4, pp569-572, 1982. [20] Q.F. Stout, "Broadcasting in mesh-connected computers", Proc. 1982 Conf on Inform. Sci. and Systems, pp85-90. [21] Q.F. Stout, "Supporting divide-and conquer algorithms for image processing", Journal of Parallel and Distributed Computing, 4, 1987, pp.95-115. [22] S. Tanimoto, The Elements of Artificial Intelligence, Computer Science Press, 1988. [23] P.H. Winston, Artificial Intelligence, Addison-Wesley, 1984. [24] Z.M. Wojcik, "Rough Approximation of Shapes in Pattern Recognition", CVGIP, 40, 228-249, 1987. [25] Z.M. Wojcik, "A Natural Approach in Image Processing and Pattern Recognition: Rotating Neighborhood Technique, Self-Adapting Threshold, Segmentation and Shape Recognition", Pattern Recognition, v. 18, no.5, 1985, pp299-326. [26] Z.M. Wojcik, "An Approach to the Recognition of Contours and Line-Shaped Objects", CVGIP, 25, 1984, ppl84-204. [27] Z.M. Wojcik, A. Rosenfeld, "A Shape Coding Array", Pattern Recognition Letters, 4, 1986, pp57-59. [28] Z.M. Wojcik, "A Parallel Shape Coding on SIMD Architecture", Proc. IEEE Intern. Workshop on Tools for AI, Fairfax, Oct. 1989. [29] Z.M. Wojcik, "The Rough Grammar for Parallel Shape Coding, Proc. ACM South Central Regional Conf, Nov. 1989, Tulsa. [30] Z.M. Wojcik, B.E. Wojcik, "A Rough Grammar for a Linguistic Recognition of Image Patches", Signal Processing, 19, 1990, ppll9-138. Fundamental Tasks in Software Development Environments Lars Bendix Institute for Electronic Systems Aalborg University Fredrik Bajers Vej 7E DK-9220 Aalborg Denmark E-mail: bendix@iesd.auc.dk Keywords: software development environments, taxonomy, configuration management, version control, personnel management, resource control Edited by: Johann Eder Received: December 12, 1992 Revised: February 9, 1993 Accepted: March 1, 1993 After having established the basic terms of the field of software development, we present a conceptual framework to help establish the key tasks to be performed in this field. The field is characterized by two orthogonal concepts: Programming-in-the-Large (PitL) and Programming-in-the-Many (PitM). These concepts can be further subdivided into the tasks of Configuration Management and Version Control (for PitL), and Personnel Management and Resource Management (for PitM). The main body of this paper is dedicated to a thorough analysis of these tasks. The conceptual framework is then applied to two systems to show how to use it to evaluate and compare systems. Finally is given a discussion of the presented framework, both in its own right and with relation to other work. 1 Introduction In this paper we will develop a conceptual framework for the tasks which are carried out in a Software Development Environment when developing software. In this context a software development environment will simply mean an environment which supports the development of software. This covers a wide span of quite different systems ranging from early and simple toolkit like systems as UNIX [22] and A Programmer's Workbench [13] to fully integrated systems as Adele [5] and Mj0lner [3]. In this field many different problems are encountered such as Configuration Management, Version Control, Personnel Management, and Resource Management. The present software development environments cover some or aU of these aspects to a varying degree. Initially the emphasis was on a simple integration of tools for configuration management and version control obtaining a new more powerful tool as done in RCS [26]. Later systems have put more emphasis on obtaining a uniform description and using a data base as the means of integrating more than just the tools for configuration management and version control [16]. They have also attacked the problems arising from the distribution of a project on many different workstations [25]. Or they have tried to solve problems connected to having to deal with coordination of many people, such as security schemas and management policies [18]. However, neither these early attempts nor present systems are complete and cover aU of the topics. Furthermore, the lack of a fixed terminology in this field - although one is proposed by Tichy in [27] - and the fact that the systems handle the topics randomly and in isolation tends to obscure a thorough understanding of both the systems and the area. For this reason a taxonomy (a check-list) is needed to remedy the situation and to provide us with a conceptual framework to highlight the differences between software development environments. Such a framework can be useful for: - evaluation of an environment. Classification according to its characteristics. Comparison of properties between different environments. Focusing on central and relevant aspects. - development of a new software development environment. An overview of what it has to include. A guide to the possible choices for each topic. Focusing on central and relevant aspects. - understanding better the field of software development. Focusing on central and relevant aspects. In the next chapter we give a short, general introduction to software development environments. In chapters 3 and 4 we focus on the tasks carried out within the fields of Programming-in-the-Large (PitL) and Programming-in-the-Many (PitM) respectively. This is followed by a discussion, in chapter 5, of the usefulness of the conceptual framework and its relation to the future development of software development environments. Finally, we draw our conclusions in chapter 6. 2 Software Development Environments Before we can give a more precise definition of what a software development environment is, we have to agree on some of the basic concepts of the field. A fixed standard terminology for software engineering has not yet emerged. Often different terms are used to cover basically the same ideas, or the same name is used for different ideas. This makes it very difficult and confusing to compare and evaluate different software development environments, and the need of some standard terminology is obvious. Here we wiU give some informal definitions of the basic concepts concerned and the conceptual framework will serve to give a coherent presentation for the field as a whole. - Component. A component is the basic block used to put together a system. It can be either atomic or composed from other components in an aggregation hierarchy. Samples of components are, among the others, the chapter of a book, a part of a program, the blueprints of a machine, or even an entire program. - Version. A component evolves while time passes. The result of making a change to a component is anew changed copy of the component. This modified component is called a version of the original one. - Configuration. Components are put together to form a system. The term configuration denotes both the actual description of how to build a system and the system itself. - Version control. This is the art of controlling the creation of new versions. The goals of version control are to save space, so that versions can be kept in as little space as possible, and to enforce a structure on the evolution of a component so that such evolution is observable and controllable. - Configuration management. This is the art of controlling the creation and the composition of systems. The goals of configuration management are to save time in the (re)generation of a system, and to enforce a structure on the way a system is built. In the context of software development environments the meaning of component can be given more precisely. The components involved will be modules, specifications, documentation and other material/documents related to the development and maintenance of software products. A software development environment is an environment or tool, which supports the development and maintenance of software systems through all of the life-cycle, that is from requirements through coding and testing to documentation and user manuals. It helps to coordinate and manage the plethora of documents in various versions and it serves to integrate the many tools which handle different types of documents and perform different tasks. The most commonly performed and supported tasks in software development have to do with configuration management and version control. Also tools supporting activities for Programming-in-the-Small (PitS), like syntax-directed editors, can be considered part of a software development environment. However, they work on a more fine-grained and less abstract level and will therefore not be treated in this paper. Instead, we will include activities carried out within the field which Dart et al. [11] have coined as Programming-in-the-Many. In their paper it is defined as "tasks such as project and team management". In this paper we will investigate this term in further depth to get a better understanding of exactly what it covers. Software development environments have undergone an immense evolution over the past 10-15 years. Early environments being primarily conceived as the operating system enhanced with a couple of specialized tools for the handling of configuration management and version control. By means of ordinary text-files the tools were integrated in a very loose way with each other and with the rest of the environment (or operating system). Later environments saw an emerging notion of some kind of simplistic data base to contain the components and to act as the medium of integration. Components were no longer considered unstructured text-files, but rather black boxes with an internal (hidden) structure for which there could be given an external and uniform description. Furthermore, distribution became a subject of interest. Present environments have elaborated more on the idea of the data base as the central repository of components. The black boxes have been "opened up" and the emphasis is now more on finding a common representation for their internal structure. Integration is obtained by the sharing of this common description among different tools and by developing an elaborated attribute schema to contain additional information about the components. Finally they introduce the concept of knowledge. There is a growing awareness of the fact that the data base is a repository of knowledge, which can be exploited in an intelligent way to automatically perform certain tasks such as extraction of dependency relations between components. Future environments could see this development carried on to pure knowledge bases with associated planners to relieve the programmer from tedious tasks. We should also see the arrival of sophisticated query systems so the programmer can be integrated as more than just a source of information. With the arrival and wide diffusion of powerful workstations, concepts like communication and distribution will become increasingly important in order to coordinate the work of the individuals of a project group. Finally we should see a more conscious notion of project management being integrated in the software development environment. For a more elaborated presentation and discussion of the evolution of especially configuration management and version control in software development environments see [2]. In the following two chapters we present our conceptual framework. At the top level we want to make a division between tasks and activities related to Programming-in-the-Large and tasks and activities related to Programming-in-the-Many. Many other distinctions could have been made such as between the types of environment (language-centred, structure-oriented, tool-kit or method-based) as have been done in [11]. However, we find it much more fruitful to emphasize the distinction between properties related to the manyfold of components and versions (PitL), and properties related to the manyfold of persons and storage locations (PitM). The former has to do with the management and control of systems and are mainly problems related to single programmers. The latter has to do with the organization and management of people and res-sources of a project. Of course this distinction cannot be clear-cut as the different tasks that have to be performed to some degree are interrelated (like a configuration of a system including modules produced by others and located on different servers). However, the advantage of our approach is that the focus is put on the more abstract level of distinguishing the different tasks and activities that have to be supported by a complete software development environment for it to constitute the ideal environment for supporting the development of software. In the construction of the framework we thus take the programmer's perspective - not his perception of the environment he uses, but rather his perception of the tasks and activities he has to perform to develop and maintain a large software system (build systems, save versions (PitL) - communicate, adhere to methods, cooperate (PitM)). 3 Programming-in-the-Large The original definition of PitL as given by DeRe-mer and Kron [12] is that it has to do with: - structuring a large collection of modules to form a system - describing module interconnectivity - enforcing module disconnectivity Based on this definition they give the proposal for a separate Module Interconnection Language to solve these problems. Much work har been done to get a better understanding of the proper mechanisms for Module Interconnection Languages. For a survey of this research see [20]. Results from this research have migrated into programming languages proper, most notably Ada [1] and Modula-2 [28], to the extent that modern programming languages have little or no need for a Module Interconnection Language on top of them. Both for this reason and because it gives more flexibility in the configuration management task [7] the latter two of the above problems can today be considered as belonging to the world of PitS. This leaves primarily the problem of structuring the modules to form consistent systems, which is basically what Configuration Management is about. Another problem which we consider to belong to PitL, but which is not treated in the early paper by DeRemer and Kron, is that of versioning. Especially for todays systems which have to be maintained and further developed for long periods of time and possibly for different hardware and operating systems, there develops a manifold of versions of each module. These versions are highly related to each other and yet they may exhibit quite different characteristics. The safe and easy administration of these versions is what is handled by Version Control. 3.1 Configuration Management During the development and maintenance of a large and complex software system, it is often necessary to (re)compose it in different ways. Both because its components evolve and because there may be the need of configuring the system differently for different hardware or different operating systems or different clients. Configuration management is about the composition of systems from the multiplicity of possible modules and the two main objectives are to save time and to add structure. Saving time concerns minimizing the cost of (re)composing a system, as weU in terms of CPU time as in terms of human and elapsed time. Adding structure serves to introduce additional constraints and abstractions, thereby making system composition more flexible and controllable. In the process of creating a software system three different steps can be distinguished: description of its structure, selection of the involved components, and instantiation of the description using the selected components. The description can be considered a generic template which gives the overall structure of the system without stating explicitly the contents of this structure. The next step is to transform this generic structure to a specific one by resolving -whenever necessary - which component to use for each "slot" of the structure. Finally, because we deal with software systems, we have to apply the usual compile-link-load cycle to the specific structure to obtain an executable system. 3.1.1 Description of systems The first thing we have to talk about for configuration management is how to describe the structure of the systems we want to generate. A description of a configuration is the formal representation of the programmer's knowledge about how to compose a system. It may serve many purposes such as consistency checking, type checking, information hiding etc. However, here we will just consider the configuration management aspect where it is used to make information available for the configuration management system such that the task of generating systems can be automated. There is a wide range of different ways to describe systems spanning from verbose scriptlike ways to almost automatic systems. The extreme would be a system where the command "build editor" would be enough to generate the editor. However, this requires that the configuration management system is in possession of perfect knowledge - a situation which we stiU have to arrive at. Early systems like Make [14] are characterized by rather verbose centralized descriptions. These descriptions contains both structural information about the dependencies between modules and operational information about how to compile, link and load the modules together. Some systems support ways of stating default derivations (like how to derive a C object code module from its source code) to make descriptions less verbose in the operational part. The advantages of these systems are that automating the system generation makes it possible to avoid errors and omissions, and that the system detects when updates are superfluous. The systems are very general in the way they work and their usage is in fact not restricted to software configuration. However, the generality has the drawback that there is little or no information available to support e. g. consistency checking of configurations. By far the most serious drawback, though, is that the dependency relations between the modules are considered a global property [7]. This implies a rather static and inflexible view of configurations, which are not in line with many of the actually used development methods such as prototyping. As stated above, the introduction of module interconnection languages had more that just configuration management purposes. Being primarily a means for providing the interface part known from modern modular programming languages, they usually contain only structural information and no operational information. However, as they are normally used in monolingual environments, the knowledge can be hard-coded into special configuration management tools. Unfortunately the usage primarily in a monolingual setting obscures one of the important objectives of a module interconnection language, namely that of permitting the safe composition of a system from multilingual components. In a configuration management perspective the big step forward is that of considering the dependency relations between components a local property. Moving away from the centralized description, they give locally for every (version of a) module an external description of important aspects of its contents. This opens up for a more dynamic and flexible view of a configuration where the relevant information is placed at the source of its origin and therefore is more easily maintainable. In some recent systems (Adele [6] and D S EE [17]), the construction of the configuration de- scription has been completely automated as regards the structural part. This has been possible because they support languages in which there are primitives for describing dependency relationship (like statements), which can be automatically extracted and used by the configuration management system. In fact Adele requires that supported languages have a notion of interface- and implementation-part. This has the consequence that the programmer has only to worry about dependencies in the context of programming the single module. Furthermore, the systems contains knowledge about how to use standard conventions (like extensions to filenames) to deduct the proper description of object-modules and executable systems. We are thus close to the ideal situation where the structural information is automatically extracted from inside the modules, and the operational information is present as a combination of a knowledgeable tool and a more formal typing notion of the modules. So in summary for description of configurations, we have to consider if: - it is done manually or automatically - it has a global or a local view - it contains only system structure or also build instructions - it is explicitly (such as text) or implicitly (such as graphics) represented 3.1.2 Selection of components Given the structuràl description of a configuration, the next step is to "populate" it with components. Except for very simple systems, the description has to be considered a template for which we have to find the proper components to "inhabit" every slot. The reason for the existence of many potential candidates for every slot is ver-sioning in a broad sense. Versioning because of bug-fixes, because of further development of a component, because of adaptations for different hardware or clients, because of different implementations of time/space trade-offs, etc. There are conceptually seen basically two different kinds of versioning/selection for which we need appropriate ways of resolving which components to choose. The first is versioning because of continuous development of a component. For this kind of versioning we would like to be able to make selections based on some sort of state (such as experimeii-tal, tested, released) or based on temporal properties. These selections can be done either dynamically ("latest tested version") or statically ("version 3.1"). Care has to be exercised when using dynamic selection as a later selection using the same criteria will not necessarily yield the same result. Also care has to be taken to distinguish dynamic selection from static selection. For instance is a statement like "latest released version" dynamic in nature, as a tested version may transform into a released version, whereas a statement like "before todays date" is static. The second kind of versioning arises from the existence of variants and the reuse of the same component in differing contexts. Here the need is not so much of selection on state or temporal properties as that of selection on (user-defined) functional properties and the existence of choice propagation. If we are building a customized system for Acme Inc., we want to be able to state this as a selection rule. Furthermore we want (at least some of) the selection rules to be propagated into the further selection of components on which the present selection depends. The general problems encountered in selection is those of how the set-up is and how the selection mechanism works. We need to consider whether the set of attributes available is pre-defined or if it is possible to have user-defined attributes, too. Furthermore, if the set of values of the pre-defined attributes is extendible or not. Most systems introduce some sort of parallel to the scope-rules of programming languages. They have a hierarchy of importance where a component in the users workspace can have precedence over the project version of that component. Other systems use a schema of standard/default indications for the same purpose. This leads to another point of great importance, namely that of ambiguous or empty selection sets. From the existing configuration management systems there seems to be no clear line in how this problem is solved. In the presence of an empty selection it is obvious to signal an error, but when does a selection become empty. Will for instance a selection-rule stating "hardware=SUN" become empty if no components have the attribute "hardware" and it is set to "SUN". Or will the absence of the attribute be interpreted as the independence of hardware, so the component wiU be selectable? The same kind of problems arise when the selection-rules are not exhaustive, thus leaving two or more components to choose from with no explicit selection-rule to do this choice. Also here there is a wide variety of solutions. Some use a schema of choosing the newest component possible. Others rely on standard/default indications of preference or some other preset strategy of scope-rules. And yet others use a selection schema introducing a hierarchy in the strength of the selections ranging over imperative, exclusive, conditional, and default selections. In summary when considering the selection of components to populate the given description, we have to pay attention to: - if choices are static or dynamic - if there is propagation of selection-rules - if the attribute schema is extendible - the existence of scope-rules - the resolution of empty/ambiguous selection sets 3.1.3 Instantiation of configurations The third step in generating a software system is that of instantiating the configuration. In the two steps we have described the system and chosen the components respectively. Now we have to assemble the specified system and dealing with software this is done by compiling the modules and linking and loading them together into an executable system. The degree to which the programmer is aware of the presence of the object-code varies much. In systems like DSEE, everything is specified in terms of source-code modules and the binaries are considered internal results of system application of tools to source-code. Other systems like Make have the programmer worry about specifying each and every detail in transforming the source-code modules into an executable load-image. The question of when the instantiation of a new configuration is executed and has effect is another key point. Most systems implement a schema of lazy effectuation - a schema where systems are only generated by explicit request. This has the advantage that the programmer has full control over when new systems are generated and can be aware of the effects of a dynamic selection. However, it also means rather long idle-times for the programmer if a lot of work has to be done to (re)build the system. For this reason some systems implement a busy effectuation schema trying to anticipate the requests. This gives very fast response times (sometimes even zero) for the instantiation of configurations. The drawback, however, is that a lot of work (CPUtime) can be consumed on instantiating configurations that are never requested. If an entire configuration had to be (re)instan-tiated every time even a smaU change was made to some module, it would lead to disastrous performance problems. All systems implement some op-timalization mechanisms to handle this problem. The best known technique is to compute the least update necessary to keep the configuration consistent. This causes a compilation only of modules for which no binary exist, and a recompilation only of modules that have been changed (or that have had effective changes) and modules that depend on these. Another approach is to keep pools of binaries to avoid compilation because of missing binaries. For large and fast evolving systems this can lead to serious space problems, which can, however, be solved (partially) by using paging-like algorithms for discarding binaries unlikely to be used. Finally the arrival of workstations supporting multiple processes and connected in networks have lead to new ways of obtaining performance gains. In these systems the work of instantiating configurations can be performed as background jobs making use of the computers idle-time or of excess CPU-time on other computers in a network. Summarizing the key points to pay attention to for the instantiation of configurations, we have the following: - orientation (source- or object-code) - effectuation (lazy or busy) - optlmalizations (least update, pools, distributed or background processing) 3.2 Version Control During its development and maintenance a component will change slightly. For many reasons it is convenient to keep, or to be able to regenerate a component also in its intermediate forms and not only in its present one. In other cases there may be distinct but related components which we want to consider as variants of each other and belonging to the same "family". Version Control aims at managing the history of development of a component and the two main objectives are to save space and to add structure. Saving space is mostly a technical matter, in which all the versions are compressed in as little space as possible. More important, however, is it that version control makes it easier and more convenient to understand and record the evolution of a component and the interrelations between the manifold of versions. When trying to manage and maintain a collection of versions and variants of components, there are three important notions: the underlying model for the evolution, the employed attribute schema for the components, and finally how to merge components. The underlying model is an important instrument to serve as a conceptual framework for structuring and restricting the way components can evolve. The attributes associated with the components are useful in the context of version control for distinguishing the different versions, but also in a larger context where they serve as an external description of some internal (private) properties of the components. In the context of parallel development (variants), merging is an often performed task to incorporate corrections/changes to one variant into other variants. 3.2.1 Model One of the most important instruments when trying to manage the manifold of versions is to have a good model. The existence of such a model makes it possible to create abstractions to suppress irrelevant details and to support a superimposed structure. The primary way of supporting abstractions is to consider the set of related versions and variants as one entity. Usually such an entity is called a family, and the members share some important characteristics (such as functionality) while others (such as implementations) may be different. Ideally the members of a family should be interchangeable and only when special characteristics are needed (like performance, special hardware, bugfixes) it will be necessary to "open up" the family and choose a specific member. Inside a family it is necessary to put a structure on the way its members can evolve from each other. Such a structure is a help to guide the evolution in a sound direction and to enforce restrictions to avoid unwanted or unsafe development. Furthermore the structure helps in providing a conceptual framework to make evident the history of previous development. As such the model serves to understand previous development and to guide future development. The most widely used structure is that of a tree. Development is basically considered to be linear, but in some points it can branch into a parallel development. The exact nature of the tree (one/more branches, branches on branches, etc.) differ from system to system, although there seems to be a general agreement on allowing only one level of branching. There is, however, one big problem with the tree-model, and that is the treatment of variants. Variants have a nature slightly different from that of versions. Variants are developed in parallel lines which for some aspects (like supported hardware) are independent from each other, but for other aspects (like inclusion of common bug-fixes) they are interrelated. This indicates the need of being able to state relations between different branches of development. This model can be realized by a graph. However, a general graph is inconvenient from the point of view of controlling the evolution, as it is too permissive. Thus restrictions (such as acyclic) are usually put on the nature of the graph. The graph also supports the situation where diverging lines of evolution have to be merged into one common (see section 3.2.3), which is not a very unusual situation in software development. In some cases the distinction between variants and revisions can be important for the organization of the whole project. In such circumstances we should look for mechanisms to support a model where there is orthogonality between variants and revisions not just on the level of individual com- ponents but on a project-wide basis. There are different approaches to this [21] [8], but they have all in common that their organization emphasizes the entire project over its individual components. Consequently, the terms variant and revision in this case span the whole project and are orthogonal to each other. In summary we have to look out for the following characteristics of the model for Version Control: - the support for abstraction - the support for structure (tree, graph, orthogonality, restrictions) - how variants are treated 3.2.2 Attribute schema For version control and other purposes an attribute schema is a necessity. For structural ends it serves to unveil the abstractions made in the model and to give an extra layer of relations between components not present in the model. Informative ends see the attributes employed in providing a way to state important history and descriptive information connected with each component. The model for version control helps in managing the manifold of versions by providing abstractions to compact the abundance of information into a manageable number of uniform units. The attributes help us to go the other way. To uncover the diversity of the components in a unit and to help in "naming" or selecting amongst them. They thus work to support and make manifest the model (such as by version numbering), but they also add to the structural model. In the absence of relations, the attributes can be used to supply an extra structure to say how the components in a unit interrelate and possibly relate to other units. An important aim of version control is to keep information other than the structure to help understand the historical development of the components. Again the attributes are able to store the needed information in a compact and concise way, so it can be used both for querying and for selecting purposes. In general, attributes are convenient for giving short, uniform information about heterogeneous components. It is a way to give a uniform external description of properties (like used language) of the component that might not even be deducible from the contents of the component (like state). Summarizing the treatment of attributes, the important points are: - support for structural purposes - support for informative purposes 3.2.3 Merging of components The merging of different versions or variants is a very important and very often performed task in the development and maintenance of software systems. Conceptually all the components of one family foUow one single line of development. There may be divergences for some periods of time, but the general flow of development is common. For versions branching off into parallel development, it is usually a temporary solution and one may soon want to integrate the changes into the main line of development. Variants are more long-lived, but in general there wiU be the need of applying the changes made to one line of development (like bug-fixes) also to some or aH of the other lines. The support for merging is not present in aU systems. Some systems consider it to be outside of the scope of the environment and to be solvable by means of other tools. For other systems (mainly non-text based) the problem is that the merging of two abstract syntax trees is not a well understood and easily solved problem. For this reason they have concentrated their efforts on other topics and leave the programmer with no support - if not to extract text-copies and to re-enter the merged copy into the environment. Many (text-based) systems, however, provide an integrated mechanism for merging. The ad^ vantage of doing the merge inside the environment is that it is possible to automatically record the fact that a component is the result of a merge of two other components. If it is done outside the control of the environment, the programmer has to supply the necessary information if there is any support at aU even for recording this type of information. The point to consider for merging of components is if it is an internally supported operation, or if it has to be performed outside of the control and support of the environment. 4 Programming-in-the-Many In this chapter we wiU look at the problems caused by the big organization around software development. Programming-in-the-Many is aimed at how to manage many people having different tasks, working on different computers, using different tools to produce slightly different products. As projects get bigger and live longer, it becomes increasingly more difficult to contain these many people and the many physical resources within the context of one single project. We subdivide this topic into how to manage the many persons involved and how to organize the many resources at disposal. Personnel Management is about how to syste-mize and formalize the interrelations between the many different persons attached to a project. To compute their tasks successfully they have to collaborate, coordinate and communicate. Often they have to adhere to some kind of formal development method and there may be pre-established patterns of communication such as for the handling of bug-reports. Furthermore, we need to protect the various parts of the project from unauthorized access. The growth in easily accessible resources has made it more and more common that each programmer has his own personal workstation. Furthermore, big and long-lived systems are often implemented on several different target computers. How to create order out of this chaos of often non-homogeneous and distributed resources is what Resource Management is dealing with. We need to give a uniform view of the resources and we need to make the distribution of them transparent. 4.1 Personnel Management As the size of software development projects grow, it becomes necessary to involve more people and to specialize them. On big projects there can be assigned several hundred persons, and during the life-time of the project (includiirg maintenance) even more people may contribute to the project in a shorter or longer period of time. With todays big multi-national companies it is not unusual to see a project also being distributed in place even to different continents. This causes severe problems in coordinating these people in a disciplined way. The problems can be approached in two ways: a formalized method of development to assure the documented collaboration and communication; and the implementation of security measures to protect against access violations. In short, we want to organize the interpersonal relations in a formalized framework, where they can be documented and controlled in order to be able to successfully manage software development projects. 4.1.1 Method Organizing big projects is a difficult and complex task. We have to assure that all parts of the project is being taken care of, and that no part of it is unintentionally being worked on by several persons. For this reason we need methods to break down the project into smaller pieces and ways to assign these pieces to certain persons or group of persons (who again might break it down into even smaller pieces). In the context of software development several formal methods have been defined. They range from rather rigid and simplistic ones like the waterfall model [23] to more anarchistic and fuzzy ones like rapid prototyping [15]. Some methods are aimed at a specific programming paradigm and can best be used under this restriction [10], while others are more generally applicable no matter which programming paradigm is used [9]. However, they all share the distinction between several different phases of the development like: requirements, specification, coding, testing and so on. The main difference between the methods is their approach to the execution of these phases. In for instance the waterfall model they have to be executed in a strictly sequential order one after the other. Others consider it to be a cycle that has to be iterated - maybe indefinitely - and where the phases may be carried out in parallel. In yet others the phases interact in arbitrary ways to lead towards the common goal - the right system. ' One thing on which aU the methods agree is the importance of communication between the different phases - or the exchange of information. And that this communication has to be documented and persistent. Documentation is usually obtained by using standard formulas in exchanging information such as specification schemas and bug reports. This has the advantage of keeping a high degree of written information exchange. Written information is easily made persistent and the (semi-)formal way in which it is stated makes it easy to construct query-systems to facilitate the fast retrieval of any wanted piece of information. A high degree of written and persistent information gives a good possibility of controlling the project. One point on which the methods differ is the extent to which they incorporate maintenance as an integral part of their model for the development. Some methods do not consider maintenance at aU. and we have to fake it considering a sequence of projects where the requirements for the new project is that for the old one plus bug corrections plus enhancements/changes. Other methods have maintenance as an integrated part of the model; some methods have it as a transition to a special maintenance phase, while others has it as a normal phase of the continuous development of a system. The maintenance phase has become increasingly important as it can consume a major part of the resources of todays software development projects [24]. All the methods are useful for controlling software development. However, as the computer is also the main tool for all the people working on the project, then we get the maximum benefit when the method is also supported by the computer. The ideal would be that all information exchange was done by means of the computer media itself. In this way all the information about the project would be on-line and easily combinable in different ways in different contexts. Furthermore, because of its storage capacity and computing power, the computer is also the perfect tool to impose the methods and to control that they are being followed. To sum up, we must look for: - support for different methods (work breakdown) - support for communication/documentation - support for maintenance 4.1.2 Security People working together on big projects need to collaborate and while collaborating also to share things among them, such as the modules of the system. However, not all information and all things should be shared between everybody - and not in the same way. For example, while a programmer works on a new version of a module, he wants that version to be private to himself so nobody else can use it by accident or make changes to it without his knowledge. When he has finished the version, he might make it accessible for the people responsible for the testing in a read/execute mode. When these in turn have finished the testing, they make it accessible to all the other programmers in execute mode - other people like the release people wiU not have access to the components of the system, but only to the compound system itself. When talking about access problems we have to consider that there are two types of illegal accesses. There are illegal accesses done with an ill-will intention and illegal accesses done by accident such as by accessing a wrong version. Within the project most illegal accesses wiU be of the second type, while the first type will be most common for people from outside the project - but maybe still within the same company. However, in some very special cases - e. g. when a programmer is away for a longer period - it can be necessary to circumvent the security system to avoid waiting for the accessibility of some important information. The most common ways to fight illegal accesses are either to put access rights on all single files or to partition the project information and assign rights to each. When we talk about putting access rights on each single file, this can be done in many different ways. Usually there exists a way to group other users into precisely defined groups for which we can grant different rights. This can be done as in UNIX-based systems where the division is between user, group and others, or it can be done as in other systems where it is possible to specify for each file a list of users which are allowed to access it. The kind of access granted can vary from a pure execute permission to an all-out write permission. The other way to grant permissions is to partition all the projects files into more or less related partitions and for each one assign access permissions to different groups of people. Probably a mixture of the two approaches wiU be the most efficient way of implementing security schemes, even if it may imply compatibility problems b'etween permissions granted under each single scheme. Rounding up, we can say that security measures fall into two groups: — security against illegal access. - possibilities of partitioning the project. 4.2 Resource Management The introduction of the personal computer - and thereby the easy access to computing resources -has had an immense impact on the way in which software development is conducted. Now people are not any more connected to a central mainframe via terminals, but are using workstations interconnected in local networks. Furthermore, the developed systems tend to get bigger and more costly. To amortize the high costs, such systems tend to have longer lifetime and be im-plementated (and maintained) on many different computers. For these reasons we see a growing trend towards a distribution of the development (and especially the maintenance) efforts in space and time. The distribution in space is a result of splitting up the project on many computers. This division has many advantages in the form of increased computing power, storage capacity, flexibility and so on. However, it also poses us the task of making the distribution transparent. Otherwise the drawbacks in form of overhead in the manual management of the partitioning will outweigh the advantages. We can consider the problems about maintaining (and developing) many variants of the same system as a question of distribution in time. We have to manage many systems created at different points in time and maybe having slightly different characteristics. This creates problems of many different kinds. We have to be able to regenerate old systems to handle bug correction. We have handle updating the common part of different variants. We need to know exactly what was shipped with each and every release (version of software, manuals and documentation). We must keep track of which clients have what system. And the list can be continued. 4.2.1 Workspaces Tke workspace is a way to solve the problem about the spatial distribution of a project. When the information (program, documentation, test) is divided on several computers, there exist the task of assisting the programmer in obtaining/maintaining easy access to it. The ideal would be to make the distribution transparent so that he does not have to care about e. g. network protocols. And to give him a uniform view of the project such that he does not have to fight idiosyncrasies of different operating systems, environments, or - more generally - applications. The requirement to the programmers environment should be that he in his normal work does not have to deal with the problems caused by distribution. It should be possible for him to make scripts (or to get ready-made ones) handling the differences in interacting with different systems. And he should be able to define a profile telling the physical position of the files he is using but which is not residing on his own file server. Furthermore, we must have some mechanisms to handle the dangers of sharing the same files. The updating of a module without the knowledge of the programmer who is responsible for it can cause very unpleasant surprises. Mechanisms that can notify us in case the module we are working on also being updated by someone else. This could be to teU us about the existence of a never version than the one we used to work on. Or that somebody is trying to update the version we are currently working on. Or that somebody is already working on the version we want to work on, such that there might be a potential conflicting update in the future. 4.2.2 Time-machines In the science fiction literature time-machines are used to take the reader on a'travel in time. Either to go back in time to see exactly how some historic event happened, or into the future to give him a glimpse of how some actions can effect the future. This is much the same functionality we want to obtain from the time- machines when they are applied to software development, we want to be able to go back in time and locate the components of a specific system and regenerate an exact copy of it. Likewise we would like to make some changes, see how they influence on the systems (future) behaviour and go back and undo some actions creating undesired effects. Maintenance of old variants is the main reason for having to go back in time. When a client calls us about a bug, we must be able to generate an exact copy of his system to be able to understand the nature of its erroneous behaviour. And when we have corrected the bug - or in other ways want to update the system - we need to know how the system is affected. It is especially important that the time-machine takes into consideration more than just the modules of the system. Albeit the most important part, we also need to be able to find the corresponding specifications, tests, documentation and so on, so also these can be consulted and updated in a correct way. The further development of a system can also benefit from the time-machines ability to go forth and back in time. When we have to make changes to a system, we can make experiments to see the effects, and if some of the effects are undesired we have the possibility to go back in time and undo them (much the same as in an editor). This can be used when we have to make a common change to different variants when we cannot do it in the common part (or to discover that it has side-effects for some variants). The facility can also be used to make exploratory programming where we by successive trail-and-error arrive at the desired result. However, the most important property of the time-machine is that it makes our experiments documented. And that it lets us work in precisely defined and consistent contexts. 5 Discussion When presenting a conceptual framework for software development environments, many differeiit approaches can be taken. One such is the one of [11] where they group a collection of systems into different categories having different characteristics and properties. This approach has in our opinion the serious drawback of only focusing on the technical topics which are captured by existing (or by their collection of) systems. As a classification of existing systems it does well. The problem is that such an approach only allows us to construct a framework which spans the known and already implemented. When we want to make a proper framework for the field of software development as such, we find that it is crucial for its generality and completeness to start from a dissection of which tasks have to be performed in this field. Such a study could take its starting point in [19], which is a presentation of the different maturity levels in the organization of the software development process. In this way we can capture also properties which are as yet poorly or not at all supported. That is why we focus on the functionality that has to be offered in the area of software development rather than giving a technical presentation of existing systems. There may be raised objections to our classification of topics, saying that we have left out things like Pits, integration, and user interface. It is true that these are important topics and that we do not treat them independently. Such topics must also be a part of a complete evaluation of a software development environment. Our focus in this paper, however, is only on the tasks which have to be carried out and which should therefore be properly supported. We think that PitS belongs at the level of individual tools, which we do not consider in this paper. Integration is a "behind-the-screen" implementation issue, which is of no concern to the user - except when it "shows up on the surface". User interface is too diffuse a topic to be treated in its own right as it affects most of the other topics - especially workspaces - and are treated there. These are all important topics, but they should be treated separately in another setting as they are outside the scope of this paper. A more serious objection is that there is no separate treatment of what is the conception of the basic unit. That there is not elaborated on what is the view of the component (internal/external description, common representation etc.). Again our point of view is that this is not the proper place for any detailed treatment ofthat topic. It is something which belongs mainly to the programming language field. It has obvious relations to some of the tasks in software development and is duely treated under these tasks. We want, however, to keep our framework language-independent and thus in the context of software development environments the treatment given in chapter 2 suffices from the point of view of the user. Our framework is very suitable for evalua- ting and comparing software development environments. It distinguishes a number of important, orthogonal topics and for each topic it lists a number of parameters which have to be considered. This provides a good foundation for evaluating how suitable a specific software development environment is for a given organization. In the presented framework, aU the topics are stated on an equal footing. In order to use the framework in an actual evaluation the relative importance of each topic has to be adjusted to the requirements of the given organization. In such a customization some of the listed topics may be left out because they are not relevant in the given context. The use of our framework ensures, however, that we start with a complete list of relevant topics. The most important innovation of this conceptual framework is the attempt to establish PitM as a dual to PitL and equally as important. Much more than just a question of management, PitM also has to deal with things like communication, cooperation, and homogeneous views of resources. As pointed out by Bazelmans [4] the lack of a well defined method for project use can be a hindrance for the widespread and coordinated use of many useful tools. This framework will hopefully help to avoid this. It is always difficult to guarantee the completeness of a framework of this nature. It wiU inadvertently be limited by the depth of our insight into and understanding of the field in question. The part of our framework which covers PitL builds on other fields with a long and rich background in research. This provides us with a solid foundation and makes it possible to refer to actual implementations of the discussed concepts. The other part which covers PitM is potentially more problematic because there is not much prior experience to base upon. We draw on work from many different fields like capability maturity models, software process modelling, and computer supported cooperative work. The relevant parts from these fields are brought together under the term of PitM and then categorized in a systematic way such that it is suitable as a framework. The field is still young, so this part of our framework should not be considered to constitute the final word. It is, however, complete with respect to the present level of knowledge. 6 Conclusions In this paper we have presented a conceptual framework to use for the study of software development environments. The field is divided into two main topics, Programming-in-the-Large and Programming-in-the-Many, which are again divided up into subtopics, Configuration Management, Version Control and Personnel Management, Resource Management respectively. Each topic is analyzed in details both to give a better understanding of the tasks which have to be performed within each subtopic, and to present some of the alternative ways to solve them. The innovative in our approach with respect to other surveys of the field, is that we apply the perspective of the user of the environment and the tasks he has to perform to solve his assignment. Other taxonomies take the perspective of the environment and are therefore neglective to tasks which are poorly or not at all supported in todays environments. Finally, we show the importance of such a framework. On the theoretical level it can be used as an introduction to the field of software development helping us to focus on important topics and to systemize our insight. On the more practical level it can be used both to evaluate and to construct environments. Acknowledgement: This research was supported, in part, by grant no. 9400911 from the Danish Natural Science Research Council. References [1] ADA Reference Manual, Proposed Standard Document, United States Department of Defense, July 1980. [2] Vincenzo Ambriola, Lars Bendix, and Paolo Ciancarini: The Evolution of Configuration Management and Version Control, Software Engineering Journal, Volume 5, Number 6, November 1990. [3] Lars Bak, Claus N0rgaard, Elmer Sandvad, J0rgen Knudsen, and Ole Madsen: An Overview of the Mj0bier BETA System, in Software Engineering Environments, Volume 3, Ellis Horwood Limited, 1991. [4] Rudy Bazelmans: Evolution of Configuration Management, ACM SIGSOFT Software Engineering Notes, Vol. 10, No. 5, October 1985. [5] N. Belkhatir, and J. Estublier: Experiences with a Data Base of Programs, ACM SIGPLAN Notices, Vol. 22, No. 1, January 1987. [6] N. Belkhatir, J. Estublier, and W. L. Melo: Adele2: A Support to Large Software Development Process, in proceedings of the International Conference on the Software Process, Re-dondo Beach, CA, October 1991. [7] Lars Bendix: Configuration Management and Version Control Revisited, PhD dissertation. Institute for Electronic Systems, Aalborg University, Denmark, October 1995. [8] Brian Berliner: CVS II: Parallelizing Software Development, in proceedings of the USENIX Winter 1990 Conference, Washington D.C. [9] Barry W. Boehm: A Spiral Model of Software Development and Enhancement, IEEE Computer, May 1988. [10] G. Booch: Object-Oriented Design with Applications, Benjamin/Cummings, 1991. [11] Susan A. Dart, Robert J. Ellison, Peter H. Feiler, and A. Nico Habermann: Software Development Environments, IEEE Computer, November 1987. [12] Frank DeRemer, and Hans H. Kron: Programming-in-the-Large versus Programming-in-the-Small, IEEE TSE, Vol. SE-2, No. 2, June 1976. [13] T. A. Dolotta, R. C. Haight, and J. R. Mashey: The UNIX Time-Sharing System: The Programmer's Workbench, The BeU System Journal, 57 (6), July-August 1978. [14] S. I. Feldman: Make - A Program for Maintaining Computer Programs, Software - Practice and Experience, Vol. 9, 1979, p. 255-265. [15] Christiane Floyd: A Systematic Look at Prototyping, in Budde Kuhlenkamp, Lars Mathias-sen, and Heinz ZUighoven, editors. Approaches to Prototyping, Springer Verlag, 1984. [16] A. Nico Habermann, and David Notkin: Gandalf: Software Development Environments, IEEE TSE, Vol. SE-12, No. 12, December 1986. [17] David Lubkin: Heterogeneous Configuration Management with DSEE, in proceedings of the 3rd International Workshop on Software Configuration Management, Trondheim, Norway,. June 1991. [27] Walter F. Tichy: Tools for Software Configu-. ration Management, in proceedings of the ACM Workshop on Software Version and Configuration Control, Grassau, Germany, January 1988. [28] N. Wirth: Programming in Modura-2, 3rd edition, Springer Verlag, 1985. [18] N. Minsky, and A. Borgida: The DARWIN S oft ware-Evolution Environment, ACM SI-GPLAN Notices, Vol. 19, No. 5, May 1984. [19] Mark C. Paulk, Bill Curtis, Mary Beth Chris-sis, and Charles V. Weber: Capability Maturity Model for Software, Version 1.1, Technical Report CMU/SEI-93-TR-24, Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA, February 1993. [20] Ruben Prieto-Diaz, and James M. Neighbors: Module Interconnection Languages, The Journal of Systems and Software, No. 6, 1986. [21] Christoph Reichenberger: Voodoo: A Tool for Orthogonal Version Management, in proceedings of the Fourth International Workshop on Software Configuration Management, Baltimore, MA, May 1993. [22] Dennis M. Ritchie, and Ken Thompson: The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974. [23] Winston W. Royce: Managing the Development of Large Software Systems, IEEE WE-SCON, August 1970. [24] Ian SommerviUe: Software Eiigineering, 4th edition, Addison-Wesley Publishing Company, 1992. [25] D. C. Swinehart, P. T. Zellweger, R. J. Beach, and R. B. Hagmann: A Structural View of the Cedar Programming Environment, ACM TOPLAS, VoL8, No. 4, October 1986. [26] Walter F. Tichy: RCS - A System for Version Control, Software - Practice and Experience, Vol. 15(7), July 1985. A Sound and Complete Axiomatization of Functional Dependencies: A Formal System With Onty Two Inference Rules Mirko Maleković University of Zagreb Faculty of Organization and Informatics Pavlinska 2, 42000 Varaždin, Croatia Keywords: completeness, formal systems, functional dependencies, inference rules, soundness Edited by: Rudolf Murn Received: December 12, 1994 Revised: August 9, 1995 Accepted: September 26, 1995 A formal system for functional dependencies is introduced. The formal system contains only two inference rules: (I) Reßexivity and (II) Generalized transitivity. 1 Introduction Various sound and complete formal systems for functional dependencies have been studied in the literature ( [Armstrong 74], [Beeri et al. 77], [Maier 83], [Pichet and Delobel 79], [Saxena and Tri-pathi 89], and [UUman 88], All the formal systems, as mentioned above, have at least three inference rules. In this paper, we present a new formal system for functional dependencies; the system has only two inference rules: reflexivity and generalized transitivity. The paper is organized as foUows. In the next section, we describe a new formal system for functional dependencies with only two inference rules. Correctness of the formal system is also proved. Conclusions are given in Section 3. 2 A Formal System with Two Inference Rules In this section we describe a formal system which contains two inference rules. The system is called -F52-system . F6'2-system for functional dependencies consists of two inference rules: (I) hX^Y if Y CX (reflexivity) (II) X -^Y, YZ ^W h XZ^W (generalized transitivity) In the following proposition we assert that FS2-system is sound and complete. Proposition 1 FS2-system is sound and complete. Proof Because it is very easy to prove that FS2 is sound, we only prove that FS2 is complete. We shall first introduce an entailment relation, denoted >-. Let F S be a formal system for functional dependencies and IR : fi,..,fn be an inference rule for functional dependencies. We shall say that FS entails IR, denoted FS >- IR, if /1,.., fn g, where fi, ■ ■fn^ps S indicates that g is derivable from /1, ...,/„ in FS. In addition, let FSi and FS2 be two formal systems for functional dependencies. We shall say that F Si entails FS2, denoted FS^ y FS2, if. F Si >- IR, for each inference rule IR in FS2. We have the following auxiliary proposition. Proposition 2 (Completeness and Relation y) Let F Si and FS2 be two formal systems for functional dependencies. FSi is complete for functional dependencies if FS2 is complete for functional dependencies and F Si >- FS2. Proof The proof follows immediately from the definitions of completeness and relation It is well-known that Armstrong's formal system, denoted A5, is complete for functional dependencies. AS has the following inference rules: M. Maleković asi : h X y if Y ex (reflexivity) as2 : X ^Y XZ ^YZ (augmentation) (transitivity) Now we shall prove that FS2 >- AS. Because (I) is asi , we have to prove that FS2 >■ as2 and FS^ >- ass First, we prove FS2 >- as2. We would like to show that y h^, xz The proof is as follows: (1) X y hypothesis (2) YZ^YZ (I) (3) XZ^YZ (1), (2), and (II) Now we give the proof of FS2 >- «53 • We would like to show that X y, y We have the following proof: (1) X -^Y hypothesis (2) y Z hypothesis (3) X-.Z (II) Because we have established FS2 >- AS, and as A5 is complete for functional dependencies, we obtain, by Proposition 2 (completeness and relation that FS2 is complete for functional dependencies. References [Armstrong 74] W. W. Armstrong, Dependency structures of database relationships, Information Processing 74, North Holland Pub. Co. Amsterdam (1974), pp. 580-583. [Beeri et al. 77] . Beeri, R. Fagin, and J. H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proc. ACM SIGMUD Int. Conf. Management of Data, Toronto, Canada (1977), pp. 47-61. [Maier 83] D. Maier, The theory of Relational Databases, Computer Science Press, RockviUe, Md., (1988.). [Pichet and Delobel 81] . Pichet and C. Delobel, Designing third normal form relational database schema, RR No. 149, January (1979), Report de Recherche de I'Universite' de Grenoble. [Saxena and Tripathi 89] P.C. Saxena and R.C. Tripathi, Cancellation Law and a Complete Axiomatization of Functional Dependencies in Relational Database, Computers and Artificial Inelligence, 8,4 (1989.), pp. 347-356. [UUman 88] J.D. UUman, Principles of Database and Knowledge Base Systems, Volume I, Computer Science Press, (1988.). 3 Conclusions We introduced a sound and complete formal system FS2 for functional dependencies. FS2-system consists of only two inference rules: (I) reflexivity and (II) generalized transitivity. Completeness of FS2 is proved. An interesting open problem remains to solve: Is there a complete and sound formal system for functional dependencies which contains only one inference rule? Acknowledgements I would like to thank the anonymous referees for their valuable comments and suggestions. CYBERNETICS & HUMAN KNOWING Cybernetics and Human Knowing is a quarterly international multi- and interdisciplinary journal on second order cybernetics and its relation and relevance to other interdisciplinary approaches such as semiotics. The journal is devoted to the new understandings of the self-organizing processes of information in human knowing that have arisen through the cybernetics of cybernetics, or second order cybernetics. This new development within cybernetics is a nondisciplinary approach. Through the concept of self-reference it tries to explore: the meaning of cognition and communication; our understanding of organization and information in human, artificial and natural systems; and our understanding of understanding within the natural and social sciences, humanities, information and library science, and in social practices as design, education, organization, teaching, therapy, art, management and politics. Because of the interdisciplinary character articles are written in such a way that people from other domains can understand them. Articles from practitioners are accepted in a special section. Subscription Information For subscription send a check in ddk or usd, your name and address to Cybernetics & Human Knowing, v/S0ren Brier, The Royal School of Li-brarianship, Aalborg Branch, Langagervej 4, DK-9220 Aalborg 0st, Denmark; or pay on Giro account no. 2 84 29 04 to Cybernetics & Human KNowing, Denmark or by Diners Club Card. The amounts are: 320 ddk (individual) and 640 ddk (institutional) for Europe and 360 ddk or 60 usd (individual) and 720 ddk or 120 usd (institutional) for the rest of the world. Editor and Editorial Board S0ren Brier is editor and publisher; e-mail: dbibsb@unidhp.uni-c.dk. The editorial board members are: Edith Ackermann (usa), Peter B0gh Anderson (Denmark), Jeanne Bamberger (usa), M.C. Bateson (usa), Stafford Beer (Canada), Stein Braten (Norway), Heinz von Fo-erster (usa), Ernst von Glasersfeld (usa), Louis Kauffmann (usa), Bradford Keeney (usa), Klaus KrippendorfF (usa), George E. Lasker (Canada), Erwin Laszlo (Italy), Niklas Luhmann (Germany), Humberto Maturana (Chile), Edgar Morin (France), Lars Qvortrup (Denmark), Thomas A. Sebeok (usa), Fred Steier (usa), Robert Vallèe, and Francisco J. Varela (France). Information for Authors To facilitate editorial work and to enhance the uniformity of presentation, authors are requested to send three copies of the paper to the Editor, and to prepare the contribution in accordance with the conventions summarized below. Manuscripts will not be returned except for editorial reasons. The language of publication is English, Authors provide printed double-spaced-ma-nuscripts with wide margins. The following information should be provided on the first page: the title, the author's name and full address, a title not exceeding 40 characters including spaces and a summary/abstract in English not exceeding 200 words. Tables, diagrams, reference lists, illustrations and illustration captions should be presented on separate sheets. Reference to a publication should preferably be made of the author, the year of publication and, when necessary, the page numbers (in parentheses). Endnotes should be typed double-spaced on a separate sheet and numbered consecutively. They should be as few and as short as possible and should include no reference material, as this should be given in the reference list. Drawings, graphs, figures and tables must be reproducible originals. They should be presented on separate sheets. Authors will be charged if their illustrations have to be re-drawn. The Editors reserve the right to correct, or to have corrected, non-native English prose, but the authors should not expect this service. The Journal has adopted U.S. English usage as its norm (this does not apply to other native users of English). Authors are advised to use italics for emphasis, quotations, author's names etc. Accepted papers should be delivered on disc in WordPerfect. A Look into Cybernetics & Human Knowing From the Editor of C&HK I received a couple of the journal numbers from which I could choose some new matters for the readers of Informatica. Let me look into Vol. 3 (1995) No. 1 (the marker used for citations wiU be 3 (1995) 1, and so on). —Contents of 3 (1995) 1: This issue is dedicated to cyber-semiotics: the integration of knowledge from second-order cybernetics and the triadic semiotics of C.S. Peirce to a broader framework for understanding information and communication. Papers are: S0ren Brier, Cyber-Semiotics: On Autopoiesis, Code-Duality and Sign Games in Bio-Semiotics; Jesper HofFmeyer, The Swarming Cyberspace of the Body; Lawrence S. Bale, Gregory Bateson, Cybernetics, and the Social/behavioral Sciences. A paper concerning praxis, entitled A (Cybernetic) Musing: Control 1 was contributed by Ranulph GlanviUe. Book Reviews presents Robert Theobald's Turning the Century: Personal and Organizational Strategies for Your Changed World, reviewed by Tetsunori Koizumi; Asghar T. Minai's Aesthetics, Mind, and Nature—A Communication Approach to the Unity of Matter and Consciousness, reviewed by Michaela Ulieru, etc. Citations from Cybernetics & Human Knowing Let us list some most challenging citations from C&HK which characterize the aim of the journal. —[1 (1992) 1, pp. 5-6, Rodney E. Donaldson, Cybernetics & Human Knowing: one possible prolegomenon.] Aspects of Humberto Maturana's brilliant analysis of the difference between transcendental and constitutive ontologies have been intuited by many wise women and men in past millennia and in a variety of cultures—but not by very many, and not with the clarity and scientific sophistication which Maturana's cybernetics offers. Heinz von Foerster, the father of the idea of second order cybernetics, refers to it as "[a] turn form looking at things out there to looking at itself". ... —^once we recognize that perception is an activity and not a passivity—the notions of "communication" and "control", as well as "information", either require redefinition or become quite quietly obsolete. ... We also learn that the past and future are stories we tell ourselves in the present ... —[1 (1992) 1, p. 14, Heinz von Foerster, Etlucs and Second-order Cybernetics.] ... in 1931, Kurt Godei, then 25 years of age, published an article whose significance goes far beyond the circles of logicians and mathematicians. The title of this article I wiU give now in English: On formally undecidable propositions in the Principia Mathematica and related systems. What Godei does in his paper is to demonstrate that logical systems, even like those so carefully constructed by Russel and Whitehead, are not immune against undeci-dables to sneak in. [P. 17] When the language switches to the track of function it is dialogic. There are of course these noises; some of them may soimd like "table", some others like "chair", but there need not be any tables or chairs. These noises are invitations to the other to make some dance steps together. The noises "table" and "chair" bring to resonance those strings in the mind of the other which, when brought to vibration, would produce noises like "table" and "chair": language in its function is connotative. In its appearance, language is descriptive. When you tell your stor^, you teU it as it was: the magnificent ship, the ocean, the big sky, and the flirt you had, that made the whole trip a delight. ... The right question is: With whom are you going to dance your story, so that your partner will float with you over the decks of your ship, wiU smeU the salt of the ocean, wiU let the soul expand over the sky, and there will be a flash of jealously when you come to the point of your flirt. In its function, language is constructive, because nobody knows the source of your story. Nobody knows and ever will know how it was: because as it was is gone for ever. —[1 (1992) 1, p. 22, Ernst von Glasersfeld, Why I Consider Myself a Cyb emetici an.] I had also come across Claude Shannon's theory and in the first two pages of his famous paper on The mathematical theory of communication}-, he mentions that meaning does not travel from a sender to a receiver. The only thing that travels are changes in some form of physical energy, which he called "signals". More important stiU, these changes in energy are signals only to those who have associated them with a codè and are therefore able, as senders, to encode their meanings in them and, as receivers, to decode them. Too often, in discussion on communication, it is overlooked that the initial code of a particulai communication system cannot be established within that system but has to be arranged by other means. The communication system we call "natural language" is no different in that regard. [P. 23] Even monolinguals, when they grow up, sometimes discover that what they thought those other were doing is not what they thought they were doing. So they may become aware of discrepancies between their use of certain words and other people's. But since they have to interact not only with things but also with other speakers of the language, they adapt their meanings as best they can to the meanings they believe others to have in their minds. Quite often this leads to the feeling that one "sees things their way". But, as most of us discover, the need for adaptation never ends. In fact, as you advance to old age, you realize how much you are alone in your conceptual world. On the strength of aU this, I came to beU-eve that the meanings we attribute to words and phrases, and to whole speeches and texts, are meanings, or built up of meanings, that we ourselves have generated in our own experience. They are the result of "self-regulation"—and the study of self-regulation is an integral part of cybernetics. —[1 (1992) 1, pp. 31-32, Ole Thyssen, Ethics as Second Order Morality.] Heinz von Foerster^ has developed the idea of a second order cybernetics. While first order cybernetics deals with observed systems, second order cybernetics deals with observing systems. This involves a shift in perspective. First order cybernetics places an observer outside the observed system, while second order cybernetics places the observer inside a sy- ^Bell Systems Technical Journal, 27, 379-423, 623-656. ^Heinz von Foerster, Observing Systems, Intersystems Publications, Salinas, CA, 1980 (Second edition 1984). stem, which embraces both the observer and the system which he observes and which observes him. Instead of a privileged observer, who monopolizes the rationality of observation, we get a variety of observers, who observe each other without any one having priority. ... Any observation takes place from a point which is invisible for the observer, while he observes. As von Foerster points out, any observation has a blind spot (von Foerster 1984, p. 289). Blindness is a condition of seeing. We are metaphysicians when we make choices which cannot be made and which nevertheless are made. We create philosophical systems on the basis of arbitrary decisions and try, perhaps, to make them socially obligatory. This happens when, e.g., a research elite decides what is good and what is bad research. Persons and institutions get their identity by making metaphysical choices, because such choices show (unfounded and arbitrarily) who they are and how to act. [P. 43] Of course a subsystem is unable to transgress its boundary. It operates internally, and it uses its medium to define its operation. ... —[2 (1993) 2, p. 4, Massimo Negrotti and Lars Qvortrup, Introduction to the Theme: the Theory of the Artificial.] ... artificial devices are built in order to "mimic" something outside the device, be it something in the natural, the psychic or the social world. But what does it mean to "mimic"? ... It is plausible to think that the concept of artificial concretely includes two poles (nature and technology) and generates new realities and not only metaphors. A children's game, a theatrical piece, a painting or 'a symphony are good examples of artificial realities in the sense that they try to reproduce situations, feelings or ideas by means of 'technologies' like social rules, language rules, color rules or acoustic rules. What kind of objects do they set up? Surely they generate artificial realities, but not in the sense of something false: rather they establish new levels of reality (or recombine other levels of reality in a new one) strictly depending, as in any other case of the artificial, on two factors: the 'selections' of the author and the technologicah tools adopted to reproduce them. In this sense, man is much more involved in doing the artificial than in doing something natural and this is, perhaps, his very peculiarity as compared to lower living systems, though not to all of them. Since to reproduce is, coeteris paribus, more easy than to produce ex novo, humans spend a lot of time reproducing the world, both the external and the internal one, thanks to the various technologies invented during the centuries. —[2 (1993) 2, pp. 7, Lars Qvortrup, Orders of Artificiality.] ... if C is an internal element of the system, then the system is a natural (or social) system, which means that it produces its own conditionallty. Thus, the system is an autopoietic system. If, however, C is an external element in relation to the system conditioned by C, then the system is artificial (or at least artificial in condition to C). Such a system does not produce its own condition: it is heteropoietic system. For example, a machine is a heteropoietic system: it may or it may not produce its own elements and relations, but it does not produce its conditionallty. [P. 12] According to Luhman, meaning is at one and the same time produced by the system and externalizing itself in relation to the system. "Communication systems develop a special way to deal with complexity, i.e., introducing a representation of the complexity of the world into the system. I call this representation of complexity 'meaning' ", Luhman writes^ ... [P. 13] Social systems: Communicate through meaning as if meaning is a common denominator. I.e. system A communicates with system B through system A's meaning-conditionality, as if it were also the meaning-conditionality of system B. One person. A, understands other person, B, as if this other person were identical with person A, or, more precisely, if person B shared person A's meaning system. We understand each other egocentrically. —[2 (1993) 2, p. 22, Massimo Negrotti, Towards a Theory of the Artificial.] Artificial is no longer a mere adjective: it is also to be conceived as a substantive. It means that there are artificial objects just as there are natural or technological ones. Artificial is an object which does not wholly overlap either with an object of nature or with an object of technology: it is bound to swing between na- Luhman Essays on Self-Reference, New York, 1990; p. 146. ture and technology. Far from overlapping with all which is simply "non-natural", this concept is closely dependent on the natural object which it aims at reproducing. The artificial constitutes an original reality (a mix of technology and nature), but is always such "with respect to something else", without which it would turn out to be meaningless as artificial and should be defined as pure technological object, as a pure machine. —[2 (1994) 3, p. 3-15, Ervin Laszlo, $-Field Memory: The Missing Factor of Order.] (A comment: for the sake of readability the markers of skipped text parts are omitted.) ... we group the major kinds of systematic realities under the heading of "alternative universes". There are four of them: the mystical /:t-universe, teleological r-universe, random-change universe, self-forming -^-universe. The origins of the /li-universe go back to the dawn of human intellectual history, with roots in both Eastern and Western thought. It was Plato who introduced it into systematic philosophy. Aristotle objected to this postulate and proceeded to outline the historically powerful variant of the r-universe. In Aristotle's conception matter is inert and formless. To account for the world's known properties we must assume action of four distinct "causes", including the final cause which makes the universe basically teleological. The ijii-universe has an especially rich history, first within philosophy and then in science. Its origins can be traced to the atomism of Democri-tus and Leucippus. After a career in philosophy, atomism penetrated into science. Scientific atomism viewed the world as the precise and predictable concourse of atoms (or more basic particles) in space and time. The laws of motion that determine all things in the universe are dynamic, invariant and rmiversal. Probed with more precise instruments, the universe refused to behave like a precise mechanism. The uncertainties that came to light suggest not merely limitations of knowledge but basic indeterminacies at the heart of reality. The breakdown of determinism in the ^-universe was presaged in Boltzmann's statistical mechanics more than a hundred years ago. The probabilistic variant of the -universe remains the main reality for contemporary science to this day. Something is missing from the ^-universe—a factor that would introduce the necessary gui- dance or direction into the random concourse of particles of matter. In the hypothesis put forward on these pages the holographic field that acts as the natural memory of the universe is termed the i/i-field. The hypothesis concerns the existence of a mnemic field that conserves the wave-transform of all configurations of matter that arise in the universe and, in the inverse transform, feeds the conserved pattern back to the corresponding configurations. The basis of the V'-field is the energy potentials believed to be associated with all particles and configuration of particles of matter. The new theory views particles as quantized localizations of the quantum probability field: it postulates that the total wave-field is made up of the energy field frequencies plus Planck's constant. Each particle is described by a probability function in space-time. Living in a ^-universe, reality is not what commonsense and even science thought it was. —[2 (1994) 4, p. 11, Lloyd Fell and David Rüssel, Towards a Biological Explanation of Human Understanding.] ... we do not think that the meaning of the words or the "body language" has been transferred from one person to the other. That kind of explanation has lead to the idea that we live in an "information age" and we come together to exchange information rather than interact. ... Our re-framing of the basic biology means that we do not regard cognition as an information-processing operation, but as a constitutive mechanism of living things. ... From the biology of Maturana and Varela we can say—as Mingers (1991)"^ has done—that language is essentially connotative rather than denotative. ... The fact that we often reach the agreement about the meaning of a word or scientific concept is a testament to our ability to reach agreement, not a proof that such an entity exists in reality. We would say that the meaning of anything lies in the relationship which we make with it. Therefore we are saying that meaning is not transferable-it is formed individually in the course of conversation. —[2 (1994) 4, p. 41, Asghar T. Minai, Information and Aesthetics.] Since the ultimate reality for me is "information" then the usual metaphysical problems arise; from the one how did the existing many derive? Unity has no differentiations. Following Hegel, Nietzsche, Heidegger, Derrida, I emphasize the "difference" principle that is associated with chance, the irrational, the spontaneous and the individual aspects of reality as opposed to the necessary, the rational, the formal, and the universal aspect of things. —[3 (1995) 1, p. 5, S0ren Brier, Cyber-Semiotics: On Autopoiesis, Code-Duality and Sign Games in Bio-Semiotics.] The idea is to make computer manipulate signals which to humans have symbolic value in a logic syntax describable in algorithms in such a way that it becomes meaningful to other language users. But although there is a lot of talk of semantics and symbols in Cognitive Science, the concept of information seems to be like Wiener's (1961)® combination of Shannon's statistical information theory and Boltzmann's probabilistic understanding of thermodynamics (Brier 1992)®. This is again combined with a linguistic theory which claims that the semantic content that symbols of a sentence represent can be determined through truth tables. The basic reality of a sentence is seen as a logical structure with seman-ticaHy empty symbols. The semantical content can then be "poured into the symbols" by their capacity to refer to things, and determined through the truth tables. Reason and the working of language in communication is seen, roughly, as fitting the model of formal logic. The core of meaning, intelligence and reasoning is seen as logical algorithms. From a biological cybernetic and semiotic point of view this theory overlooks various fundamental characteristics of biological systems: self-organization, closeness, complexity, autonomy, self-interest in survival, life history and inten-tionality. The mechanistic idea of reason and knowledge—and of logic, of course—has led to a simplistic understanding of how meaning functions in both language and in practice. The mecha-nicists hope that the causal interaction of symbols can be explained through their syntactic relations. —[3 (1995) 1, p. 16, Jesper Hoffmeyer, The Swar- ^ J. Mingers (1991), The Cognitive Theories of Maturana and Varela, Systems Practice 4 pp. 319-338. Wiener, Cybernetics or Control and Communication in the Animal and the Machine, The M.I.T. Press and John Wiley Sons, New York (Second edition). ®S. Brier, Information and Consciousness: A Critique of the Mechanistic Foundation for the Concept of Information, C&HK 1 (1992) 2/3. ming Cyberspace of the Body.] If the 'observation of observing systems' is the core of second order cybernetics, then certainly biology is a kind of second order cybernetics, for living systems are definitely observing systems. [P. 17] DNA does not contain the key to its own interpretation. In a way the molecule is hermetic. In the prototype case of sexually reproducing organism, only the fertilized egg 'knows' how to interpret it, i.e., to use its text for the construction of the organism. The interpreter of the DNA message is buried in the cytoskeleton of the fertilized egg (and the growing embryo). This in turn is the product of history, i.e., of the billions of molecular habits acquired through the evolution of the eukaryotic cell (Margulis 1981)^ in general and the successive phylogenetic history of the species in particular. (It took evolution two billion years to produce this marvelous entity, the eukaryotic cell. Having accomplished this deed, evolution spent only one and a half billion years producing all the rest.) [P. 22] There is a growing awareness among im-munologists that the separation of the immune system from the rest of the body, and especially from the brain, is illusory. Not only the nerve fibers branching into the organs of the immune system, thymus, lymph glands, bone marrow and spleen, but more importantly, a major conceptual shift in neuroscience has been wrought by the realization that brain function is modulated by numerous chemicals in addition to classical neurotransmitters. Many of these informational substances are neuropeptides. Their number presently exceeds 50 and most, if not aU, alter behavior and mood. We now recognize that their semio-tic specificity resides in receptors rather than the close juxtaposition occurring at classical synapses. —[3 (1995) 1, p. '28-29, Lawrence S. Bale, Gregory Bateson, Cybernetics, and the Social/behavioral Sciences.] System theory emerged out of the need to map and explain biological phenomena that cannot be suitable understood using the classical mechanistic model of reality. "The analytic, mechanistic, one-way causal paradigm of classical science" (BertalanfFy, 1968, p. xxi)®. as Austrian biologist Ludwig von Bertalanffy describes it, assumes that reality can be quantifia-bly analyzed; that a whole can be understood in terms of its parts; and that the nature and function of a substance or an organism can be comprehended by reducing it to its material, externally observable components. ... the successes garnered by the classical scientific paradigm revealed its inadequacies. As refined tools have opened wider panoramas of research, exhibiting data of increasing complexity, science has been driven to search for new ways of conceptualizing reality. In short, the classical paradigm of science has proven inadequate to the task of mapping the natural world. It is particularly inadequate when applied to describing and explaining the multivariable processes of human interaction, e.g., communication, and human-kind's intricate interrelationship with local and global ecological systems. [P. 38] Note how the cybernetic paradigm shifts the focus of our discourse away from: discreet material substances, one-way causality, structure, and summativity. Rather, a cybernetic explanation focuses on: process and behavior, dynamic or animated organization, circular or more complex tlian circular causality, the mutual causal loops of feedback cycles, interaction between multiple variables, and emergent morphogenesis. Hence, the cybernetic stability of a system must be understood not as an inactive structure, but as a pattern of events—an animated organization of exchanges and transformations within the system's parameters. Hence, it is not the characteristics of the "parts" alone that are basic to any whole. Rather, it is the manner in which the system's differentiated components are interrelated that gives them their distinctive properties. Furthermore, within more complex systems the "differentiated parts" exhibit properties which they owe specifically to being components of a larger whole. Is this presentation instructive for the readers and authors of Informatical I hope so, thanking S0ren Brier, the editor, giving me the opportunity to write this report. ^L. Margulis, Symbiosis in Cell Evolution: Life and Its Environment on Earth, Freeman, San Francisco 1981. ®L. von BertalanfFy, General Systems Theory, George Braziller, New York 1968. Report: ISCA '95 Report: EURO-PAR'95 The 22th Annual International Symposium on Computer Architecture was held in Santa Margherita Ligure, Italy, on June 18-24, 1995. Last time this symposium was organized in Europe in 1983. Program Committee, led by James E. Smith, selected 37 out of 180 submitted papers from France, Germany, Japan, Spain, Sweden, Switzerland and USA. Papers were scheduled in the following sessions: Multiprocessors and Applications, Cache Coherence, Interconnect Technology and I/O, Instruction Level Parallelism, New Microarchitectures, Managing Memory Hierarchies, Interconnection Network Routing, Novel Memory Access Mechanisms, Branch Prediction, System Evaluation, Instruction Fetching, Caches, and Processor Architecture. P re-conference tutorials were: - High Performance Microprocessors - Introduction to Parallel Computing - Introducing Parallel Databases for OLTP and Query Processing to Computer Architects - Reliable, Parallel Storage Architecture: RAID and Beyond - Parallelizing Compilers and Beck-end Optimizations - Distributed Shared memory: Concepts and Systems - A Methodology and Tool for Performance Prediction and Evaluation of Complex Computing Platforms - Continuing to Exploit Instruction Level Pa-raUelisrri: Issues, Bottelnecks, and Enabling Conditions In addition, the following workshops were organized: - Undergraduate Computer Architecture Education - Pre-Hardware Performance Analysis Techniques: How Good are We at this? - Fifth Workshop on Scalable Shared-Memory Multiprocessors There were almost 300 participants (from 20 countries) among which also researchers from Computer Systems Dept. of the Jožef Stefan Institute, Ljubljana, Slovenia. The next ISCA will be in Philadelphia, USA. Jurij Šile The EURO-PAR'95 conference was the first in a series of annual EURO-PAR conferences, formed by merging the PARLE and CONPAR-VAPP conference series on parallel processing, with the intent to create the main annual scientific event on parallel processing in Europe. The scope of the series covers the full spectrum of parallel processing, ranging from theory to design and applications. The objective is to provide a forum to promote the development of parallel computing, both as an industrial technique and as an academic discipline, extending the frontier of both the state of the art and the state of the practice. The EURO-PAR'95 conference was organized in Stockholm by the Swedish Institute of Computer Science and the Department of Teleinfor-matics at KTH. The call for papers resulted in 196 submissions; the selection process resulted in 50 regular papers and 11 posters being accepted for presentation on one of the following sessions: Parallel Algorithms, Language Implementation, Compiling Techniques, Semantics and Tools, Loop Parallelization, Architecture Design, Interconnection Networks, Cache Systems, Load Balancing, Scheduling, Fault Tolerance and SIMD Arrays, Applications, and Posters. The presentations included A model for efficient programming of dynamic applications on distributed memory multiprocessors (A.Erzmann et al.), Scheduling master-slave multiprocessor systems (S.Sahni), Using knowledge-based techniques for parallelization on parallelizing compilers (Ch.-T. Yang et al.). Efficient solutions for mapping parallel programs (P.Bouvry et al.), Efficient run-time program allocation on a parallel computer (J.Silc, B.Robic). Three invited talks were given during the conference by Greg Papadopoulos {Mainstream parallelism: Taking sides on the SMP/MPP/Cluster Debate), Björn Enquist {The O z programming model), and Gert Smolka {Parallelism in computational algorithms and the physical world). Conference proceedings are published by Springer-Verlag in the Lecture Notes in Computer Science series, vol. 966. The next EURO-PAR conference will take place in Lyon, France, in August 1996. Borut Robič Announcement of the forthcomming issue of INFORMATICA on the topic: MIND <> COMPUTER i.e. Mind NOT EQUAL Computer In this special issue we want to reevaluate the soundness of current AI research positions (especially the heavily disputed strong-AI paradigm) as well as pursue new directions aimed at achieving true intelligence. This is a brainstorming special issue about core ideas that will shape future AL We are interested in critical papers representing aU positions on the issues. The first part of this special issue wiU be a small number of invited papers, including papers by Wi-nograd, Dreyfus, Michie, McDermott, Agre, Te-cuci etc. Here we are soliciting additional papers on the topic. TOPICS: Papers are invited in aU subareas and on all aspects of the above topic, especially on: - the current state, positions, and advancements achieved in the last 5 years in particular subfields of AI, - the trends, perspectives and foundations of natural and artificial intelligence, - strong AI versus weak AI and the reality of most current "typical" publications in AI, - new directions in AL TIME TABLE AND CONTACTS: Papers in 5 hard copies had to be received by May 15, 1995 at one of the following addresses (please, no email/FAX submissions): North & South America: Marcin Paprzycki paprzycki_m@gusher. pb. utexas. edu Department of Mathematics and Computer Science University of Texas of the Permian Basin Odessa, TX 79762, USA Asia, Australia: Xindong Wu xindongOinsect.sd.monash.edu.au Department of Software Development, Monash University Melbourne, VIC 3145, Australia Europe, Africa: Matjaž Gams matjaz.gamsQijs.si Jozef Stefan Institute, Jamova 39 61000 Slovenia, Europe E-mail information about the special issue is available from the above 3 contact editors. The special issue wiU be published in late 1995. FORMAT AND REVIEWING PROCESS: Papers should not exceed 8,000 words (including figures and tables but excluding references. A full page figure should be counted as 500 words). Ideally 5,000 words are desirable. Each paper have been refereed by at least two anonymous referees outside the author's country and by an appropriate subset of the program committee. When accepted, the authors wiU be asked to transform their manuscripts into the Informatica IWr^X style (available from ftp.arnes.si; directory /magazines/informatica). More information about Informatica and the Special Issue can be accessed through URL: ftp ://ftp.arnes.si/magazines/informatica. TIME-96: Third International Workshop on Temporal Representation and Reasoning Key West, Florida, USA May 19-20, 1996 CALL FOR PAPERS The purpose of this workshop is to bring together active researchers in the area of temporal representation and reasoning in Artificial Intelligence. Through paper presentations and discussions, the participants will exchange, compare, and contrast results in the area. The workshop is planned as a two day event to immediately precede FLAIRS-96 (Ninth Annual Florida Artificial Intelligence Research Symposium, May 2022). Workshop participants are also encouraged to submit papers to FLAIRS and attend the conference. The workshop will be conducted as a combination of paper presentations, a poster session, an invited talk, and panel discussions. The format wiU provide ample time for discussions and exchange of ideas. Submission of high quality papers describing mature results or on-going work are invited for all areas of temporal representation and reasoning, including, but not limited to: temporal logics and ontologies temporal langiiages and architectures continuous versus discrete time point versus interval representations expressive power versus tractability belief and uncertainty in temporal knowledge temporal databases and knowledge bases temporal learning and discovery reasoning about actions and events time and nonmonotonism time and constraints time in problem solving (e.g. diagnosis, qualitative physics,...) multiple agents, communication, and synchronization applications To maximize interaction among participants, the size of the workshop wiU be limited. Accepted papers will be invited for full presentation or a poster presentation. AU submissions must be received by December 5, 1995. Notification of acceptance or rejection wiU be sent to the first author (or designated author) by February 26, 1996. Prospective participants should submit 5 copies of a 6-8 page paper (indicating the selected areas) to: TIME-96 Luca Chittaro and Angelo Montanari Dipartimento di Matematica e Informatica Università' di Udine Via delle Scienze, 206 33100 Udine - ITALY Or preferably, submit by anonymous FTP a postscript version of the paper to: bach. dimi. uniud. it (158.110.1.140) directory: pub/time96 After submitting electronically, please communicate the title, area, and authors of the paper by sending an e-mail to time96@dimi.uniud.it (this address can also be used to obtain further information). The TIME-96 workshop has also a web page at: http://www.seas.smu.edu/ mario/time-workshop/welcome.html 1 Publication All accepted papers wiU be published in the workshop proceedings. As well, a selected subset of the papers wiU be invited for inclusion (subject to refereeing) in a book or in a special issue of a journal. 2 Organization GENERAL Chairs Scott Goodwin and Howard Hamilton, University of Regina, Canada ORGANIZING COMMITTEE Peter Haddawy, University of Wisconsin-Milwaukee Robert Morris, Florida Institute of Technology Andre Trudel, Acadia University Peter van Beek, University of Alberta PROGRAM COMMITTEE Chairs Luca Chittaro and Angelo Montanari, Universita' di Udine, Italy SPONSORING ORGANIZATIONS Sponsorship for TIME-96 is being sought from the American Association for Artificial Intelligence (AAAI), Florida Artificial Intelligence Research Society (FLAIRS), and the University of Udine. PROGRAM COMMITTEE Frank Anger, University of West Florida, USA Fahiem Bacchus, University of Waterloo, Canada Mark Boddy, Honeywell Systems and Research Center, USA Luca Chittaro (co-chair), Università' di Udine, Italy Jan Chomicki, Kansas State University, USA Philippe Dague, Universite Paris-Nord, France Tom Dean, Brown University, USA Mark Denecker, K. University Leuven, Belgium Jennifer Elgot-Drapkin, Arizona State University, USA Marcelo Finger, Imperial College, UK Michael Fisher, Manchester Metropolitan University, UK Dov Gabbay, Imperial CoUege, UK Malik GhaUab, LAAS-CNRS, France Anthony Galton, University of Exeter, UK Michael Gelfond, University of El Paso, USA Michael GeorgefF, Australian AI Institute, Australia Peter Haddawy, University of Wisconsin-Milwaukee, USA Pat Hayes, University of Illinois at Urbana-Champaign, USA Peter Ladkin, Uni-versitaet Bielefeld, Germany Gerard Ligozat, Universite Paris XI, France Angelo Montanari (co-chair), Università' di Udine, Italy Robert Morris, Florida Institute of Technology, USA Bernhard Nebel, Universitaet des Saarlandes, Germany Don Perlis, University of Maryland, USA Han Reichgelt, University of the West Indies, Jamaica Raymond Reiter, University of Toronto, Canada Mark Reynolds, Kings CoUege, UK Ma-arten de Rijke, CWI, The Netherlands Erik Sandewall, Linkoping University, Sweden Marek Ser-got, Imperiai College, UK Murray Shanahan, Imperiai CoUege, UK Peter van Beek, University of Alberta, Canada Andre Trudel, Acadia University, Canada 3 Summary of Important Dates December 5, 1995 - Submission deadline February 26, 1996 - Notification of acceptance April 15, 1996 - Camera-ready copy deadUne May 19-20, 1996 - TIME-96 Workshop May 20-22, 1996 - FLAIRS-96 Conference Machine Learning List The Machine Learning List is moderated. Contributions should be relevant to the scientific study of machine learning. Mail contributions to ml@ics.uci.edu. Mail requests to be added or deleted to ml-request@ics.uci.edu. Back issues may be FTP'd from ics.uci.edu in pub/ml-list/V/ or N.Z where X and N are the volume and number of the issue; ID: anonymous PASSWORD: URL- http://www.ics.uci.edu/AI/-ML/Machine-Learning.html First Workshop on Numerical Analysis and Applications Russe, Bulgaria June 24-27, 1996 Organizers University of Russe, Association of Bulgarian Mathematicians - Russe Co-organizers Institute of Mathematics and Center for Informatics and Information Technologies of the Bulgarian Academy of Sciences, Technical University of Gabrovo, Technical University of Sofia Traditionally every 4 years a Conference on Numerical Analysis and Applications is organized in Bulgaria. The present workshop is meant to support this tradition and to serve as an intermediate meeting between these conferences. We would like to give an opportunity for mathematicians and applied scientists to discuss topics of common interest. The workshop wiU have three tracks: 1. Numerical linear algebra. 2. Numerical methods for differential equations. 3. Numerical modelling. Preliminary list of Invited Speakers R. Bisseling (Netherlands), L. Brugnano (Italy), S. K. Godunov (Russia), A. Griewank (Germany), A. Hadjidimos (USA), S. Hammarling (UK), W. Hofmann (Germany), A. Karageorghis (Cyprus), Yu. A. Kuznetsov (Russia), R. Maerz (Germany), W. T. Pickering (UK), R. Plemmons (USA), I. V. Puzynin (Russia), G. I. Shishkin (Russia), T. Szulc (Poland), E. E. Tyrtyshnikov (Russia), W. Varnhorn (Germany), V. V. Voevodin (Russia), Z. Zlatev (Denmark). Organizing committee L. Vulkov (Chair), P. Yalamov (co-Chair), A. An-dreev, P. Ivanova, I. Lirkov, M. Paprzycki, V. Pavlov, S. Romanova, T. Todorov, K. Zlateva. We would like to invite aU interested individuals to ORGANIZE a MINISYMPOSIUM related to one or more of the conference tracks. Please send a minisymposium abstract (approximately one page) and a list of 4-8 speakers to one of the addresses listed below. The deadline for proposals is December 31, 1995. A general call for papers and more details about the meeting will be provided in the future announcements. For more information, please, contact: Plamen Yalamov, Dept. of Mathematics, University of Russe, 7017 Russe, BULGARIA, yalamovQiscbg.acad.bg Marcin Paprzycki, Dept. of Matliematics and CS, UT Permian Basin, Odessa, TX 79762, USA, paprzycki jnOgusher. pb. utexas . edu THE MINISTRY OF SCIENCE AND TECHNOLOGY OF THE REPUBLIC OF SLOVENIA Address: Slovenska 50, 61000 Ljubljana, Tel.: +386 61 1311 107, Fax: +386 61 1324 140. WWW:http://www.mzt.si Minister: Prof. Rado Bohinc, Ph.D. State Secretary for Int. Coop.: Rado Genorio, Ph.D. State Secretary for Sci. and Tech.: Ciril Baškovič Secretary General: Franc Hudej, Ph.D. The Ministry also includes: The Standards and Metrology Institute of the Republic of Slovenia Address: Kotnikova 6, 61000 Ljubljana, Tel.: +386 61 1312 322, Fax: +386 61 314 882., and The Industrial Property Protection Office of the Republic of Slovenia Address: Kotnikova 6, 61000 Ljubljana, Tel.: +386 61 1312 322, Fax: +386 61 318 983. Scientific Research and Development Potential. The statistical data for 1993 showed that there were 180 research and development institutions in Slovenia. Altogether, they employed 10,400 people, of whom 4,900 were researchers and 3,900 expert or technical staif. In the past ten years, the number of researchers has almost doubled: the number of Ph.D. graduates increased from 1,100 to 1,565, while the number of M.Sc.'s rose from 650 to 1,029. The "Young Researchers" (i.e. postgraduate students) program has greatly helped towards revitalizing research. The average age of researchers has been brought down to 40, with one-fifth of them being younger than 29. The table below shows the distribution of researchers according to educational level and sectors (in 1993): Sector Ph.D. M.Sc. Business enterprises 51 196 Government 482 395 Private non-profit organizations 10 12 Higher education organizations 1022 426 Total 1,565 1,029 mainly small businesses. The shortfall was addressed by increased public-sector spending: its share of GDP nearly doubled from the mid-seventies to 0,86% in 1993. Income of R&D organizations spent on R&D activities in 1993 (in million US$): Sector Total Basic App. Exp. res. res. dev. Business ent. 83,9 4,7 32,6 46,6 Government 58,4 16,1 21,5 20,8 Private non-p. 1,3 0,2 0,6 0,5 Higher edu. 40,9 24,2 8,7 8 Total 184,5 45,2 63,4 75,9 Financing Research and Development. Statistical estimates indicate that US$ 185 million (1,4% of GDP) was spent on research and development in Slovenia in 1993. More than half of this comes from public expenditure, mainly the state budget. In the last three years, R&D expenditure by business organizations has stagnated, a result of the current economic transition. This transition has led to the financial decline and increased insolvency of firms and companies. These cannot be replaced by the growing number of The policy of the Slovene Government is to increase the percentage intended for R&D in its budget. The Science and Technology Council of the Republic of Slovenia is preparing the draft of a national research program (NRP). The government will harmonize the NRP with its general development policy, and submit it first to the parliamentary Committee for Science, Technology and Development and after that to the parliament. The parliament approves the NRP each year, thus setting the basis for deciding the level of public support for R&D. The Ministry of Science and Technology is mainly a government institution responsible for controlling expenditure of the R&D budget, in compliance with the NRP and the criteria provided by the Law on Research Activities. The Ministry finances research or CO- finances development projects through public bidding, partially finances infrastructure research institutions (national institutes), while it directly finances management and top-level science. The focal points of R&D policy in Slovenia are: - maintaining the high level and quality of research activities, - stimulating collaboration between research and industrial institutions, - (co)financing and tax assistance for companies engaged in technical development and other applied research projects, - research training and professional development of leading experts, - close involvement in international research and development projects, - establishing and operating facilities for the transfer of technology and experience. JOŽEF STEFAN INSTITUTE Jožef Siefan (1835-1893) was one of the most prominent physicists of the 19th century. Born to Slovene parents, he obtained his Ph.D. at Vienna University, where he was later Director of the Physics Institute, Vice-President of the Vienna Academy of Sciences and a member of several scientific institutions in Europe. Stefan explored many areas in hydrodynamics, optics, acoustics, electricity, magnetism and the kinetic theory of gases. Among other things, he originated the law that the total radiation from a black body is proportional to the 4th power of its absolute temperature, known as the Stefan-Boltzmann law. The Jožef Stefan Institute (JSI) is the leading independent scientific research in Slovenia, covering a broad spectrum of fundamental and applied research in the fields of physics, chemistry and biochemistry, electronics and information science, nuclear science technology, energy research and environmental science. The Jožef Stefan Institute (JSI) is a research organisation for pure and applied research in the natural sciences and technology. Both are closely interconnected in research departments composed of different task teams. Emphasis in basic research is given to the development and education of young scientists, while applied research and development serve for the transfer of advanced knowledge, contributing to the development of the national economy and society in general. At present the Institute, with a total of about 700 staff, has 500 researchers, about 250 of whom are postgraduates, over 200 of whom have doctorates (Ph.D.), and around 150 of whom have permanent professorships or temporary teaching assignments at the Universities. In view of its activities and status, the JSI plays the role of a national institute, complementing the role of the universities and bridging the gap between basic science and applications. Research at the JSI includes the following major fields: physics; chemistry; electronics, informatics and computer sciences; biochemistry; ecology; reactor technology; applied mathematics. Most of the activities are more or less closely connected to information sciences, in particular computer sciences, artificial intelligence, language and speech technologies, computer-aided design, computer architectures, biocybernetics and robotics, computer automation and control, professional electronics, digital communications and ne- tworks, and applied mathematics. The Institute is located in Ljubljana, the capital of the independent state of Slovenia (or S^nia). The capital today is considered a crossroad between East, West and Mediterranean Europe, offering excellent productive capabilities and solid business opportunities, with strong international connections. Ljubljana is connected to important centers such as Prague, Budapest, Vienna, Zagreb, Milan, Rome, Monaco, Nice, Bern and Munich, all within a radius of 600 km. In the last year on the site of the Jožef Stefan Institute, the Technology park "Ljubljana" has been proposed as part of the national strategy for technological development to foster synergies between research and industry, to promote joint ventures between university bodies, research institutes and innovative industry, to act as an incubator for high-tech initiatives and to accelerate the development cycle of innovative products. At the present time, part of the Institute is being reorganized into several high-tech units supported by and connected within the Technology park at the Jožef Stefan Institute, established as the beginning of a regional Technology park "Ljubljana". The project is being developed at a particularly historical moment, characterized by the process of state reorganisation, privatisation and private initiative. The national Technology Park will take the form of a shareholding company and will host an independent venture-capital institution. The promoters and operational entities of the project are the Republic of Slovenia, Ministry of Science and Technology and the Jožef Stefan Institute. The framework of the operation also includes the University of Ljubljana, the National Institute of Chemistry, the Institute for Electronics and Vacuum Technology and the Institute for Materials and Construction Research among others. In addition, the project is supported by the Ministry of Economic Relations and Development, the National Chamber of Economy and the City of Ljubljana. Jožef Stefan Institute Jamova 39, 61000 Ljubljana, Slovenia Tel.:-F386 61 1773 900, Fax.:-t-386 61 219 385 Tlx.:31 296 JOSTIN SI WWW: http://www.ijs.si E-mail: matjaz.gams@ijs.si Contact person for the Park: Iztok Lesjak, M.Sc. Public relations: Natalija Polenec INFORMATICA AN INTERNATIONAL JOURNAL OF COMPUTING AND INFORMATICS INVITATION, COOPERATION Submissions and Refereeing Please submit three copies of the manuscript with good copies of the figures and photographs to one of the editors from the Editorial Board or to the Contact Person. At least two referees outside the author's country will examine it, and they are invited to make as many remarks as possible directly on the manuscript, from typing errors to global philosophical disagreements. The chosen editor will send the author copies with remarks. If the paper is accepted, the editor will also send copies to the Contact Person. The Executive Board will inform the author that the paper has been accepted, in which case it will be published within one year of receipt of the original figures on separate sheets and the text on an IBM PC DOS floppy disk or by e-mail - both in ASCII and the Informatica IM^ format. Style and examples of papers can be obtained by e-mail from the Contact Person or from FTP or WWW (see the last page of Informatica). Opinions, news, calls for conferences, calls for papers, etc. should be sent directly to the Contact Person. QUESTIONNAIRE Send Informatica free of charge Yes, we subscribe Please, complete the order form and send it to Dr. Rudi Murn, Informatica, Institut Jožef Stefan, Jamova 39, 61111 Ljubljana, Slovenia. Since 1977, Informatica has been a major Slovenian scientific journal of computing and informatics, including telecommunications, automation and other related areas. In its 16th year (more than two years ago) it became truly international, although it still remains connected to Central Europe. The basic aim of Informatica is to impose intellectual values (science, engineering) in a distributed organisation. Informatica is a journal primarily covering the European computer science and informatics community -scientific and educational as well as technical, commercial and industrial. Its basic aim is to enhance communications between different European structures on the basis of equal rights and international refereeing. It publishes scientific papers accepted by at least two referees outside the author's country. In addition, it contains information about conferences, opinions, critical examinations of existing publications and news. Finally, major practical achievements and innovations in the computer and information industry are presented through commercial publications as well as through independent evaluations. Editing and refereeing are distributed. Each editor can conduct the refereeing process by appointing two new referees or referees from the Board of Referees or Editorial Board. Referees should not be from the author's country. If new referees are appointed, their names will appear in the Refereeing Board. Informatica is free of charge for major scientific, educational and governmental institutions. Others should subscribe (see the last page of Informatica). ORDER FORM - INFORMATICA Name: ............................................. Office Address and Telephone (optional): Title and Profession (optional): ............................................................ .................................................... E-mail Address (optional): ............. Home Address and Telephone (optional): ........... .................................................... Signature and Date: ................... Referees: David Abramson, Catriel Beeri, Azer Bestavros, Jacek Blazewicz, Laszlo Boeszoermenyi, Ivan Bratko, Jerzy Brzezinski, Marian Bubak, Wojciech Buszkowski, Ryszard Choras, David ClifF, Travis Craig, Tadeusz Czachorski, Luc De Raedt, Georg Dorfner, Maciej Drozdowski, Hesham El-Rewini, Pierre Flener, Terrence Forgarty, Hugo de Garis, Eugeniusz Gatnar, Janusz Gorski, Georg Gottlob, David Green, Herbert Groiss, Inman Harvey, Elke Hochmueller, Rod Ryszard Jakubowski, Eric Johnson, Li-Shan Kang, Roland Kaschek, Jan Kniat, Gilad Koren, Henryk Kravirczyk, Ben Kroese, Zbyszko Krolikowski, Benjamin Kuipers, Phil Laplante, Bud Lawson, Ulrike Leopold-Wildburger, Joseph Y-T. Leung, Raymond Lister, Doug Locke, Andrzej Marciniak, Vladimir Marik, Jacek Martinek, Florian Matthes, Dieter Merkl, Zbigniew Michalewicz, Roland Mittermeir, Tadeusz Morzy, Daniel Mosse, Jerzy Nogieć, Stefano Nolfl, Tadeusz Pankowski, Warren Persons, Gustav Pomberger, Gary Preckshot, Ke Qiu, Michael Quinn, Gerald Quirchmayer, Ewaryst Rafajlowicz, Wolf Rauch, Peter Rechenberg, Felix Redmill, Bo Sanden, Guenter Schmidt, William Spears, Przemyslaw Stpiczynski, Maciej Stroinski, Tomasz Szmuc, Jurij Tasič, Ken Tindell, A Min Tjoa, Wieslaw Traczyk, Marek Tudruj, Andrzej Urbanski, Janusz Zalewski, Yanchun Zhang, Gerhard Widmer EDITORIAL BOARDS, PUBLISHING COUNCIL Informatica is a journal primarily covering the European computer science and informatics community; scientific and educational as well as technical, commercial and industrial. Its basic aim is to enhance communications between different European structures on the basis of equal rights and international refereeing. It publishes scientific papers accepted by at least two referees outside the author's country. In addition, it contains information about conferences, opinions, critical examinations of existing publications and news. Finally, major practical achievements and innovations in the computer and information industry are presented through commercial publications as well as through independent evaluations. Editing and refereeing are distributed. Each editor from the Editorial Board can conduct the refereeing process by appointing two new referees or referees from the Board of Referees or Editorial Board. Referees should not be from the author's country. If new referees are appointed, their names will appear in the Refereeing Board. Each paper bears the name of the editor who appointed the referees. Each editor can propose new members for the Editorial Board or Board of Referees. Editors and referees inactive for a longer period can be automatically replaced. Changes in the Editorial Board and Board of Referees are confirmed by the Executive Editors. The coordination necessary is made through the Executive Editors who examine the reviews, sort the accepted articles and maintain appropriate international distribution. The Executive Board is appointed by the Society Informatika. Informatica is partially supported by the Slovenian Ministry of Science and Technology. Each author is guaranteed to receive the reviews of his article. When accepted, publication in Informatica is guaranteed in less than one year after the Executive Editors receive the corrected version of the article. Executive Editor - Editor in Chief Anton P. Zeleznikar Volaričeva 8, Ljubljana, Slovenia E-mail: anton.p.zeleznikarQijs.si Executive Associate Editor (Contact Person) Matjaž Gams, Jožef Stefan Institute Jamova 39, 61000 Ljubljana, Slovenia Phone: -1-386 61 1773 900, Fax: +386 61 219 385 E-mail: matjaz.gamsQijs.si WWW: http://www2.ijs.si/"mezi/matjaz.html Executive Associate Editor (Technical Editor) Rudi Murn, Jožef Stefan Institute Publishing Council: Tomaž Banovec, Ciril Baškovič, Andrej Jerman-Blažič, Dagmar Suster, Jernej Virant Board of Advisors: Ivan Bratko, Marko Jagodic, Tomaž Pisanski, Stanko Strmčnik Editorial Board Suad Alagić (Bosnia and Herzegovina) Shuo Bai (China) Vladimir Batagelj (Slovenia) Francesco Bergadano (Italy) Leon Birnbaum (Romania) Marco Botta (Italy) Pavel Brazdil (Portugal) Andrej Brodnika (Canada) Janusz Brozyna (France) Ivan Bruha (Canada) Luca Console (Italy) Hubert L. Dreyfus (USA) Jozo Dujmović (USA) Johann Eder (Austria) Vladimir Fomichov (Russia) Janez Grad (Slovenia) Noel Heather (UK) Francis Heylighen (Belgium) Bogomir Horvat (Slovenia) Hiroaki Kitano (Japan) Sylva Kočkova (Czech Republic) Miroslav Kubat (Austria) Jean-Pierre Laurent (France) Jadran Lenarčič (Slovenia) Magoroh Maruyama (Japan) Angelo Montanari (Italy) Igor Mozetič (Austria) Stephen Muggleton (UK) Pavol Navrat (Slovakia) Jerzy R. Nawrocki (Poland) Marcin Paprzycki (USA) Oliver Popov (Macedonia) Sašo Prešern (Slovenia) Luc De Raedt (Belgium) Paranandi Rao (India) Giacomo Delia Riccia (Italy) Wilhelm Rossak (USA) : Claude Sammut (Australia) Johannes Schwinn (Germany) Jin Šlechta (UK) Branko Sonček (Italy) Harald Stadlbauer (Austria) Oliviero Stock (Italy) Gheorghe Tecuci (USA) Robert Trappl (Austria) Terry Winograd (USA) Claes Wohlin (Sweden) Stefan Wrobel (Germany) Xindong Wu (Australia) Volume 19 Number 3 September 1995 ISSN 0350-5596 An International Journal of Computing and Informatics Gonterits: Reliability Optimization of Concurrent Software ■ with Redundancy ; , . An Algorithm for Self-learning and Self-completing Fuzzy Control Rules Performance Bounds on Scheduling Parallel Tasks with Setup Time oii Hypercube Systems . HLO: A Higher-Order Deductive Object-Oriented Database Language On the Balance of the Informational Exchange, Its Flow, and Fractional Revealing Large Informational Quanta, in the 'Hot' Living Systems(T < 0_) . : Elements of Metamatheniatical and Informational Calculus Nonlinear Adaptive Prediction Algorithm and Its Parallel Implementation - , Termination Conditions for Parallel Shape Recognition ' t - ^ Fundamental Tasks in Software Development Environments, A Sound and Complete Axiomatization of Functional Dependencies: A Formal System With Onty Two Inference Rules jrwu K. Yao X.Li S. Bai Z. Liu J.F. Lin S.J. Chen M. Liu J. Slechta A.P. Zeleznikar R.A. Wasniowski Z.M.Wojcik B.E. Wojcik L. Bendix M. Malekovic 291 301 313 319 333 345 371 379 391 407 Reports and Announcements 409