Jacek Grekow
email: j.grekow@pb.edu.pl

Music Emotion Maps in

Keywords: emotion detection, emotion tracking, audio feature extraction, music information retrieval

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

Introduction

Emotions are a dominant element in music, and they are the reason people listen to music so often [START_REF] Pratt | Music as the language of emotion[END_REF]. Systems searching musical compositions on Internet databases more and more often add an option of selecting emotions to the basic search parameters, such as title, composer, genre, etc. The emotional content of music is not always constant, and even in classical music or jazz changes often. Analysis of emotions contained in music over time is a very interesting aspect of studying the content of music. It can provide new knowledge on how the composer emotionally shaped the music or why we like some compositions more than others.

Music emotion recognition, taking into account the emotion model, can be divided into categorical or dimensional. In the categorical approach, a number of emotional categories (adjectives) are used for labeling music excerpts. It was presented in the following papers [START_REF] Grekow | Mood tracking of musical compositions[END_REF][START_REF] Grekow | Mood tracking of radio station broadcasts[END_REF][START_REF] Lu | Automatic mood detection and tracking of music audio signals[END_REF]. In the dimensional approach, emotion is described using dimensional space -2D or 3D. Russell [START_REF] Russell | A circumplex model of affect[END_REF] proposed a 2D model, where the dimensions are represented by arousal and valence; used in [START_REF] Schmidt | Feature selection for content-based, timevarying musical emotion regression[END_REF][START_REF] Yang | A regression approach to music emotion recognition[END_REF]. The 3D model of Pleasure-Arousal-Dominance (PAD) was used in [START_REF] Deng | Dynamic time warping for music retrieval using time series modeling of musical emotions[END_REF][START_REF] Lin | Exploration of music emotion recognition based on midi[END_REF].

Music emotion recognition concentrates on static or dynamic changes over time. Static music emotion recognition uses excerpts from 15 to 30 seconds and omits changes in emotions over time. It assumes the emotion in a given segment does not change. Dynamic music emotion recognition analyzes changes in emotions over time. Methods for detecting emotion using a sliding window are presented in [START_REF] Korhonen | Modeling emotional content of music using system identification[END_REF][START_REF] Lu | Automatic mood detection and tracking of music audio signals[END_REF][START_REF] Schmidt | Feature selection for content-based, timevarying musical emotion regression[END_REF][START_REF] Yang | A regression approach to music emotion recognition[END_REF]. Deng and Leung [START_REF] Deng | Dynamic time warping for music retrieval using time series modeling of musical emotions[END_REF] proposed multiple dynamic textures to model emotion dynamics over time. To find similar sequence pasterns of musical emotions, they used subsequence dynamic time warping for matching emotion dynamics. Aljanaki et al. [START_REF] Aljanaki | Emotion based segmentation of musical audio[END_REF] investigated how well structural segmentation explains emotion segmentation. They evaluated different unsupervised segmentation methods on the task of emotion segmentation. Imbrasaite at al. [START_REF] Imbrasaite | Emotion tracking in music using continuous conditional random fields and relative feature representation[END_REF] and Schmidt at al. [START_REF] Schmidt | Modeling musical emotion dynamics with conditional random fields[END_REF] used Continuous Conditional Random Fields for dimensional emotion tracking.

In our study, we used dynamic music emotion recognition with a sliding window. We experimentally selected a segment length of 6 sec as the shortest period of time after which a music expert can recognize an emotion.

The rest of this paper is organized as follows. Section 2 describes the music annotated data set and the emotion model used. Section 3 presents features extracted by using tools for audio analysis. Section 4 describes regressor training and their evaluation. Section 5 presents the results of emotion tracking. Finally, Section 6 summarizes the main findings.

Music Data

The data set that was annotated consisted of 324 six-second fragments of different genres of music: classical, jazz, blues, country, disco, hip-hop, metal, pop, reggae, and rock. The tracks were all 22050 Hz mono 16-bit audio files in .wav format.

Data annotation was done by five music experts with a university musical education. During annotation of music samples, we used the two-dimensional valence-arousal (V-A) model to measure emotions in music [START_REF] Russell | A circumplex model of affect[END_REF]. The model consists of two independent dimensions (Fig. 1) of valence (horizontal axis) and arousal (vertical axis). Each person making annotations after listening to a music sample had to specify values on the arousal and valence axes in a range from -10 to 10 with step 1. On the arousal axis, a value of -10 meant low while 10 high arousal. On the valence axis, -10 meant negative while 10 positive valence.

Value determination on the A-V axes was unambiguous with a designation of a point on the A-V plane corresponding to the musical fragment. The data collected from the five music experts was averaged. Figure 2 presents the annotation results of a data set with A-V values. Each point on the plane, defined by values of arousal and valence, represents one of 324 musical fragments. As can be seen in the figure, the musical compositions fill the four quadrants formed by arousal and valence almost uniformly. The amount of examples in quarters on the A-V emotion plane is presented in Table 1.

Features Extraction

For feature extraction, we used Essentia [START_REF] Bogdanov | ESSENTIA: an audio analysis library for music information retrieval[END_REF] and Marsyas [START_REF] Tzanetakis | Marsyas: A framework for audio analysis[END_REF], which are tools for audio analysis and audio-based music information retrieval. Marsyas software (version 0.5.0), written by George Tzanetakis, is implemented in C++ and retains the ability to output feature extraction data to ARFF format. With this tool, the following features can be extracted: Zero Crossings, Spectral Centroid, Spectral Flux, Spectral Rolloff, Mel-Frequency Cepstral Coefficients (MFCC), and chroma features -31 features in total. For each of these basic features, Marsyas calculates four statistic features (the mean of the mean, the mean of the standard deviation, the standard deviation of the mean, and the standard deviation of the standard deviation).

Essentia is an open-source C++ library, which was created at Music Technology Group, Universitat Pompeu Fabra, Barcelona. Essentia (version 2.1 beta) contains a number of executable extractors computing music descriptors for an audio track: spectral, time-domain, rhythmic, tonal descriptors, and returning the results in YAML and JSON data formats. Extracted features by Essentia are divided into three groups: low-level, rhythm, and tonal features. Essentia also calculates many statistic features: the mean, geometric mean, power mean, median of an array, and all its moments up to the 5th-order, its energy, and the root mean square (RMS). To characterize the spectrum, flatness, crest and decrease of an array are calculated. Variance, skewness, kurtosis of probability distribution, and a single Gaussian estimate were calculated for the given list of arrays.

The previously prepared, labeled by A-V values, music data set served as input data for tools used for feature extraction. The obtained lengths of feature vectors, dependent on the package used, were as follows: Marsyas -124 features and Essentia -530 features.

Regressor Training

In this paper emotion recognition was treated as a regression problem. We built regressors for predicting arousal and valence using the WEKA package [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. For training and testing, the following regression algorithms were used: SMOreg, REPTree, M5P.

We evaluated the performance of regression using the 10-fold cross validation technique (CV-10). The whole data set was randomly divided into ten parts, nine of them for training and the remaining one for testing. The learning procedure was executed a total of 10 times on different training sets. Finally, the 10 error estimates were averaged to yield an overall error estimate.

For measuring the performance of regression, we used correlation coefficient (CF). Correlation coefficient measures the statistical correlation between the actual values and the predicted values. The correlation coefficient ranges from 1 to -1. Value 1 means perfectly correlated results, 0 there is no correlation, and -1 means that the results are perfectly correlated negatively. The highest values for correlation coefficient (CF) were obtained using SMOreg (implementation of the support vector machine for regression) and are presented in Table 2. CF improved to 0.88 for arousal and 0.74 for valence after applying attribute selection (attribute evaluator: WrapperSubsetEval [START_REF] Kohavi | Wrappers for feature subset selection[END_REF], search method: BestFirst). Predicting arousal is a much easier task for regressors than valence in both cases of extracted features (Essentia, Marsays). CF for arousal were comparable (0.88 and 0.85), but features which describe valence were much better using Essentia for audio analysis. The obtained CF 0.74 was much higher than 0.54 using Marsyas features.

Results of Emotion Tracking

We used the best obtained models for predicting arousal and valence to analyze musical compositions. The compositions were divided into 6-second segments with a 3/4 overlap. For each segment, features were extracted and models for arousal and valence were used.

The predicted values are presented in the figures. For each musical composition, the obtained data was presented in 4 different ways:

1. Arousal-Valence over time; 2. Arousal-Valence map; 3. Arousal over time; 4. Valence over time.

Simultaneous observation of the same data in 4 different projections enabled us to accurately track changes in valence and arousal over time, such as tracking the location of a prediction on the A-V emotion plane. Emotion maps present two different emotional aspects of these compositions. The first significant difference is distribution on the quarters of the Arousal-Valence map. In Let It Be (Fig. 3b), the emotions of quadrants Q4 and Q1 (high valence and low-high arousal) dominate. In Sonata Pathetique (Fig. 4b), the emotions of quarter Q4 (low arousal and low valence) dominate with an incidental emergence of emotions of quarter Q3 (low arousal and low valence).

Emotion Maps

Another noticeable difference is the distribution of arousal over time. Arousal in Let It Be (Fig. 3c) has a rising tendency over time of the entire song, and varies from low to high. In Sonata Pathetique (Fig. 4c), in the first half (s. 0-160) arousal has very low values, and in the second half (s. 160-310) arousal increases incidentally but remains in the low value range.

The third noticeable difference is the distribution of valence over time. Valence in Let It Be (Fig. 3d) remains in the high (positive) range with small fluctuations, but it is always positive. In Sonata Pathetique (Fig. 4d), valence, for the most part, remains in the high range but it also has several large declines in valence (s. 120, 210, 305), which makes valence more diverse.

Arousal and valence over time were dependent on the musical content. Even on a short fragment of music, these values varied significantly. From the course of arousal and valence, it appears that Let It Be is a song of a decisively positive nature with a clear increase in arousal over time. Sonata Pathetique (2nd movement) is mostly calm and predominantly positive.

Features Describing Arousal and Valence Values in Musical Compositions

To analyze and compare changes in arousal and valence over time (time series), we proposed the following parameters: Analysis of the distribution of emotions over time gives a much more accurate view of the emotional structure of a musical composition. It provides not only information on which emotions are dominant in a composition, but also how often they change, and their tendency. The presented list of features is not closed. We will search for additional features in the future.

Comparison of Musical Compositions

Another experiment was to compare selected well-known Ludwig van Beethoven's Sonatas with several of the most famous songs by The Beatles. We used nine musical compositions from each group for the comparison (Table 3). This experiment did not aim to compare all the works of Beethoven and The Beatles, but only to find the rules and most important features distinguishing these 2 groups. Each sample was segmented and arousal and valence were detected. Then, 15 features, which were presented in the previous section, were calculated for each sample. We used the PART algorithm [START_REF] Frank | Generating accurate rule sets without global optimization[END_REF] from the WEKA package [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF] to find the decision-making rules differentiating the two groups.

It turned out that the most distinguishing feature for these two groups of musical compositions was the Standard deviation of Valence. It was significantly smaller in The Beatles' songs than in Beethoven's compositions. Standard deviation of Valence reflects how big deviations were from the mean. The results show that in Beethoven's compositions valence values were much more varied than in the songs of The Beatles.

To find another significant feature in the next stage, we removed the characteristic that we found previously (Standard deviation of Valence) from the data set. Another significant feature was Standard deviation of Arousal. In Beethoven's compositions, the values of the Standard deviation of Arousal were much greater than in the Beatles' songs. This proves the compositions have a greater diversity of tempo and volume.

In the next analogous stage, the feature we found was Standard deviation of derivative of Arousal. It reflects the magnitude of changes in arousal between the studied segments. We found higher values of Standard deviation of derivative of Arousal in Beethoven's compositions.

The interesting thing is that in the group of the most important distinguishing features we did not find features describing emotion type (Mean value of Arousal, Mean value of Valence or Percentage representation of emotion in 4 quarters). This is confirmed by the fact that we cannot assign common emotions to the different sample groups (Beethoven, The Beatles); in all groups, we have emotions from the four quadrants of the emotion model. Features that better distinguish between the two groups of compositions were features pertaining to changes in emotions and their distribution in the musical compositions.

Conclusions

In this article we presented the approach in which the detection of emotion was modeled by the regression problem. Conducting experiments required building a database, annotation of samples by music experts, construction of regressors, attribute selection, and analysis of selected musical compositions. We obtained a satisfactory correlation coefficient value for SVM for regression algorithm at 0.88 for arousal and 0.74 for valence.

The result applying regressors are emotion maps of the musical compositions. They provide new knowledge about the distribution of emotions in musical compositions. They reveal new knowledge that had only been available to music experts until this point. The proposed parameters describing emotions can be used in the construction of a system that can search for songs with similar emotions. They describe in more detail the distribution of emotions, their evolution, frequency of changes, etc.

Fig. 1 .

 1 Fig. 1.Russell's circumplex model[START_REF] Russell | A circumplex model of affect[END_REF]

Fig. 2 .

 2 Fig. 2. Data set on A-V emotion plane

Figures 3 and 4

 4 Figures 3 and 4 show emotion maps of two compositions, one for the song Let It Be by Paul McCartney (The Beatles) and the second, Sonata Pathetique (2nd movement) by Ludwig van Beethoven.Emotion maps present two different emotional aspects of these compositions. The first significant difference is distribution on the quarters of the Arousal-Valence map. In Let It Be (Fig.3b), the emotions of quadrants Q4 and Q1 (high valence and low-high arousal) dominate. In Sonata Pathetique (Fig.4b), the emotions of quarter Q4 (low arousal and low valence) dominate with an incidental emergence of emotions of quarter Q3 (low arousal and low valence).Another noticeable difference is the distribution of arousal over time. Arousal in Let It Be (Fig.3c) has a rising tendency over time of the entire song, and varies from low to high. In Sonata Pathetique (Fig.4c), in the first half (s. 0-160) arousal has very low values, and in the second half (s. 160-310) arousal increases incidentally but remains in the low value range.The third noticeable difference is the distribution of valence over time. Valence in Let It Be (Fig.3d) remains in the high (positive) range with small fluctuations, but it is always positive. In Sonata Pathetique (Fig.4d), valence, for the most part, remains in the high range but it also has several large declines in valence (s. 120, 210, 305), which makes valence more diverse.Arousal and valence over time were dependent on the musical content. Even on a short fragment of music, these values varied significantly. From the course of arousal and valence, it appears that Let It Be is a song of a decisively positive nature with a clear increase in arousal over time. Sonata Pathetique (2nd movement) is mostly calm and predominantly positive.

Fig. 3 .Fig. 4 .

 34 Fig. 3. A-V maps for the song Let It Be by Paul McCartney (The Beatles)

Table 1 .

 1 Amount of examples in quarters on A-V emotion plane

	Quarter Arousal-Valence Amount
	Abbreviation		of examples
	Q1	high-high	93
	Q2	high-low	70
	Q3	low-low	80
	Q4	low-high	81

Table 2 .

 2 Correlation coefficient obtained for SMOreg

	Essentia		Marsyas
	Arousal Valence Arousal Valence
	Before attribute 0.69	0.51	0.79	0.39
	selection
	After attribute 0.88	0.74	0.85	0.54
	selection

Table 3 .

 3 List of musical compositions

	L. v. Beethovens Sonatas	The Beatles
	Sonata Appassionata, part 1	Hey Jude
	Sonata Appassionata, part 2	P.S. I Love You
	Sonata Appassionata, part 3 While My Guitar Gently Weeps
	Sonata Waldstein, part 1	I'll Follow The Sun
	Sonata Waldstein, part 2	It's Only Love
	Sonata Waldstein, part 3	Yesterday
	Sonata Pathetique, part 1	Michelle
	Sonata Pathetique, part 2	Girl
	Sonata Pathetique, part 3	Let It Be

Acknowledgments. This research was realized as part of study no. S/WI/3/2013 and financed from Ministry of Science and Higher Education funds.


Adam Klimowicz
email: a.klimowicz@pb.edu.pl

On Using Speed as The Criteria of State Selection for Minimization of Finite State Machines

Keywords: finite state machine (FSM), state minimization, high speed

This paper presents a heuristic method for minimization of incompletely specified Mealy finite state machines. In this method, such optimization criteria as the speed and possibility of merging other states are taken into account already at the stage of minimizing internal states. Algorithms for the estimation of optimization criteria values are described. The proposed method is based on two states merging. Experimental results for two styles of state encoding and two types of programmable structures are presented. The results show that this approach to minimization of FSM in most of cases is more effective than classical methods in respect of FSM performance.

Introduction

The problem of increase of performance of electronic equipment becomes especially actual. It is connected to an acceleration of rate of human life, broad implementation of products of electronics to all spheres of human life and complication of the tasks solved by electronic equipment. High-speed performance of electronic projects is important in such spheres as computers, robotics, telecommunication, embedded systems, wired and wireless networks, transport, military and etc. The high-speed performance of the electronic system directly depends on performance of the main control unit (system clock frequency) and also on the control units of the separate parts of the system. Generally the control unit represents the sequential circuit which mathematical model is the finite state machine (FSM). There are some approaches to increase the performance of the electronic equipment:

 the technological: using the elements with a high-speed performance;

 the system: using a piping and multi-core processors;

 the circuitry: increase of a supply voltage;  the logical: using the synthesis methods allowing to build FSMs and control units with the maximum high-speed performance, etc.

Today the large number of scientific researches is devoted to the first three directions (especially to the first) while to the fourth direction, according to author, insufficient attention is paid. At the same time, the methods of a logic synthesis can be used for any technological basis, can be applied together with system methods, and do not depend on supply voltage. The first attempts to combine minimization and state assignment procedures were made in [START_REF] Hallbauer | Procedures of state reduction and assignment in one step in synthesis of asynchronous sequential circuits[END_REF][START_REF] Lee | Concurrent Minimization and State Assignment of Finite State Machines[END_REF][START_REF] Avedillo | SMAS: A program for concurrent state reduction and state assignment of finite state machines[END_REF]. In [START_REF] Hallbauer | Procedures of state reduction and assignment in one step in synthesis of asynchronous sequential circuits[END_REF], the problem was considered for asynchronous FSMs so as to minimize the state code length. The method proposed in [START_REF] Lee | Concurrent Minimization and State Assignment of Finite State Machines[END_REF] was applicable only to state machines where the number of states did not exceed 10. In paper [START_REF] Avedillo | SMAS: A program for concurrent state reduction and state assignment of finite state machines[END_REF], a program for concurrent state minimization and state assignment was presented, which made it possible to form incompletely specified state codes.

The problem of the simultaneous minimization of area and signal delay on the critical path is considered in [START_REF] Rama Mohan | A new approach to synthesis of PLA-based FSM's[END_REF][START_REF] Gupta | A state assignment scheme targeting performance and area[END_REF][START_REF] Lindholm | High frequency and low power semi-synchronous PFM state machine[END_REF][START_REF] Liu | An Embedded low power reconfigurable fabric for finite state machine operations[END_REF]. In [START_REF] Rama Mohan | A new approach to synthesis of PLA-based FSM's[END_REF], a structural model of the FSM called MAR model is proposed, which consists of an FSM and a combinational circuit with flip-flops in the feedback loops. In [START_REF] Gupta | A state assignment scheme targeting performance and area[END_REF], codes with two unities (two-hot) and three unities (three-hot) are used. In [START_REF] Lindholm | High frequency and low power semi-synchronous PFM state machine[END_REF], the minimization of power consumption and delay is considered for asynchronous FSMs. The concept of a low power semi-synchronous FSM operating on a high frequency is proposed that can be implemented and tested as an ordinary synchronous FSM. In [START_REF] Liu | An Embedded low power reconfigurable fabric for finite state machine operations[END_REF], a two-level structural model is proposed to minimize the power consumption, area and delay. The first level of this model consists of sequential units, while the second level consists of combinational units of limited size.

The paper [START_REF] Miyazaki | Performance Improvement Technique for Synchronous Circuits Realized as LUT-Based FPGA's[END_REF] presents a new technique for improving the performance of a synchronous circuit configured as a look-up table based FPGA without changing the initial circuit configuration; only the register location is altered. It improves clock speed and data throughput at the expense of latency. In [START_REF] Jozwiak | Fast and compact sequential circuits through the information-driven circuit synthesis[END_REF] a new sequential circuit synthesis methodology is discussed that targets FPGAs and reconfigurable SoC platforms. The methodology is based on the information-driven approach to circuit synthesis, general decomposition and the previously developed theory of information relationship measures.

The paper [START_REF] Huang | On speeding up extended finite state machines using catalyst circuitry[END_REF] proposes a timing optimization technique for a complex finite state machine that consists of not only random logic but also data operators. The proposed technique, based on the concept of catalyst, adds a functionally redundant blockwhich includes a piece of combinational logic and several other registers -to the circuits under consideration so that the timing critical paths are divided into stages.

The paper [START_REF] Nedjah | Evolutionary Synthesis of Synchronous Finite State Machines[END_REF] proposes to use the evolutionary methodology to yield optimal evolvable hardware that implements the state machine control component. The evolved hardware requires a minimal hardware area and introduces a minimal propagation delay of the machine output signals. The paper [START_REF] Czerwiński | Synthesis method of high speed finite state machines[END_REF] is concerned with the problem of state assignment and logic optimization of high speed finite state machines. The method is designed for PAL-based CPLD implementation.

The analysis of available studies showed that there are no works in which the number of internal states and the speed of FSM are simultaneously minimized. In this paper, we propose an heuristic method for minimization of incompletely specified Mealy FSMs with unspecified values of output variables. This method is based on an operation of two states merging, where such optimization criteria as the speed (critical delay path) and possibility of merging other states are taken into account already at the stage of minimizing internal states. In addition to reduction of internal states this method minimizes the number of FSM transitions and FSM input variables.

Preliminaries

An ISFSM can have incompletely specified outputs and incompletely specified transitions. In practice, designers usually redefine the unspecified transitions by transitions to the present state or to the reset state. Sometimes they use transitions to an additional state, where an error signal is generated, what makes it possible to increase the functional reliability of the digital systems. In the presented approach we define the unspecified values only for the output variables and do not change the unspecified transitions.

Let us denote by L the number of FSM input variables of a set X = {x 1 ,…,x L }, by N the number of FSM output variables of a set Y = {y 1 ,…,y N }, by M the number of FSM internal states of a set A = {a 1 ,…,a M }, and by R the minimal number of bits required to encode internal states, where R = intlog 2 M.

A FSM behavior can be described by the transition list. The transition list is a table with four columns: a m , a s , X(a m ,a s ), and Y(a m ,a s ). Each row of the transition list corresponds to one FSM transition. The column a m contains a present state, the column a s contains a next state, the column X(a m ,a s ) contains a transition condition (an input vector), and the column Y(a m ,a s ) contains an output vector. An ISFSM output vector is represented by ternary vector. For example, Y(a m ,a s )="01-0", where 0 denotes zero value, 1 denotes unity value, and dash ("-") denotes a don't care value of the corresponding output variable.

The transition condition may be described in the column X(a m ,a s ) in the form of conjunction of FSM input variables. The transition condition can also be represented by a ternary vector. Since the FSM behavior is deterministic, all the transition conditions from every FSM state should be mutually orthogonal. Two transition conditions are orthogonal if they have different significant values (0 or 1) at least in one position.

Two FSM states a i and a j can be merged, i.e. replaced by one state a i_j , if they are equivalent. Equivalency of two FSM states means that FSM behavior does not change when these states are merged in one. FSM behavior does not change after merging, if the transition conditions from the states a i and a j that lead to different states are orthogonal. If there are transitions from states a i and a j that lead to the same unique state, then the transition conditions for such transitions should be equal. Moreover, the output vectors that are generated at these transitions should be not orthogonal. Note also that in case of two FSM states merging wait states can be formed. The detailed conditions of the states merging procedure are precisely described in paper [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF].

Under FSM states merging the output vectors with unspecified values can be merged only if they are not orthogonal. Thus the significant values (0 or 1) remain without changes, and the unspecified values are replaced by the corresponding significant values. For example, let Y(a i ,a s ) ="1-0-0" and Y(a j ,a s ) ="-1010", and let the states a i and a j assume merging, then the output vector Y(a i_j ,a s ) ="11010" will be formed at the transition from the new state a i_j to the state a s .

Main minimization algorithm

The main strategy of the proposed method consists in finding the set G of all the pairs of FSM states satisfying the merging conditions. Then for each pair of states from set G the trial merging is performed. Finally a pair (a i ,a j ) is selected for merging in such a way that leaves the maximal possibilities for other pairs of FSM states merging. This process repeats as long as there exists a possibility of merging for at least one pair of FSM states. The method was described more precisely in paper [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF].

In distinction from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], in the present paper we chose for merging at each step the pair (a i , a j ) that best satisfies the optimization criteria in terms of speed, and leaves the maximum possibilities for merging other pairs of states. This procedure is repeated while at least one pair of states can be merged. Let (a s , a t ) be a pair of states in G, where S st is the estimate of speed (critical delay path), and M st is the estimate of the possibility to merge other states. Regarding to the above considerations, the FSM minimization algorithm can be described as follows.

Algorithm 1 (general algorithm for FSM minimization)

1. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], form the set G of pairs of states that admit merging. If G =  (no pairs can be merged), go to step 5 2. For each pair of states (a s , a t ) in G, calculate the estimates S st , and M st of the optimization criteria.

3. Choose a pair of states (a i , a j ) for merging. Among all the pairs in G, choose a pair (a i , a j ) for which S ij = min; if there are several such pairs, then choose among them the one for which M ij = max.

4. Merge the pair of states (a i , a j ). Store the results of minimization (transition list and corresponding S st value ). Go to step 1.

5. Among all saved results of minimization select one with minimal S st value.

6. Minimize the number of transitions in the FSM.

7. Minimize the number of input variables in the FSM.

Stop.

Merging of the states a i and a j (step 4 of Algorithm 1), minimization of the number of transitions (step 6 of Algorithm 1) and minimization of the number of input variables (step 7 of Algorithm 1) are performed as described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF].

Algorithms of minimization of the number of transition an input variables are based on some observations. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and the second transition from a 1 under condition 1 x leads to another state a 3 and on each of these transitions not orthogonal output vectors are formed ( 1x is an inversed form of the variable x 1 ). Suppose that the states a 2 and a 3 can be merged. After merging a 2 and a 3 , a new state a 23 is formed. Now two transitions lead from a 1 to a 23 , one under condition x 1 and the second under condition 1

x . The latter means that the transition from a 1 to a 23 is unconditional and two transitions can be replaced by one unconditional transition. Notice that in general transition conditions from a state a 1 can be much more complicated.

At minimization of the number of FSM input variables can be performed at a situation when certain input variables have no impact on the transition conditions. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and another transition from a 1 under condition 1

x leads to a state a 3 and the variable x 1 does not meet anywhere else in transition conditions of the FSM. Suppose that after the states a 2 and a 3 have been merged, the transition from the state a 1 to the state a 23 becomes unconditional, i.e. it does not depend on values of input variables. The latter means that the variable x 1 has no impact on any FSM transition and therefore it is redundant.

Estimation of optimization criteria

To estimate the optimization criteria, all pairs of states in G are considered one after another. For each pair of states (a s , a t ) in G, a trial merging is performed. For the resultant FSM, its internal states are encoded using one of the available methods that will later be used in the synthesis of the FSM, and the system of Boolean functions corresponding to the combinational part of the FSM is built. Next, for the pair (a s , a t ), the speed S st , and the possibility of minimizing other states M st are estimated. The optimization criteria for each pair of states (a s , a t ) in G are estimated at step 2 of Algorithm 1 using the following algorithm.

Algorithm 2 (estimation of optimization criteria).

1. Sequentially consider the elements of the set G.

2. For each pair of states (a s , a t )  G, make a trial merging.

3. Perform the internal states assignment using one of the available methods.

4. Build the system of Boolean functions W corresponding to the combinational part of the FSM.

5. Estimate the critical delay path (speed) S st .

6. Estimate the possibility of other states minimization M st .

7. Return to the original FSM (before merging at step 2).

8. Execute steps 2-7 for all pairs of states in G.

Stop.

The speed of operation of an FSM is determined by the length of the critical path of its combinational part, which is equal to the number of CPLD macrocells or FPGA logic elements involved in the critical path.

The CPLD architecture is a set of functional units of which each consists of two programmable arrays -AND and OR. The outputs of the array AND are connected to the inputs of the array OR; they are called terms. Typically, the number of inputs of functional blocks in CPLDs is sufficiently large (16-54) and it usually exceeds the number of arguments of the functions implemented by the combinational part of the FSM. If the FSM is implemented on the basis of CPLD, then the cause of the decomposition of the system of Boolean functions corresponding to the combinational part of the FSM can be a large number of minterms in the DNF of a function and a large number of arguments of a function. For that reason, when the FSM is implemented on the basis of CPLD, two critical paths are found, and the longest of them is chosen.

In the case of a large number of minterms in the DNF of a function, the linear decomposition with respect to the minterms is used. The number of inputs of the OR gates is restricted by the parameter q max -the maximum number of terms that can be connected to one CPLD macrocell (typically, q max for different families of CPLDs is between 12 and 90). In the case of a large number of arguments, linear decomposition of the Boolean function with respect to the arguments is used, where the number n FB of inputs of CPLD functional blocks is used as the restriction (for different families of CPLDs, n FB is between 16 and 54).

In the general case, the architecture of modern FPGAs can be represented as a set of logic elements based on Look-Up Tables (LUT). A feature of LUTs is that they can realize any Boolean function but with a small number of arguments (typically, 4-6 and more often 4). In the case when the number of arguments of functions to be realized exceeds the number of LUT inputs n L , the Boolean function must be decomposed with respect to the number of arguments [START_REF] Zakrevskij | Logic Synthesis of Cascade Circuits[END_REF]. Among the great number of decomposition methods for Boolean functions with respect to the number of arguments, linear decomposition methods are most popular. They are used in the majority of industrial EDA tools. When the FSM is implemented on the basis of FPGA, the length of the critical path depends only on the maximum number of arguments of the realized functions.

Algorithm 3 (for the estimation of the FSM speed of operation).

1. Find the maximum number L max of arguments of the functions realized by the combinational part of the FSM. For each pair of states (a s , a t ) in G, calculate the estimates S st , and M st of the optimization criteria

  i W w w L L i   max max , (1)
where L(w i ) is a set of arguments of the function w i . If the FSM is implemented on the basis of CPLD, then additionally the maximum number of minterms in the DNFs of the functions realized by the combinational part of the FSM is determined:

  i W w w Q Q i   max max , (2)
where Q(w i ) is a set of minterms in the DNF of the function w i .

2. Calculate the length of the critical path in the combinational part of the FSM.

2.1.

If the FSM is implemented on the basis of CPLD, then the lengths of two critical paths are found: one (S L ) depending on the maximum number of arguments ( ]x[ is the minimal integer greater than or equal to x):

S L = 1 + ](L max -n FB )/(n FB -1)[ (3)
and the other (S Q ) depending on the maximum number of terms:

S Q = 1 + ](Q max -q max )/(q max -1)[. (4)
Set S st = max(S L , S Q ).

2.2.

If the FSM is implemented on the basis of FPGA, the length of the critical path is determined only based on the maximum number of arguments:

S st = 1 + ](L max -n L )/(n L -1)[. (5)

Stop.

The estimate M st is determined by the number of pairs of the FSM that can be merged after merging the pair (a s , a t ). To provide the best possibilities for merging other states, M st should be maximized. With regard to the above considerations, the algorithm for estimating the FSM speed of operation is as follows.

Algorithm 4 (for estimation of possibility of merging other states).

1. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], find the set G st of pairs of states that can be merged upon merging the pair (a s , a t ). For each pair of states (a s , a t )  G, make a trial merging.

Set

M st = | G st |. 3. Stop.

Experimental results

The method for minimization was implemented in a program called ZUBR. The ZUBR system is the scientific-industrial software developed for design of digital systems based on programmable logic. To estimate the efficiency of the offered method we used MCNC FSM benchmarks [START_REF] Yang | Logic synthesis and optimization benchmarks user guide[END_REF]. Each of tested FSM benchmarks was encoded using binary and one-hot encoding. The speed was calculated for the initial FSM, the STAMINA program [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF] and the method described in this paper. Two models of programmable structures were used for experiments. The CPLD device model has following parameters, which can affect synthesis result: q max =5 and n FB =54. It corresponds to real CPLD devices, such as XC9500XL from Xilinx. The FPGA device model has only one parameter, which can affect synthesis result: n L =4. It corresponds to most of real FPGA devices, such as Virtex and Spartan from Xilinx or Cyclone and Stratix from Altera.

The experimental results for binary encoding and synthesis using the CPLD device are presented in Table 1, where M 0 and S 0 are, respectively, the number of internal states and signal delay critical path (the number of logical levels after synthesis) of the initial FSM; M 1 and S 1 are, respectively, the same parameters after minimization using STAMINA and M 2 , and S 2 are, respectively the same parameters after minimization using proposed method (with taking in consideration speed of FSM). S 0 /S 2 and S 1 /S 2 are ratios of the corresponding parameters; and Mean is the geometric mean value. The analysis of Table 1 shows that application of the proposed method using binary encoding allows to reduce the number of internal states of the initial FSM. Similarly, the average reduction of the critical delay path of the FSM makes 1.44 times, and on occasion (example train11) 2.5 times. In comparison to STAMINA the number of states is higher in 1 case but the average reduction of the critical delay path of the FSM makes 1.67 times, and on occasion (example bbsse) 2.89 times.

The experimental results for one-hot encoding and CPLD device are presented in Table 2, where all parameters have the same meaning as in Table 1. The analysis of Table 2 shows that application of the proposed method using one-hot encoding allows to reduce the number of internal states of the initial FSM. Similarly, the average increase of the speed of the FSM makes 1.38 times, and on occasion (example train11) 2.5 times. In comparison to STAMINA the number of states is higher in 1 case but the average reduction of the critical delay path of the FSM makes 1.43 times, and on occasion (example tma) 2.17 times. The experimental results for binary encoding and FPGA device are presented in Table 3, where all parameters have the same meaning as in Table 1 and Table 2. The analysis of Table 3 shows that the average reduction of the critical delay path of the FSM makes 1.25 times, and on occasion (examples lion9 and train11) 2 times. In comparison to STAMINA the number of states is higher in one case and speed of FSM for both methods is equal.

The experimental results for one-hot encoding and FPGA device are presented in Table 4, where all parameters have the same meaning as in above tables. The analysis of Table 4 shows that application of the proposed allows to reduce the critical delay path 1.27 times, and on occasion even 2 times. In comparison to STAMINA the number of states is higher in one case (example beecount). The average reduction of the critical delay path of the FSM is almost equal (in extreme cases -for tma benchmark reduction ratio is equal 1.33, but for beecount -0.67).

It can be noticed that the reduction of states in most of cases leads to critical path reduction of FSMs. But for 3 cases, if using STAMINA minimization program, there was a longer critical delay path than for the FSM without using minimization. These results were obtained when minimization for CPLD was performed. The analysis of the Table 5 shows that results obtained using presented approach are better than results obtained from the STAMINA in all styles of encoding used. Also, the one-hot encoding style was the better than binary in terms of FSM speed for all considered cases for CPLD devices. Table 6 presents the average speed for two used encoding styles for FPGA device, where all parameters have the same meaning as in Table 5. The analysis of the Table 6 shows that results obtained using presented approach are equal or better than results obtained from the STAMINA in both of styles of encoding used. Also, the binary encoding style was the better than one-hot in terms of FSM speed for all considered cases for FPGA devices. It can be noticed, that in terms of speed, the binary encoding is more effective for FPGA devices and the one-hot encodingfor CPLD. It is related to fact, that the key parameters for FPGA devices is the number of arguments of each function, which is often higher than the number of minterms in tested benchmarks. The last mentioned parameter is a key parameter in synthesis on CPLD. To increase speed in FPGA implementation we can use other methods of decomposition, e.g. functional decomposition [START_REF] Luba | A General Approach to Boolean Function Decomposition and its Applications in FPGA-based synthesis[END_REF].

Conclusion

In this paper an efficient method for ISFSM minimization was presented. In this method, the critical delay path is taken into account already at the stage of the minimization of the number of internal states. The presented method allows to reduce the number of internal states of FSM and additionally it allows to increase a speed of FSMs comparing to STAMINA program . The proposed method also allows to reduce the number of FSM transitions and input variables. The time of execution of presented algorithm do not exceed 20 seconds on the computer with Intel i3 processor for FSMs having more than 200 states and 1500 transitions.

In future, more experiments with real digital systems will be performed using industrial EDA tools and specific programmable devices. In the offered approach to FSM minimization only two states merging is considered. The presented method can be modified to join a group of states containing more states. Proposed method is only the part of work on the complex minimization method [START_REF] Solov'ev | Complex minimization method for finite state machines implemented on programmable logic devices[END_REF], where speed, power consumption and area parameters are taken in consideration. In future, this method will serve to minimize power, cost and increase speed for FSM realization on programmable logic devices.

Table 1 .

 1 The experimental results for binary encoding and CPLD device

	Name	M0	S0	M1	S1	M2	S2	S0/S2	S1/S2
	bbara	10	7	7	4	7	4	1,75	1,00
	bbsse	16	10	13	26	13	9	1,11	2,89
	beecount	7	5	4	4	5	4	1,25	1,00
	lion9	14	4	4	3	4	2	2,00	1,50
	s27	6	7	5	6	5	5	1,40	1,20
	sse	16	10	13	26	13	9	1,11	2,89
	tma	20	6	18	16	18	6	1,00	2,67
	train11	12	5	4	3	4	2	2,50	1,50
	Mean							1,44	1,67

Table 2 .

 2 The experimental results for one-hot encoding and CPLD device

	Name	M0	S0	M1	S1	M2	S2	S0/S2	S1/S2
	bbara	10	3	7	2	7	2	1.50	1.00
	bbsse	16	7	13	12	13	7	1.00	1.71
	beecount	7	5	4	4	5	4	1.25	1.00
	lion9	14	4	4	3	4	2	2.00	1.50
	s27	6	7	5	6	5	5	1.40	1.20
	sse	16	7	13	12	13	7	1.00	1.71
	tma	20	6	18	13	18	6	1.00	2.17
	train11	12	5	4	3	4	2	2.50	1.50
	Mean							1.38	1.43

Table 3 .

 3 The experimental resultS for binary encoding and FPGA device

	Name	M0	S0	M1	S1	M2	S2	S0/S2	S1/S2
	bbara	10	3	7	2	7	2	1.50	1.00
	bbsse	16	3	13	3	13	3	1.00	1.00
	beecount	7	2	4	2	5	2	1.00	1.00
	lion9	14	2	4	1	4	1	2.00	1.00
	s27	6	2	5	2	5	2	1.00	1.00
	sse	16	3	13	3	13	3	1.00	1.00
	tma	20	3	18	3	18	3	1.00	1.00
	train11	12	2	4	1	4	1	2.00	1.00
	Mean							1.25	1.00

Table 4 .

 4 The experimental resultS for one-hot encoding and FPGA device

	Name	M0	S0	M1	S1	M2	S2	S0/S2	S1/S2
	bbara	10	5	7	4	7	4	1.25	1.00
	bbsse	16	7	13	6	13	6	1.17	1.00
	beecount	7	3	4	2	5	3	1.00	0.67
	lion9	14	4	4	2	4	2	2.00	1.00
	s27	6	3	5	3	5	3	1.00	1.00
	sse	16	7	13	6	13	6	1.17	1.00
	tma	20	6	18	8	18	6	1.00	1.33
	train11	12	4	4	2	4	2	2.00	1.00
	Mean							1.27	0.99

Table 5

 5 presents the average speed for two used encoding styles for CPLD device. S AV0 , S AV1 and S AV2 parameters stand for the average speed of the initial FSM, the FSM after minimization using the STAMINA program and the method from this paper accordingly.

Table 5 .

 5 Average speed comparison for tested encodings for CPLD device

	Encoding SAV0 SAV1	SAV2
	Binary	6.75 11.0 5.125
	One-hot	5.5 6.875 4.375

Table 6 .

 6 Average speed comparison for tested encodings for FPGA device

	Encoding SAV0	SAV1	SAV2
	Binary	2.5 2.125 2.125
	One-hot 4.875 4.125	4.0

Acknowledgements. The research was done in the framework of the grant S/WI/1/2013 and financed from the funds for science by MNiSW.


Petros-Fotios Alvanitopoulos

Ioannis Andreadis
email: iandread@ee.duth.gr

Anaxagoras Elenas
email: elenas@civil.duth.gr

Fuzzy inference systems for automatic classification of earthquake damages

Keywords: Seismic Parameters, Earthquake Damage Classification, Fuzzy Inference Systems

This paper presents efficient models in the area of damage potential classification of seismic signals. After an earthquake, one of the most important actions that authorities must take is to inspect structures and estimate the degree of damages. The interest is obvious for several reasons such as public safety, economical recourses management and infrastructure. This approach provides a comparative study between the Mamdani-type and Sugeno-type fuzzy inference systems (FIS). The fuzzy models use a set of artificial accelerograms in order to classify structural damages in a specific structure. Previous studies propose a set of twenty well-known seismic parameters which are essential for description of the seismic excitation. The proposed fuzzy systems use an input vector of twenty seismic parameters instead of the earthquake accelerogram and produce classification rates up to 90%. Experimental results indicate that these systems are able to classify the structural damages in structures accurately. Both of them produce the same level of correct classification rates but the Mamdani-type has a slight superiority.

Introduction

Earthquake engineering can be defined as the field of engineering which deals with earthquakes and their effect on structures such as multistory buildings, bridges, towers, etc. As with any other natural phenomenon, earthquakes and their effects should be considered when designing a structure to ensure its safety. However, it is not economically feasible to design a structure that can withstand any seismic event without damages (elastic response). Sometimes devastating earthquakes hit populated areas. In this case, the ability to estimate the post-seismic damage status of oscillated structures instantly after the earthquake event may optimize the administration measures (optimized management of human and material resources, reduction of loss of lives and injuries).

The thrust of the current research is the automatic approach of the post-seismic status of buildings using intelligent FIS. Two types of fuzzy systems (Mamdani and Sugeno) are designed and implemented. These models use a set of artificial accelerograms. Numerical results indicate the ability of them to classify the structural damage in the examined structure.

In this research the set of artificial accelerograms is applied as a case study to a sixth floor reinforced concrete frame structure. The proposed classifiers can estimate the degree of structural damage on any other structure under the precondition that the training phase is carried out for the same building.

The key point of this study is to map the input space (artificial accelerograms) to an output space (degree of structural damage). Accelerograms are records of the acceleration versus time measured during an earthquake ground motion. The seismic accelerograms are a useful tool in earthquake engineering because they are able to provide an explicit description of the seismic excitation. However, due to the random sizes and shapes it is very difficult to exploit their similarities. Therefore, a set of twenty seismic parameters has been used to represent the seismic signals. These seismic parameters have been presented in the literature during the last decades and are able to express the damage potential of earthquakes. Table 1 presents those parameters. Previous study [START_REF] Elenas | Correlation Study Between Seismic Acceleration Parameters and Damage Indices of Structures[END_REF] reveals the correlation grade between seismic parameters and damage indices of structures. For the present approach the level of structural damage caused by an earthquake is numerically quantified using damage indices (DIs). In recent years considerable efforts have been devoted to develop different types of damage indices (local-global). In general, a damage index is local when it refers to a restricted area (e.g. a cross section), while it is considered global when it describes the state of the whole structure. In this study the systems were developed based on the maximum inter storey drift ratio (MISDR) [START_REF] Rodriguez-Gomez | Evaluation of Seismic Damage Indices for Reinforced Concrete Structures[END_REF] and the widely used Park/Ang [START_REF] Park | Mechanistic Seismic Damage Model for Reinforced Concrete[END_REF] overall damage indicator.

In order to quantify the consequences of an earthquake, it is necessary to know the physical deterioration (damage) of the building suffered during the seismic event. The examined set of 450 artificial accelerograms generates a wide spectrum of structural damage from negligible to severe. The values of damage indices of each accelerogram are divided into four damage categories (low-medium-largetotal) according to Table 2. These classes correspond to non damage or minor damage, repairable damage, irreparable damage and partial or total collapse of the building, respectively. According to this classification of the structural damages it seems at first sight that the classification is unequivocal. However, from the engineer's point of view, a damage index value close to the class limits cannot be classified unequivocally to a specific damage category. For example, a structural damage ratio of 0.499 cannot unequivocally classify the accelerogram in the low class, because the option to belong in the medium class should be possible. Thus, the set of damage indices can be considered as a fuzzy set and fuzzy methods are appropriate to be applied to such classification procedures.

Damage Degree Structural Damage

Indicators

Low Medium Large Total

Park/Ang DI G [-] ≤ 0.3 0.3 < DI G ≤ 0.6 0.6 < DI G ≤ 0.8 DI G > 0.8 MISDR [%] ≤ 0.5 0.5< MISDR ≤ 1.5 1.5< MISDR ≤ 2.5 > 2.5
Previous studies [START_REF] Andreadis | Intelligent Seismic Acceleration Signal Processing for Damage Classification in Buildings[END_REF][START_REF] Alvanitopoulos | A New Algorithm for the Classification of Earthquake Damages in Structures[END_REF][START_REF] Alvanitopoulos | A Genetic Algorithm for the Classification of Earthquake Damages in Buildings[END_REF] attempt to classify the structural damages in buildings. The first approach is based on the shape similarity of accelerograms. However, due to the random nature of seismic signals this approach led to a poor classification rates. The second approach is based on seismic parameters which can express the damage potential of an earthquake [START_REF] Elenas | Correlation Study Between Seismic Acceleration Parameters and Damage Indices of Structures[END_REF]. These seismic parameters were graphically used to represent the seismic load instead of the accelerogram itself. The extracted classification results based on artificial neural networks (ANNs) were better than the results of the first approach. Nevertheless, it was desirable to test the accuracy of the system using an additional damage index and a wide set of seismic signals. This has been achieved by the third technique using a combination of genetic algorithm and ANNs.

This paper studies the potential of two alternate soft computing techniques for earthquake damage classification based on fuzzy logic. Fuzzy classifiers have been successfully and widely applied to many fields. Moreover, recently the evolving fuzzy rule based classifiers have been proved promising tools that offer high performance (classification rates) and computational efficiency [START_REF] Angelov | Evolving Fuzzy-Rule-Based Classifiers from Data Streams[END_REF][START_REF] Angelov | Evolving Fuzzy Classifiers Using Different Model Architectures[END_REF]. The ability of fuzzy logic to model nonlinear functions of arbitrary complexity makes it even more important to investigate its ability to estimate the earthquake damage in buildings. The classification results show that these systems are able to estimate the seismic vulnerability of buildings avoiding complex mathematical processes.

Proposed Method

The Mamdani-Type Fuzzy Inference System

The proposed fuzzy system has twenty inputs corresponding to the twenty seismic parameters that result from the processing of seismic signals. These values can represent seismic accelerograms and are normalized into a range [0, 1]. The FIS has one output that indicates the level of earthquake damage in structure. A model of the system is shown in Fig. 1.

The fuzzyfication of the inputs is realized using four Gaussian-shaped membership functions (mfs), namely low, medium, large and total. On the other hand the output consists of four triangular-shaped mfs, namely low, medium, large and total. The number and shape of the mfs were selected after an extensive set of preliminary tests. These tests involved simulations with different types and numbers of mfs such as triangular, trapezoidal and Gaussian. The tests confirmed that the below mfs presents good qualitative results. The following equations define the membership functions.

The Gausian function depends on two parameters σ and c as given by:

2 -(x-c) 2 2σ f(x, σ,c) = e (1)
where c and σ are the mean value and the variance, respectively. Low:

The triangular function depends on two parameters m and σ as given by:

m x 1 f o rm x m x m 1 f o rm x m 0 o t h e r w i s e f (x;m, ) - ⎧ ⎫ - -σ ≤≤ ⎪ ⎪ σ ⎪ ⎪ ⎪ ⎪ - - ≤≤ σ + ⎨ ⎬ σ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ σ = (6
) where m and σ are the center and width of the triangular-shaped function, respectively.

Low: 1 0 x 1 for 0.3333 x 0 0.3333

x 0 1 for 0 x 0.3333 0.3333 0 o t h e r w i s e mf (x;0, 0.3333)

- ⎧ ⎫ - - ≤≤ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ - - ≤≤ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ = (7)
- ⎧ ⎫ - ≤ ≤ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ - - ≤ ≤ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ = (8)
Large: 3 0.6667 x 1 for 0.3333 x 0.6667 0.3333 x 0.6667 1 for 0.6667 x 1 0.3333 0 o t h e r w i s e mf (x;0.6667, 0.3333)

- ⎧ ⎫ - ≤ ≤ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ - - ≤ ≤ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ = (9)
Total: The inputs are routed to the output through a Mamdani [START_REF] Mamdani | An Experiment in Linguistic Synthesis with a Fuzzy Logic Controller[END_REF] type of fuzzy inference that uses a set of rules which is not unique and depends on the number of the training samples. In this study two DIs have been used so the structure of the model has a different set of rules for each damage indicator. Knowing the training data points it is possible to extract fuzzy rules [START_REF] Kulkarni | Computer Vision and Fuzzy-Neural Systems[END_REF]. In an effort to generate fuzzy rules the following steps have been considered:

- ⎧ ⎫ - ≤ ≤ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ - - ≤≤ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ = (10)
Step 1: Divide the input/output space into fuzzy regions and assign each region a fuzzy membership function. In this approach the number of regions for each variable is equal to four since four are the aforementioned membership functions.

Step 2: Generate fuzzy rules using the training samples. First determine the degree of the given training input X for each membership function, and assign the input to the region with the maximum degree of membership. The extracted rule is as follows:

R 1 : If X 1 is Low ^ X 2 is Large . . . X 20 is Medium, THEN Y is Low
Step 3: Assign a degree to each rule: For each data point a fuzzy rule is generated. The degree of the fuzzy rule is: D(R 1 )=min(μLow(X 1 ),μLarge(X 2 ),…μMedium(X 20 )) [START_REF] Sugeno | Industrial Applications of Fuzzy Control[END_REF] In this model the antecedent of each rule has more than one part. The antecedent consists of twenty terms since twenty are the seismic parameters. The fuzzy operator AND (min) is applied to obtain a number that represents the result of the antecedent of each rule. In Mamdani type of fuzzy inference, the fuzzy sets from the consequent of each rule are combined through the aggregation operator and the resulting fuzzy set is defuzzified to yield the output of the system. The aggregation operator, in this case, is set to maximum and the defuzzification method is that of the center of gravity (CoG) [START_REF] Kulkarni | Computer Vision and Fuzzy-Neural Systems[END_REF].

The Tagaki-Sugeno-Kang (TSK)-Type Fuzzy Inference System

In the present study a (TSK) fuzzy system was used for the classification of earthquake damage in the examined structure. This methodology was introduced in 1985 [START_REF] Sugeno | Industrial Applications of Fuzzy Control[END_REF], and it is similar to the Mamdani method in many respects. The first two parts of the fuzzy inference process, fuzzifying the inputs and applying the fuzzy operator, are exactly the same. The main difference between Mamdani and Sugeno is that the Sugeno output membership functions are either linear or constant.

Let D be the set of input-output data pairs (training data), X={x 1 ,…,x n } p ⊂ be the set of p-dimensional input vectors, and Y={y 1 ,…,y n } ⊂ be the associated set of output vectors. The set Z with input-output vectors taken together can be denoted by:

p p 1 k k k x Z z , k 1,..., n y + ∈ ℜ = = ∈ℜ = ∈ ℜ ⎧ ⎫ ⎛ ⎞ ⎨ ⎬ ⎜ ⎟ ⎝ ⎠ ⎩ ⎭ (12)
The TSK model comprises of a set of IF-THEN fuzzy rules having the following form: R 1 : If x 1 is A i1 and ... and x p is A ip Then y i =b i0 +b i1 x 1 +…+b ip x p where i=1,…,M, A ij =(j=1,…,p) are antecedent fuzzy sets, y i is the output of the ith rule, and b il (l=0,1, ...,p) are the consequent parameters. The overall output y overall of the model is computed as follows:

( )

M M i i i i0 i1 1 ip p overall i 1 i 1 M M i i i 1 i 1 y b b x . . . b x y = = = = τ τ + + + ∑ ∑ = = τ τ ∑ ∑ (13)
where τ i is the firing strength of R i .

In our approach the proposed model is a zero-order TSK system. The consequent parameters are set to 0 (except b i0 ) and the outputs of rules are constant. The rule base is the same with the Mamdani fuzzy model. The mfs of the input vector are set using the previous equations [START_REF] Rodriguez-Gomez | Evaluation of Seismic Damage Indices for Reinforced Concrete Structures[END_REF][START_REF] Park | Mechanistic Seismic Damage Model for Reinforced Concrete[END_REF][START_REF] Andreadis | Intelligent Seismic Acceleration Signal Processing for Damage Classification in Buildings[END_REF][START_REF] Alvanitopoulos | A New Algorithm for the Classification of Earthquake Damages in Structures[END_REF]. All consequent mfs from Mamdani are replaced by singleton spikes. The firing strength of each rule is computed using the AND operator, in this case, is set to minimum. The TSK model is shown in Fig. 2.

Results

After the nonlinear dynamic analysis of the structure, two DIs, namely, the DI of Park/Ang, and the MISDR have been computed. According to these DIs, the damages caused by seismic excitations, were classified into four classes. The next step of our method was to pass the seismic signals through the proposed fuzzy models and examine their effectiveness. Artificial accelerograms were used in order to simulate natural earthquakes. Table 3 presents the classification results for the examined FIS. As it can be seen, from Table 3 the same set of training samples provide different number of rules for each DI. The correct classification rates were better in the case of Park/Ang DI than in the case of MISDR. Moreover, the Mamdami system presents better classification rates than the TSK model. However, both of these systems are able to evaluate the seismic damage potential and produce the same level of correct classification rates.

Conclusions

The utility of fuzzy logic in pattern classification problems is nowadays quite extensive. This paper attempts to design diagnostic systems with high classifica-tion accuracy in the scientific area of earthquake engineering. First a set of 450 artificial accelerograms with known damage effects was required in order to derive the parameters which are able to describe the seismic intensity. Two FIS (Mamdani-type, TSK-type) are presented. The Mamdani-type is slightly better. Experimental results show that the systems developed herein, presents the same level of classification rates (up to 90%). These promising results are the starting point for further exploration with more seismic events applied also to other types of structures. Until today, survey is performed with on-site examination by expert engineers. With the proposed technique engineers will have an additional tool which can guide them to a fast and confident estimation of the post-seismic damage condition of interested structures. Moreover, they can be used by the public administration for the adequate post-seismic distribution of financial and other resources in the case of severe earthquakes.

Fig. 1 .

 1 Fig. 1. The Mamdani inference system.

Fig. 2 .

 2 Fig. 2. The TSK fuzzy system.

Table 1 .

 1 Seismic parameters.

	Seismic Parameters
	Peak Ground Acceleration	Power (P 0.90 )
	Peak Ground Velocity	Central Period
	Strong Motion Duration after Trifunac/Brady	Arias Intensity
	Root Mean Square Acceleration	Spectral Displacement
	Spectrum Intensity after Housner	Spectral Velocity
	Spectrum Intensity after Kappos	Spectral Acceleration
	Spectrum Intensity after Martinez-Rueda	Seismic Energy Input
	Seismic Intensity after Fajfar/Vidic/Fischinger	Effective Peak Acceleration (EPA)
	Destructiveness Potential	Maximum EPA
	Cumulative Absolute Velocity	PGA to PGV ratio

Table 2 .

 2 Damage Degree.

Table 3 .

 3 Classification Results Using Mamdani and TSK Fuzzy Systems.

	Type

of FIS Mamdani TSK MISDR DI of Park/Ang MISDR DI of Park/Ang

	Number of training samples	300	300	300	300
	Number of Rules	193	179	193	179
	Number of unknown samples	450	450	450	450
	Number of well recognized samples	392	407	388	393
	Total % of the classification	87.10%	90,44%	86,22%	87,33%


Zbigniew Michalewicz
email: zbyszek@cs.adelaide.edu.au

How Artificial Intelligence may be applied in real world situations

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


Masoud Mohammadian

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

Innovative Applications of Artificial Intelligence

Techniques in Software Engineering

Masoud Mohammadian

University of Canberra, ACT, Australia.

Masoud.mohammadian@canberra.edu.au

Abstract. Artificial Intelligence (AI) techniques have been successfully applied in many areas of software engineering. The complexity of software systems has limited the application of AI techniques in many real world applications. This talk provides an insight into applications of AI techniques in software engineering and how innovative application of AI can assist in achieving ever competitive and firm schedules for software development projects as well as Information Technology (IT) management. The pros and cons of using AI techniques are investigated and specifically the application of AI in IT management, software application development and software security is considered.

Organisations that build software applications do so in an environment characterised by limited resources, increased pressure to reduce cost and development schedules. Organisations demand to build software applications adequately and quickly. One approach to achieve this is to use automated software development tools from the very initial stage of software design up to the software testing and installation. Considering software testing as an example, automated software systems can assist in most software testing phases.

On the hand data security, availability, privacy and integrity are very important issues in the success of a business operation. Data security and privacy policies in business are governed by business requirements and government regulations. AI can also assist in software security, privacy and reliability. Implementing data security using data encryption solutions remain at the forefront for data security. Many solutions to data encryption at this level are expensive, disruptive and resource intensive. AI can be used for data classification in organizations. It can assist in identifying and encrypting only the relevant data thereby saving time and processing power. Without data classification organizations using encryption process would simply encrypt everything and consequently impact users more than necessary. Data classification is essential and can assist organizations with their data security, privacy and accessibility needs. This talk explores the use of AI techniques (such as fuzzy logic) for data classification and suggests a method that can determine requirements for classification of organizations' data for security and privacy based on organizational needs and government policies. Finally the application of FCM in IT management is discussed.


Dencho Batanov
email: com.bd@fit.ac@cy

Knowledge-Based Support for Software Engineering

Keywords: Knowledge, Software Engineering, Software Development Life Cycle (SDLC), Ontology, Expert System. 1

The existing ambiguity of the notion of software engineering is mainly due to the fact that it is based on and depends on knowledge. The new definition of the term "software engineering", proposed in this paper, encounters that fact. The main subject of discussion in the paper is how three different types of knowledge, namely declarative explicit, declarative structured (ontologies) and tacit can be used for effective support of software engineering as both practice and academic subject. Illustrative examples are shown along with some trends for more intensive use of knowledge for support of software engineering.

guidelines. Such a thesis is valid at least to some extent for al engineering disciplines but having in mind the specifics of software products and the existing practice of developing software systems of any size, it could be accepted in full for software engineering although, as the author states, the statements cannot be proved. The problem with this thesis is that the term "human activity" is too broad and vague that obviously cannot be used to clearly define the term of "software engineering". On the other hand the activities which distinguish distinctly the humans from the other forms of life are based on creating and continuous use of knowledge. There are different types of knowledge and different approaches to its classification, for example one is to classify knowledge as static, dynamic, declarative, procedural, heuristic, knowledge of methods and knowledge of equipment and tools; another is to separate knowledge in three different levelssurface, domain and deep; and as another option knowledge in classified in two large groups -explicit (objective) and tacit (subjective). No matter how the knowledge is classified the practice of software engineering shows that knowledge of different types is intensively used in all its phases. This can be expressed by the following definition of the term of software engineering:

Software engineering is a systematic approach to the management and development of software systems based on use of all kinds of knowledge, which is embedded in the final software product. Fig. 1 shows the basic idea of the above definition. Central point of the definition is the focus on use of all kinds of knowledge, which in this particular case is classified in three groups: explicit (declarative knowledge), ontologies (declarative structured knowledge) and tacit (individual-related knowledge, which is result of accumulated experience and expressed mainly in a form of rules). It is worth noting at least three interesting properties of the definition: (a) it deals with the two meanings of technology -tools (software products) and processes (management and development); (b) it covers the two major activities in engineering of software systemsmanagement (team organization, choosing the strategy, planning, scheduling, budgeting, cost estimation, maintenance, etc.) and development (use of models, methods, techniques and tools as elements of the chosen methodology), and (c) the quality of the tool (software system) strongly depends on the quality of the processes (management and development).

The software development life cycle (SDLC) consists of well defined phases that developers carry out during the process of software system development and which are subject of research and education. The above definition adds some new aspects of he development, research and education regarding: (a) the necessity of identifying the specific kind of knowledge, which is appropriate for a given phase of SDLS, and (b) use of existing or creating new methods, techniques and tools for gathering, representing and manipulating knowledge for support of the respective phase of SDLC.

The next sections of the paper represent illustrative examples of using the three types of knowledge from the definition for support of software engineering. The use of declarative explicit knowledge in well-known forms as description of models, methods, techniques and tools, manuals, documentation, standards, etc., is briefly mentioned in Section 2. Section 3 is dedicated to one promising way to use structured declarative knowledge in a form of ontology for supporting some of the phases of software development life cycle. In Section 4 an approach of using tacit knowledge for building expert system for supporting requirements analysis phase is described. Conclusions are outlined and some recommendations for further work are made in Section 5.

Use of declarative explicit knowledge

Without doubt this is the kind of knowledge, which is most well known, popular and available. For more than forty years a lot of specialized knowledge has been created, accumulated and disseminated in form of collections of models, methods, techniques and tools, related books, papers, reports on good and bad practices, curricula, training and certification programs with respective teaching and learning materials, manuals, standards and so on. This valuable repository of knowledge is a great and widely used opportunity for practitioners, educators, students and scientists to learn and know more in the field of software engineering. This kind of knowledge, as it is shown in [START_REF] Dick) Fairley | Software Engineering: from Craft to Profession[END_REF] is the basis of transition of the software engineering discipline from craft to profession.

Declarative explicit knowledge, although usually thematically classified, is nonstructured in nature. To use such type of knowledge the users need guidance by experienced people to be able to navigate among the numerous sources of related information. That is why this knowledge is used mostly in education, including training and certification. Software engineering education is of primary importance for preparing software developers and is a subject of teaching in all academic institutions all over the world. A good example of accumulated knowledge for creating and applying software engineering curricula for universities is the model, proposed by the Joint Task Force on Computing Curricula of IEEE Computing Society and ACM [START_REF]Computing Curriculum -Software Engineering, Public Draft 1, The Joint Task Force on Computing Curricula[END_REF]. The curricula seem to be developed for major of MSc in software engineering but the model can be definitely used for creating the content of related courses at bachelor degree level. We should not forget however that software engineering is based on knowledge and skills from a number of basic courses in Computer Science, such as data structures and algorithms, principles of programming languages, object-oriented programming, databases, etc., which constitute the necessary body of knowledge. In this regard the role of lecturers in software engineering is vital for advising students what to select and read. For example, is not enough to state in the beginning of the course that "software engineering is systematic and disciplined approach to software development" -it is absolutely necessary to support this statement through the entire course with relevant readings, case studies, analyses of good and bad practices and so on. Another good example is to include Software Engineering Project as a separate credited subject in the curriculum giving the students the opportunity to apply their knowledge and skills to development of real software systems. For this purpose they are required to find themselves a lot of additional sources of information about the methods, techniques and tools to be used, analytically compare them and finally to make decision what to be chosen. This is the only way to convert knowledge into practice.

Another useful example of relying on explicit declarative knowledge is the so called codified body of knowledge [START_REF] Dick) Fairley | Software Engineering: from Craft to Profession[END_REF], represented by two significant projects -SEEKA (Software Engineering Education Knowledge Areas) and SWEBOK (SoftWare Engineering Body of Knowledge). SEEKA is more oriented to the knowledge areas that should be covered in an undergraduate curriculum in software engineering while SWEBOK concerns knowledge and practices, which can be applied to most projects most of the time. Although the slight differences both of them offer extremely helpful information about software engineering as a subject of learning and practice.

Software engineering in practice is different from software engineering in education. The differences are in the size and complexity of the projects, the number of people involved, the organization and management of the teams, the required quality of the software product and related compliance with standards, the time and budget constraints, etc. Accordingly, along with the traditional descriptions and manuals of models, methods, techniques and tools, there are additional sources of explicit declarative knowledge, which support the work of practitioners in software engineering. Examples of such sources are the large number of approved and working standards for software quality assurance, the regular publications of professional societies like IEEE and ACM and their special interest groups in software engineering, specialized journals and proceedings of conferences and workshops, analytical reviews of good and bad practices, project reports and so on. Another well known for specialists example is the so-called "Capability Maturity Model" (CMM) [START_REF] Dick) Fairley | Software Engineering: from Craft to Profession[END_REF], created in the Software Engineering Institute at Carnegie Mellon University. The model helps evaluating the software products in a standardized way, which contributes to improving the working processes and the quality of the product as a whole.

In fact all necessary sources of explicit declarative knowledge are available somewhere in the world repository. Is it enough for more effective and efficient software product development? Not, of course, simply because the access to those resources is difficult and time consuming especially when the developers need the information online. Recent Web technologies however offer solution of this problem through Web services and currently emerging cloud computing. This can be considered as a challenging research and implementation topics for knowledge-based support of software engineering.

Use of declarative structured knowledge (ontologies)

Ontology here is defined as declarative structured knowledge because it can be derived from the structural representation of concepts (entities, objects, classes) linked through existing or established relationships in a given problem domain. This is another interpretation of the definition of ontology as a specification of a representational vocabulary for a shared domain of discourse: definitions of classes, relations, functions, and other objects [START_REF] Gruber | Towards Principles for the Design of Ontologies Use for Knowledge Sharing[END_REF] or, more generally, a specification of conceptualization [START_REF] Dencho | Merging ontologies and object-oriented technologies for software development[END_REF]. In this section I will show as illustrative example how ontologies as form of knowledge can be used to support some of the most difficult phases of SDLC in object-oriented software engineering. The readers who would be interested in this example as complete representation can find more detailed description of respective models, methods and techniques in [START_REF] Dencho | Using Ontologies to Create Object Model for Object-Oriented Software Engineering, Chapter 16, Part 3[END_REF], [START_REF]A Practical Guide to Effective Requirements Development[END_REF].

The motto of classical object-oriented software development may be formulated in different ways, but its essence can be stated simply: "Identify and concentrate on objects in the problem domain description first. Think about the system function later." At the initial analysis phase, however, identifying the right objects, which are vital to the system's functionality, seems to be the most difficult task in the whole development process from both theoretical and practical point of view. Object-oriented software development is well supported by a huge number of working methods, techniques, and tools, except for this starting point -object identification and building the related system object model. Converting the text description of system problem domain and respective functional requirements into an object model is usually left to the intuition and experience of developers. One commonly accepted rule of thumb is, "If an object fits within the context of the system's responsibilities, then include it in the system." However, since the members of the development team are likely to have different views on many points, serious communication problems may occur during the later phases of the software development process. Here is the place where the knowledge represented by ontologies can help. It is worth noting that an ontology is either built already for a given problem domain or, if not, can be created using respective methods, techniques and tools (languages) specific for the field of ontology development, which is not objective of this paper. Fig. 2 illustrates the way in which ontology can be used as a supporting tool for the process of building the object model of the software system and converting its elements (objects) into abstract data types (ADTs). As far as the implementation of ADTs are classes and they are the basic building modules of object-oriented software, it becomes clear that actually the ontologies can help the entire analysis and design phases of SDLC. Models are inseparable and one of the most significant parts of any methodology. They help developers to better understand complex tasks and represent in a simpler way the work they should do to solve those tasks. Fig. 3 shows the models, which we use to transform requirements specification to object model of the system. The starting point of transformation is the text model (T-model), which represents a concise description of the problem domain, where the software system under development will work, written in a natural language, usually English. If not available, the T-model should be created by the developer describing the general user requirements for the system functionality. The presumption is that this problem domain description contains the main objects, which will participate in ensuring the system's functionality. Of course, at this level the objects are represented by their natural names only and as such are very far from the form we need to reach -represented as ADTs.

Ontology

Fig.3. Models for converting a text description into an object model

To help this process we refer to a tool of conceptualization -an ontological engine, which applied to the T-model, generates an ontology model (O-model) of the problem domain. The O-model is a straightforward and practically useful source of information for identifying the participating objects. We use this information to build a so-called Full Matrix model (MF-model), which represents in a simple form objects along with the linkages (relationships) between them. However, we should say that the processing of the MF-model is semi-formal in nature. This means that at this phase the developer should take important decisions about which objects could be considered as basic ADTs and which, and where, could play a role of attributes of other ADTs. The idea is simple but not very easy for implementation -to reduce the full object matrix to a reduced matrix (we call this model MRmodel), which contains only the basic objects represented later as ADTs containing other ADTs as attributes. The implementation is not very easy because we need more information here, which relates to expected functionality of participating objects. This information, however, is available or can be extracted from the Use Case model of the system under development. Note that at this phase we can also use the problem domain ontology. Along with showing the concepts hierarchy (possible objects in the system) the ontologies also analyze the verbs linking those concepts, which can be considered as functions (operations) belonging to respective objects. We actually use the text descriptions of different Use Cases to extract different functionality of the system by the ontological engine and as a result we get the so-called Use Case Ontological model (UO-model). The functionality, expressed by the UO-model, can be used at this phase along with the ontological information about the objects in the MF-model to create the Data and Function model (DF-model). As a matter of principle DF-model can be used for each of the objects in the DF-model but this would lead to a high degree of redundancy and quite complicated matrix presentation even for relatively simple Tmodels. To avoid this we propose to use so called business object patterns. The representation of the C-model is significantly different from MR-model however, as far as the former shows not only the object hierarchy but the objects' structure as well. In other words, the C-model is a model representing ADTs. The last model, the XML-model is optional but can be very important in practice because it allows the C-model to be published on the Web in a unified (XML-based) format supporting in this way the collaborative work, which is a commonly accepted technology nowadays.

The shown models and the process of their transformation can help developers of complex object-oriented software systems to: (a) transform user requirements (represented as text description) into an object model of the software system based on the use of ontologies; (b) improve the existing methods and techniques for creating a specific ontology from a text description of the system problem domain; (c) work out implementation techniques and tools for semi-automated or automated generating and editing of ADTs for object-oriented application software development, and (d) improve the effectiveness and efficiency of the existing methodology for high-level system analysis in object-oriented software engineering.

Use of tacit knowledge

For all phases of SDLC without any exceptions the developers are forced to make decisions, which are vital for the quality of the final product. Give one and the same user requirements and specifications to, let us say ten different teams, and you will get certainly ten absolutely different systems as result. Not different in required functionality but different as user acceptance, performance, cost, reliability, etc., generally speaking different in quality. This is not quite normal for other conventional products but for software the opposite would be not normal. This is the uniqueness of software product. And this is because the people who make decisions at some points of SDLC are different -as background, qualification, experience or as knowledge and skills in the field of software engineering. Practically most of this knowledge is tacit in nature -knowledge, which is hidden, difficult to express, explain, share with others and formalize. Tacit knowledge exists usually in two forms [START_REF] Marcus | CASSANDRA: An Automated Software Engineering Coach[END_REF]: (1) knowledge embodied in people and social networks, and (2) knowledge embedded in the processes and products that people create. We are interested here in the second form. Because the people develop and use tacit knowledge before they are able to formalize or codify it the problem is how to extract this knowledge from those who possess it and after that to represent and process it in a computerized environment in order to implicitly embed it in the software product. The artificial intelligence offers different representation schemes and respective methods and techniques for manipulating such type of knowledge but the most popular and relatively easy for implementation way remains the use of rule-based expert systems. Unfortunately, especially in the field of software engineering there are only a few examples of such systems, which are attempts to support some of the phases of SDLC. We used one of these examples -CASSANDRA to support the phase of requirements analysis and specification. This phase is one of the most difficult and ambiguous and at the same time of vital importance for the success of the project. As it is stated in [START_REF] Horvath | [END_REF] "Research indicates that nearly 50% of all software project defects originate in the requirements gathering process and that 60% to 80% of project failures can be attributed directly to poor requirements gathering." Obviously any guidance during this phase would be extremely useful.

CASSANDRA [15] is an ambitious project for developing an automated software engineering coach and the name stands for Cassandra -an Assistant for System Specification AND Requirements Analysis. The idea is the support to be in a style that resembles a human coach -proactive, asks the user questions, gives advices and recommendations and explains them in the case of users' request. Everything in CASSANDRA is implemented in Prologthe user interface, knowledge base, persistency and CASE tool access. Having the framework however, the contents of the inserted facts and questions asked can be easily changed, which allows for adjusting the expert system to the needs of different categories of users. We, for example, developed an expert tool for novice and junior developers with the idea to apply it to the educational process. In addition we changed completely the user interface implementing it in C# in .NET environment, which has connectivity to Prolog, giving in this way an opportunity for more attractive and convenient interaction between the user and system.

The architecture of CASSANDRA is quite complicated and it is not the aim of this paper to consider it in more details. The generation of recommendations however follows the classical mechanism of rule-based expert systems. All questions, facts and recommendations, which are the basic elements of knowledge base, are organized in functionally well-defined groups, such as goals of the system, system users, system constraints, system architecture, functionality definitions, design, performance, maintenance and support. Below are two examples of related fact and recommendation as illustration: fact (es1,no):-fact ('present software', no), recommend ('The fact that the company is not using any present software at the moment has both its advantages and its disadvantages. That is, you are going to be the first one who will try to find out all the needs of the company therefore more work should be done. On the other hand, it means that you have no competitor to compete with on the functionality of the software.'). recommendation (existing_software):-fact(es1,no), recommend ('You need to develop very careful strategies from which you will retrieve information about how the company is working and for what reason it needs the software for in order to be able to provide the best possible software solution for it. Some of those methods and techniques you can find out in the book of ....... on page ......').

The inference engine first calls the recommendation rule which on its turn calls the fact rule in order to be satisfied. The fact rule then starts the process to satisfy itself. That is, it starts calling all the facts that are included in its rule.

There are a good number of environments for development of rule-based expert systems. It seems to me however that the problem with having so small number of working examples of expert systems for support of software engineering is to find experts for different phases of SDLC ready for sharing their tacit knowledge. On the other hand the process of creating a solid knowledge base is costly and very time consuming. The decision maybe is the leading organizations in computing as IEEE and ACM to start coordinating this hard work as well as collaboration between universities and respective funding at national level.

Conclusion and recommendations

The long time existing ambiguity of the notion of software engineering is mainly due to the fact that it is based on and depends on knowledge. A new definition of the term is proposed in this paper, which states: "Software engineering is a systematic approach to the management and development of software systems based on use of all kinds of knowledge, which is embedded in the final software product". More specifically, three types of knowledge are identified as basic for support of developers' activities in software engineering: explicit declarative knowledge, which are unstructured in nature, ontologies as representatives of declarative structured knowledge and tacit knowledge. The main body of the paper is dedicated to illustrative examples of and respective comments on the use of each one of those kinds of knowledge in the education and practice of software engineering.

Using explicit declarative knowledge, accumulated and disseminated in form of collections of models, methods, techniques and tools, related books, papers, reports on good and bad practices, curricula, training and certification programs with respective teaching and learning materials, manuals, standards and so on, is still dominant. Nowadays Web technologies and more specifically Web services and currently emerging cloud computing can open new opportunities for more efficient and effective use of world repository in the field of software engineering. This can be considered as a challenging research and implementation topics for knowledge-based support of software engineering.

Most interesting, challenging and promising approach to knowledge-based support of practically all phases of SDLC is using ontologies. They either exist or can be created for different specific problem domains and offer good opportunities for merging with software engineering. The example shown and briefly discussed in the paper is dedicated to creating the object model of the software system from a given textual description of the problem domain and system functionality. It is expected more research to be carried out in this promising area.

Finally, an example of using tacit knowledge in an expert system serving as an automated coach in software engineering, and particularly in the requirement analysis phase, and built on the basis of CASSANDRA environment, is shown and discussed. Such type of expert systems could be very helpful for both education and practice in software engineering but their development requires collaborative work and availability of solid resources.

Fig. 1 .

 1 Fig.1. The Software Engineering Pyramid

Fig. 2 .

 2 Fig. 2. Ontologies and Building Object Model (ADT)

Acknowledgements. My thanks go to the hundreds of my students, who during the years have always inspired me to teach and supervise them better in the fields of software engineering and knowledge-based systems.