Journal Article Techniques for Genetic Software Architecture Design Get access Outi Sievi-Korte, Outi Sievi-Korte * 1Department of Pervasive Computing, Tampere University of Technology, Korkeakoulunkatu 1, P.O. Box 553, 33101 Tampere, Finland *Corresponding author: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Kai Koskimies, Kai Koskimies 1Department of Pervasive Computing, Tampere University of Technology, Korkeakoulunkatu 1, P.O. Box 553, 33101 Tampere, Finland Search for other works by this author on: Oxford Academic Google Scholar Erkki Mäkinen Erkki Mäkinen 2School of Information Sciences, University of Tampere, Kanslerinrinne 1, 33014 University of Tampere, Tampere, Finland Search for other works by this author on: Oxford Academic Google Scholar The Computer Journal, Volume 58, Issue 11, November 2015, Pages 3141–3170, https://doi.org/10.1093/comjnl/bxv049 Published: 14 July 2015 Article history Received: 01 December 2014 Revision received: 25 May 2015 Published: 14 July 2015

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as 𝒩𝒞 1 and 𝒜𝒞 1 , and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in U E * -uniform 𝒩𝒞 1 . Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in 𝒪(n log n) time and 𝒪(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in 𝒜𝒞 1 .

Techniques exist to synthesize software architecture using genetic algorithms that employ transformations based on mutations and crossover. In this paper, we demonstrate that complementary crossover can significantly improve this technique. We study two versions of complementary crossover, one in which parents are selected so that they complement each other but the genes are inherited randomly from the parents, and another in which the genes are inherited in a more purposeful way. Empirical studies on two sample systems suggest that the complementary crossover outperforms the traditional crossover in genetic software architecture synthesis especially in the presence of mutations that provide delayed reward.

Software architecture design can be regarded as finding an optimal combination of known general solutions and architectural knowledge with respect to given requirements. Based on previous work on synthesizing software architecture using genetic algorithms, we propose a refined fitness function for assessing software architecture in genetic synthesis, taking into account the specific anticipated needs of the software system under design. Inspired by real life architecture evaluation methods, the refined fitness function employs scenarios, specific situations possibly occurring during the lifetime of the system and requiring certain modifiability properties of the system. Empirical studies based on two example systems suggest that using this kind of fitness function significantly improves the quality of the resulting architecture.

A wireless ad hoc sensor network consists of a number of sensors spreading across a geographical area. The performance of the network suffers as the number of nodes grows, and a large sensor network quickly becomes difficult to manage. Thus, it is essential that the network be able to self-organize. Clustering is an efficient approach to simplify the network structure and to alleviate the scalability problem. One method to create clusters is to use weakly connected dominating sets (WCDSs). Finding the minimum WCDS in an arbitrary graph is an NP-complete problem. We propose a neural network model to find the minimum WCDS in a wireless sensor network. We present a directed convergence algorithm. The new algorithm outperforms the normal convergence algorithm both in efficiency and in the quality of solutions. Moreover, it is shown that the neural network is robust. We investigate the scalability of the neural network model by testing it on a range of sized graphs and on a range of transmission radii. Compared with Guha and Khuller's centralized algorithm, the proposed neural network with directed convergency achieves better results when the transmission radius is short, and equal performance when the transmission radius becomes larger. The parallel version of the neural network model takes time O(d), where d is the maximal degree in the graph corresponding to the sensor network, while the centralized algorithm takes O(n2). We also investigate the effect of the transmission radius on the size of WCDS. The results show that it is important to select a suitable transmission radius to make the network stable and to extend the lifespan of the network. The proposed model can be used on sink nodes in sensor networks, so that a sink node can inform the nodes to be a coordinator (clusterhead) in the WCDS obtained by the algorithm. Thus, the message overhead is O(M), where M is the size of the WCDS.

This paper empirically compares five linear-time algorithms for generating unbiased random binary trees. More specifically, we compare the relative asymptotic performance of the algorithms in terms of the numbers of various basic operations executed on average per tree node. Based on these numbers a ranking of the algorithms, which depends on the operation weights, can be deduced. A definitive ranking of the algorithms, however, hardly exists.

The Minimally Adequate Synthesizer (MAS) is an interactive algorithm that synthesizes UML statechart diagrams from sequence diagrams. It follows D. Angluin's (1987) framework of a minimally adequate teacher to infer the desired statechart diagram by consulting the user. To minimize the number of consultations needed, MAS keeps track of the interaction with the user. Together with its general knowledge about sequence diagrams, this makes MAS operate mostly without the user's help, but allowing him to guide the process at critical points. In this paper, we discuss the MAS algorithm and its practical implementation, integrated with a real-world UML modeling tool, the Nokia TDE ("The Design Environment"). Moreover, we discuss the interaction between the algorithm and the user as a medium for improving the algorithm and for further reducing the number of user consultations needed. Furthermore, we show how MAS can be used to incrementally synthesize sequence diagrams into an edited or a manually constructed statechart diagram. Totally automatic synthesis algorithms may result in a state machine that contains undesired generalizations. Because MAS consults the user during the synthesis process, the user can be confident that such generalizations do not appear in the resulting statechart diagram.

We (re-)introduce a Turing machine model for computer viruses. Despite the recent criticism of Turing machine models, they enjoy important advantages: their well-known notation and rich theory make them easy to understand and to elaborate. For many natural problems concerning computer viruses, e.g. for various decidability problems, Turing machine models provide a suitable platform of research.

Given a binary tree coding system, the set of valid code words of all binary trees can be considered as a context-free language over the alphabet used in the coding system. The complexity of the language obtained varies from one coding system to another. Xiang, Tang and Ushijima have recently proved some properties of such languages. We show that their results can be more easily proved by noticing the form of the generating grammar in question. Namely, in the simplest cases the language obtained is a left Szilard language, a very simple deterministic language. Moreover, we prove some new results concerning the ‘binary tree languages’.

We consider here some special forms of ambiguity for pure context-free grammars, namely pattern avoiding ambiguity, pattern preserving ambiguity, pattern ambiguity, and grammar avoiding ambiguity. The first two properties are undecidable for arbitrary pure context-free grammars, and in a particular but general enough case we can effectively decide whether or not a pure context-free grammar is pattern preserving ambiguous.

A Jumping Petri Net ([18], [12]), JPTN for short, is defined as a classical net which can spontaneously jump from a marking to another one. In [18] it has been shown that the reachability problem for JPTN's is undecidable, but it is decidable for finite JPTN's (FJPTN). In this paper we establish some specific properties and investigate the computational power of such nets, via the interleaving semantics. Thus, we show that the non-labelled JPTN's have the same computational power as the labelled or λ-labelled JPTN's. When final markings are considered, the power of JPTN's equals the power of Turing machines. The family of regular languages and the family of languages generated by JPTN's with finite state space are shown to be equal. Languages generated by FJPTN's can be represented in terms of regular languages and substitutions with classical Petri net languages. This characterization result leads to many important consequences, e.g. the recursiveness (context-sensitiveness, resp.) of languages generated by arbitrarily labelled (labelled, resp.) FJPTN's. A pumping lemma for nonterminal jumping net languages is also established. Finally, some comparisons between families of languages are given, and a connection between FJPTN's and a subclass of inhibitor nets is presented.

This note introduces subclasses of even linear languages for which there exist inference algorithms using positive samples only.

This note shows that it is undecidable whether or not an arbitrary context-free grammar is (0,l)-total, i.e., whether or not {0, 1} + ⊆ g(Szl(G)) holds for an arbitrary context-free grammar G, the left Szilard language Szl(G) of G, and a homomorphism g mapping the labels of G's productions into {0, 1} ∪ {λ}. These considerations are motivated by cryptosystems recently proposed by Andrasiu et al.

Abstract The automatic synthesis of state machines describing the behaviour of a class of objects in object‐oriented software modelling is studied. It is shown that the synthesis can be carried out on the basis of trace diagrams giving possible sequences of events during the execution of the system. An algorithm originally developed for the automatic construction of programs on the basis of their execution traces is applied to the problem, and an experimental state machine synthesizer is implemented. It is demonstrated that such a synthesizer is a highly useful component in a practical object‐oriented CASE system.

Several combinatorial and other programs deal with the structure (or the shape) of binary trees paying no attention to the data possibly maintained by the tree. For such programs it is useful to represent the structure without pointers and records. This paper surveys such representations. Especially, we concentrate on different ways of representing the structure of a binary tree by using a sequence of integers.

We discuss the implementation of two locally adaptive data compression methods, called the transpose and interval coding. It is found out that the implementations are extremely efficient compared to other similar methods. Moreover, errors are less catastrophic to these methods than to most adaptive compression schemes.