International Journal of Software Engineering and Knowledge Engineering

The unrelenting trend of larger and larger sizes of Software Systems and data has made software comprehensibility an increasingly difficult problem. However, a tacit consensus that human understanding of software is essential for most software related activities, stimulated software developers to embed comprehensibility in their systems’ design. On the other hand, recent empirical successes of Deep Learning neural networks, in several application areas, seem to challenge the tacit consensus: is software comprehensibility a necessity, or just superfluous? This introductory paper, to the 2020 special issue on Theoretical Software Engineering, offers reasons justifying our standpoint on the referred controversy. This paper also points out to specific techniques enabling Human Understanding of software systems relevant to this issue’s papers.

Well-designed software systems, with providers only modules, have been rigorously obtained by algebraic procedures from the software Laplacian Matrices or their respective Modularity Matrices. However, a complete view of the whole software system should display, besides provider relationships, also consumer relationships. Consumers may have two different roles in a system: either internal or external to modules. Composite modules, including both providers and internal consumers, are obtained from the joint providers and consumers Laplacian matrix, by the same spectral method which obtained providers only modules. The composite modules are integrated into a whole Software System by algebraic connectors. These algebraic connectors are a minimal Occam’s razor set of consumers external to composite modules, revealed through iterative splitting of the Laplacian matrix by Fiedler eigenvectors. The composite modules, of the respective standard Modularity Matrix for the whole software system, also obey linear independence of their constituent vectors, and display block-diagonality. The spectral method leading to composite modules and their algebraic connectors is illustrated by case studies. The essential novelty of this work resides in the minimal Occam’s razor set of algebraic connectors — another facet of Brooks’ Propriety principle leading to Conceptual Integrity of the whole Software System — within Linear Software Models, the unified algebraic theory of software modularity.

This paper introduces a mechanism to recover traceability links between the requirements and logical models in the context of critical systems development. Currently, lifecycle processes are covered by a good number of tools that are used to generate different types of artifacts. One of the cornerstone capabilities in the development of critical systems lies in the possibility of automatically recovery traceability links between system artifacts generated in different lifecycle stages. To do so, it is necessary to establish to what extent two or more of these work products are similar, dependent or should be explicitly linked together. However, the different types of artifacts and their internal representation depict a major challenge to unify how system artifacts are represented and, then, linked together. That is why, in this work, a concept-based representation is introduced to provide a semantic and unified description of any system artifact. Furthermore, a traceability function is defined and implemented to exploit this new semantic representation and to support the recovery of traceability links between different types of system artifacts. In order to evaluate the traceability function, a case study in the railway domain is conducted to compare the precision and recall of recovery traceability links between text-based requirements and logical model elements. As the main outcome of this work, the use of a concept-based paradigm to represent that system artifacts are demonstrated as a building block to automatically recover traceability links within the development lifecycle of critical systems.

This paper presents a novel method to infer regular expressions from positive examples. The method consists of a candidate’s construction phase and an optimization phase. We first propose multiscaling sample augmentation to capture the cycle patterns from single examples during the candidate’s construction phase. We then use common substrings to build regular expressions that capture patterns across multiple examples, and we show this algorithm is more general than those based on common prefixes or suffixes. Furthermore, we propose a pruning mechanism to improve the efficiency of useful common substring mining, which is an important part of common substring-based expression building algorithm. Finally, in the optimization phase, we model the problem of choosing a set of regular expressions with the lowest cost as an integer linear program, which can be solved to obtain the optimal solution. The experimental results on synthetic and real-life samples demonstrate the effectiveness of our approach in inferring concise and semantically meaningful regular expressions for string datasets.

The paper describes how to formally specify three path finding algorithms in Maude, a rewriting logic-based programming/specification language, and how to model check if they enjoy desired properties with the Maude LTL model checker. The three algorithms are Dijkstra Shortest Path Finding Algorithm (DA), A* Algorithm and LPA* Algorithm. One desired property is that the algorithms always find the shortest path. To this end, we use a path finding algorithm (BFS) based on breadth-first search. BFS finds all paths from a start node to a goal node and the set of all shortest paths is extracted. We check if the path found by each algorithm is included in the set of all shortest paths for the property. A* is an extension of DA in that for each node $n$ an estimation $\mathrm{\text{h}}(n)$ of the distance to the goal node from $n$ is used and LPA* is an incremental version of A*. It is known that if $\mathrm{\text{h}}$ is admissible, A* always finds the shortest path. We have found a possible relaxed sufficient condition. The relaxed condition is that there exists the shortest path such that for each node $n$ except for the start node on the path $\mathrm{\text{h}}(n)$ plus the cost to $n$ from the start node is less than the cost of any non-shortest path to the goal from the start. We informally justify the relaxed condition. For LPA*, if the relaxed condition holds in each updated version of a graph concerned including the initial graph, the shortest path is constructed. Based on the three case studies for DA, A* and LPA*, we summarize the formal specification and model checking techniques used as a generic approach to formal specification and model checking of path finding algorithms.

Access and reuse of authoritative phylogenetic knowledge have been a longstanding challenges in the evolutionary biology community — leading to a number of research efforts (e.g. focused on interoperation, standardization of formats, and development of minimum reporting requirements). The Phylotastic project was launched to provide an answer to such challenges — as an architectural concept collaboratively designed by evolutionary biologists and computer scientists. This paper describes the first comprehensive implementation of the Phylotastic architecture, based on an open platform for Web services composition. The implementation provides a portal, which composes Web services along a fixed collection of workflows, as well as an interface to allow users to develop novel workflows. The Web services composition is guided by automated planning algorithms and built on a Web services registry and an execution monitoring engine. The platform provides resilience through seamless automated recovery from failed services.

Because of rapid growth in mobile application markets, competition between companies that provide similar applications has become fierce. To improve user satisfaction for keeping existing users and attracting new users, application developers need to quickly respond to customer feedback regarding functionality and performance defects. In software engineering, specifying an accurate evolution plan according to user feedback is useful but quite difficult. Hence, we propose an approach for predicting and recommending evolution plans to application developers that includes: (1) when a new version of an App should be released; (2) which features should be updated in the next version and (3) if a new version is released, to what degree users would like or dislike it. This approach is based on an elaborate text analysis of massive numbers of user reviews and App update histories. A collocation-based mRAKE method is presented to extract requested and updated features from user reviews and update logs, and the intensity and sentiment scores of each feature are calculated to quantitatively represent time-series histories of App updates and user requests. Machine learning algorithms including linear support vector, Gaussian naïve Bayes and logistic regression are employed to discover the underlying correlation between user opinions embedded in their reviews and the App update behaviors of developers, and rich experiments were conducted on real data to validate the effectiveness of the proposed approach. Overall, our approach can achieve an average accuracy of 72.8% and 93.7% in release time recommendation and content updates of successive versions, respectively, and it can predict user reactions to a planned version with an average accuracy of above 89.0%.