Abstract In 2015, LearnLib, the open-source framework for active automata learning, received the prestigious CAV artifact award. This paper presents the advancements made since then, highlighting significant additions to LearnLib, including state-of-the-art algorithms, novel learning paradigms, and increasingly expressive models. Our efforts to mature and maintain LearnLib have resulted in its widespread use among researchers and practitioners alike. A key factor in its success is the achieved compositionality which allows users to effortlessly construct thousands of customized learning processes tailored to their specific requirements. This paper illustrates these features through the development of a learning process for the life-long learning of procedural systems. This development can be easily replicated and modified using the latest public release of LearnLib.

Abstract This paper illustrates the power of extending Language Driven Engineering (LDE) with Domain-Specific Natural Languages (DSNLs) through a case study on two levels. Both cases benefit from the characteristic decomposition feature of LDE, resulting in tasks tailored to the application of domain-specific languages, here with a focus on the application of DSNLs supported by LLM-based code generation. In the first case study, we show how DSNL-supported LDE facilitates the development of point-and-click adventures, whereas the second case study focuses on migration: We demonstrate how the entire LDE scenario for point-and-click adventure games can be migrated to output TypeScript instead of JavaScript using LLM-based code generation exclusively, without manually writing any code. This migration not only infers the required types, but also preserves an important property of the original LDE scenario: generated web applications can be automatically validated by design via automata learning and subsequent model checking. Even better, this property can be exploited to automatically validate the correctness of the migration by learning so-called difference automata that characterize the behavioral differences between the generated JavaScript-based and Type-Script-based applications.

Compilers use a wide range of advanced optimizations to improve the quality of the machine code they generate. In most cases, compiler optimizations rely on precise analyses to be able to perform the optimizations. However, whenever a control-flow merge is performed information is lost as it is not possible to precisely reason about the program anymore. One existing solution to this issue is code duplication, which involves duplicating instructions from merge blocks to their predecessors. This paper introduces a novel and more aggressive approach to code duplication, grounded in loop unrolling and control-flow unmerging that enables subsequent optimizations that cannot be enabled by applying only one of these transformations. We implemented our approach inside LLVM, and evaluated its performance on a collection of GPU benchmarks in CUDA. Our results demonstrate that, even when faced with branch divergence, which complicates code duplication across multiple branches and increases the associated cost, our optimization technique achieves performance improvements of up to 81%.

Abstract Random Forests are one of the most popular classifiers in machine learning. The larger they are, the more precise the outcome of their predictions. However, this comes at a cost: it is increasingly difficult to understand why a Random Forest made a specific choice, and its running time for classification grows linearly with the size (number of trees). In this paper, we propose a method to aggregate large Random Forests into a single, semantically equivalent decision diagram which has the following two effects: (1) minimal, sufficient explanations for Random Forest-based classifications can be obtained by means of a simple three step reduction, and (2) the running time is radically improved. In fact, our experiments on various popular datasets show speed-ups of several orders of magnitude, while, at the same time, also significantly reducing the size of the required data structure.

Abstract In this paper, we present the envisioned style and scope of the new topic “Explanation Paradigms Leveraging Analytic Intuition” (ExPLAIn) with the International Journal on Software Tools for Technology Transfer (STTT). Intention behind this new topic is to (1) explicitly address all aspects and issues that arise when trying to, if possible, reveal and then confirm hidden properties of black-box systems, or (2) to enforce vital properties by embedding them into appropriate system contexts. Machine-learned systems, such as Deep Neural Networks, are particularly challenging black-box systems, and there is a wealth of formal methods for analysis and verification waiting to be adapted and applied. The selection of papers of this first Special Section of ExPLAIn, most of which were co-authored by editorial board members, is an illustrative example of the style and scope envisioned: In addition to methodological papers on verification, explanation, and their scalability, case studies, tool papers, literature reviews, and position papers are also welcome.

Abstract In this paper, we present Forest GUMP (for Generalized, Unifying Merge Process) a tool for verification and precise explanation of Random forests. Besides pre/post-condition-based verification and equivalence checking, Forest GUMP also supports three concepts of explanation, the well-known model explanation and outcome explanation, as well as class characterization, i.e., the precise characterization of all samples that are equally classified. Key technology to achieve these results is algebraic aggregation, i.e., the transformation of a Random Forest into a semantically equivalent, concise white-box representation in terms of Algebraic Decision Diagrams (ADDs). The paper sketches the method and demonstrates the use of Forest GUMP along illustrative examples. This way readers should acquire an intuition about the tool, and the way how it should be used to increase the understanding not only of the considered dataset, but also of the character of Random Forests and the ADD technology, here enriched to comprise infeasible path elimination. As Forest GUMP is publicly available all experiments can be reproduced, modified, and complemented using any dataset that is available in the ARFF format.

Abstract TADS are a novel, concise white-box representation of neural networks. In this paper, we apply TADS to the problem of neural network verification, using them to generate either proofs or concise error characterizations for desirable neural network properties. In a case study, we consider the robustness of neural networks to adversarial attacks, i.e., small changes to an input that drastically change a neural networks perception, and show that TADS can be used to provide precise diagnostics on how and where robustness errors a occur. We achieve these results by introducing Precondition Projection, a technique that yields a TADS describing network behavior precisely on a given subset of its input space, and combining it with PCA, a traditional, well-understood dimensionality reduction technique. We show that PCA is easily compatible with TADS. All analyses can be implemented in a straightforward fashion using the rich algebraic properties of TADS, demonstrating the utility of the TADS framework for neural network explainability and verification. While TADS do not yet scale as efficiently as state-of-the-art neural network verifiers, we show that, using PCA-based simplifications, they can still scale to medium-sized problems and yield concise explanations for potential errors that can be used for other purposes such as debugging a network or generating new training samples.

Abstract In this paper, we present an algebraic approach to the precise and global verification and explanation of Rectifier Neural Networks , a subclass of Piece-wise Linear Neural Networks (PLNNs), i.e., networks that semantically represent piece-wise affine functions. Key to our approach is the symbolic execution of these networks that allows the construction of semantically equivalent Typed Affine Decision Structures (TADS). Due to their deterministic and sequential nature, TADS can, similarly to decision trees, be considered as white-box models and therefore as precise solutions to the model and outcome explanation problem. TADS are linear algebras, which allows one to elegantly compare Rectifier Networks for equivalence or similarity, both with precise diagnostic information in case of failure, and to characterize their classification potential by precisely characterizing the set of inputs that are specifically classified, or the set of inputs where two network-based classifiers differ. All phenomena are illustrated along a detailed discussion of a minimal, illustrative example: the continuous XOR function.

Abstract In this paper, we present Forest GUMP (for Generalized, Unifying Merge Process) a tool for providing tangible experience with three concepts of explanation. Besides the well-known model explanation and outcome explanation, Forest GUMP also supports class characterization, i.e., the precise characterization of all samples with the same classification. Key technology to achieve these results is algebraic aggregation, i.e., the transformation of a Random Forest into a semantically equivalent, concise white-box representation in terms of Algebraic Decision Diagrams (ADDs). The paper sketches the method and illustrates the use of Forest GUMP along an illustrative example taken from the literature. This way readers should acquire an intuition about the tool, and the way how it should be used to increase the understanding not only of the considered dataset, but also of the character of Random Forests and the ADD technology, here enriched to comprise infeasible path elimination.

Abstract This is the second issue in the new “Competitions and Challenges” (CoCha) theme of the International Journal on Software Tools for Technology Transfer. The new theme was established to support competitions and challenges with an appropriate publication venue. The first issue presented the competition on software testing Test-Comp 2019, which was part of the TOOLympics 2019 event. In this second issue for TOOLympics, we present selected competition reports. The TOOLympics event took place as part of the 25-years celebration of the conference TACAS. The goal of the event was to provide an overview of competitions and challenges in the area of formal methods.

Abstract This paper presents a compositional approach to active automata learning of Systems of Procedural Automata (SPAs), an extension of Deterministic Finite Automata (DFAs) to systems of DFAs that can mutually call each other. SPAs are of high practical relevance, as they allow one to efficiently learn intuitive recursive models of recursive programs after an easy instrumentation that makes calls and returns observable. Key to our approach is the simultaneous inference of individual DFAs for each of the involved procedures via expansion and projection: membership queries for the individual DFAs are expanded to membership queries of the entire SPA, and global counterexample traces are transformed into counterexamples for the DFAs of concerned procedures. This reduces the inference of SPAs to a simultaneous inference of the DFAs for the involved procedures for which we can utilize various existing regular learning algorithms. The inferred models are easy to understand and allow for an intuitive display of the procedural system under learning that reveals its recursive structure. We implemented the algorithm within the LearnLib framework in order to provide a ready-to-use tool for practical application which is publicly available on GitHub for experimentation.

Abstract This paper (1) summarizes the history of the RERS challenge for the analysis and verification of reactive systems, its profile and intentions, its relation to other competitions, and, in particular, its evolution due to the feedback of participants, and (2) presents the most recent development concerning the synthesis of hard benchmark problems. In particular, the second part proposes a way to tailor benchmarks according to the depths to which programs have to be investigated in order to find all errors. This gives benchmark designers a method to challenge contributors that try to perform well by excessive guessing.

Abstract This paper proposes a simplicity-oriented approach and framework for language-to-language transformation of, in particular, graphical languages. Key to simplicity is the decomposition of the transformation specification into sub-rule systems that separately specify purpose-specific aspects. We illustrate this approach by employing a variation of Plotkin’s Structural Operational Semantics (SOS) for pattern-based transformations of typed graphs in order to address the aspect ‘computation’ in a graph rewriting fashion. Key to our approach are two generalizations of Plotkin’s structural rules: the use of graph patterns as the matching concept in the rules, and the introduction of node and edge types. Types do not only allow one to easily distinguish between different kinds of dependencies, like control, data, and priority, but may also be used to define a hierarchical layering structure. The resulting Type-based Structural Operational Semantics (TSOS) supports a well-structured and intuitive specification and realization of semantically involved language-to-language transformations adequate for the generation of purpose-specific views or input formats for certain tools, like, e.g., model checkers. A comparison with the general-purpose transformation frameworks ATL and Groove, illustrates along the educational setting of our graphical WebStory language that TSOS provides quite a flexible format for the definition of a family of purpose-specific transformation languages that are easy to use and come with clear guarantees.

Abstract In this paper, we prove that Hennessy–Milner Logic (HML), despite its structural limitations, is sufficiently expressive to specify an initial property $$\varphi _0$$ φ0 and a characteristic invariant $$\upchi _{_I}$$ χI for an arbitrary finite-state process P such that $$\varphi _0 \wedge \mathbf{AG }(\upchi _{_I})$$ φ0∧AG(χI) is a characteristic formula for P. This means that a process Q, even if infinite state, is bisimulation equivalent to P iff $$Q \models \varphi _0 \wedge \mathbf{AG }(\upchi _{_I})$$ Q⊧φ0∧AG(χI) . It follows, in particular, that it is sufficient to check an HML formula for each state of a finite-state process to verify that it is bisimulation equivalent to P. In addition, more complex systems such as context-free processes can be checked for bisimulation equivalence with P using corresponding model checking algorithms. Our characteristic invariant is based on so called class-distinguishing formulas that identify bisimulation equivalence classes in P and which are expressed in HML. We extend Kanellakis and Smolka’s partition refinement algorithm for bisimulation checking in order to generate concise class-distinguishing formulas for finite-state processes.

We present Pyro, a framework for enabling domain-specific modeling via the internet. Provided with an adequate metamodel specification, Pyro turns your browser into a collaborative, domain-specific, graphical development environment with features reminiscent of desktop IDEs for textual programming languages. The required metamodeling is supported in a high-level, simplicity-driven fashion, and the entire ready-to-run browser-based domain-specific development environment is generated fully automatically. We will illustrate the steps of this development along the realization of a graphical IDE for the Architecture Analysis and Design Language (AADL).

Evaluation of scientific contributions can be done in many different ways. For the various research communities working on the verification of systems (software, hardware, or the underlying involved mechanisms), it is important to bring together the community and to compare the state of the art, in order to identify progress of and new challenges in the research area. Competitions are a suitable way to do that. The first verification competition was created in 1992 (SAT competition), shortly followed by the CASC competition in 1996. Since the year 2000, the number of dedicated verification competitions is steadily increasing. Many of these events now happen regularly, gathering researchers that would like to understand how well their research prototypes work in practice. Scientific results have to be reproducible, and powerful computers are becoming cheaper and cheaper, thus, these competitions are becoming an important means for advancing research in verification technology. TOOLympics 2019 is an event to celebrate the achievements of the various competitions, and to understand their commonalities and differences. This volume is dedicated to the presentation of the 16 competitions that joined TOOLympics as part of the celebration of the $$25^{ th }$$ anniversary of the TACAS conference.

This paper covers the Rigorous Examination of Reactive Systems (RERS) Challenge 2019. For the first time in the history of RERS, the challenge features industrial tracks where benchmark programs that participants need to analyze are synthesized from real-world models. These new tracks comprise LTL, CTL, and Reachability properties. In addition, we have further improved our benchmark generation infrastructure for parallel programs towards a full automation. RERS 2019 is part of TOOLympics, an event that hosts several popular challenges and competitions. In this paper, we highlight the newly added industrial tracks and our changes in response to the discussions at and results of the last RERS Challenge in Cyprus.

RERS is an annual verification challenge that focuses on LTL and reachability properties of reactive systems. In 2017, RERS was extended to a one day workshop that in addition to the original challenge program also featured an invited talk about possible future developments. As a satellite of ISSTA and SPIN, the 2017 RERS Challenge itself increased emphasis on the parallel benchmark problems which, like their sequential counterparts, were generated using property-preserving transformations in order to scale their level of difficulty. The first half of the RERS workshop focused on the 2017 benchmark profiles, the evaluation of the received contributions, and short presentations of each participating team. The second half comprised discussions about attractive problem scenarios for future benchmarks, like race detection, the topic of the invited talk, and about systematic ways to leverage a tool's performance based on competition benchmarks and machine learning.

Abstract We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata . Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory , i.e., a set of operations and tests on the data domain that can be used in guards. Key to our learning technique is a novel learning model based on so-called tree queries . The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.

In this paper, we sketch how treating product lines as systems of possibly heterogeneous constraints allows one to elegantly and consistently manage product lines in terms of a product line of product lines. In fact, as will also be illustrated along our example scenarios, this leads to a framework for a consistent division of labour in an "easy for the many difficult for the few" fashion which supports correctness by construction. Central for this approach are our powerful model-based synthesis and code generation technologies, which turn systems of constraints into executable models or target code.

SUMMARY In this article, we present our experience with over a decade of strict simplicity orientation in the development and evolution of plug‐ins. The point of our approach is to enable our graphical modeling framework jABC to capture plug‐in development in a domain‐specific setting. The typically quite tedious and technical plug‐in development is shifted this way from a programming task to the modeling level, where it can be mastered also by application experts without programming expertise. We show how the classical plug‐in development profits from a systematic domain‐specific API design and how the level of abstraction achieved this way can be further enhanced by defining adequate building blocks for high‐level plug‐in modeling. As the resulting plug‐in models can be compiled and deployed automatically, our approach decomposes plug‐in development into three phases where only the realization phase requires plug‐in‐specific effort. By using our modeling framework jABC, this effort boils down to graphical, tool‐supported process modeling. Furthermore, we support the automatic completion of process sketches for executability. All this will be illustrated along the most recent plug‐in‐based evolution of the jABC framework, which witnessed quite some bootstrapping effects. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, we evaluate and categorize how five representative, Java-based, state-of-the-art business process management systems, namely jBPM (4.x and 5.x), Activiti, AristaFlow and jABC, realize the integration of services. In particular, we show that the use of domain specific business activities is the currently most sophisticated technique for integrating services in business processes, and describe what they consist of, how they are created, how they can be organized and how they are used. This sheds light on the corresponding state-of-the-art, and shows that, in particular the supposedly big players, have quite some room for improvement.

This paper shows how the reflexivity of Ecore can be exploited for incrementally bootstrapping domain-specific code generators in the model-driven and service-oriented code generation framework Genesys. Key to this technology is the EMF SIB Generator, which, based on a very small set of manually written code generator services called SIBs, incrementally generates services in a bootstrapping fashion. To this end, it leverages Ecore's metamodel, which is specified in Ecore itself, to iteratively enlarge the set of SIBs until all concepts of Ecore are covered. On this basis, the EMF SIB Generator can then be used to generate all services required for constructing a corresponding code generator for any given metamodel specified in Ecore. This approach can be staightforwardly applied to arbitrary metalevels and elegantly enables the model-driven and service-oriented construction of code generators for Ecore-based domain-specific languages.

In this paper, we leverage service-orientation as a means for combining the strengths of the UML-based code generator framework AndroMDA for generating static application aspects with code generators focussing on the dynamic aspects. The latter are developed with Genesys, a code generation framework that combines the ideas of model-driven development and service-orientation in order to enable a high-level engineering of code generators. This demonstrates a new level of reusability and even has the potential for full code generation, which elegantly eliminates the need for the typical round-trip engineering in model-driven development environments. We demonstrate the applicability of our approach by means of an example from the field of bioinformatics.

PROPHETS is our flexible framework for the synthesis of processes from libraries of basic services. In this paper we demonstrate how its synthesis strategy can be tailored to the considered application domain. For this purpose, PROPHETS provides a number of configuration options, such as different data exchange formats (e.g. shared variables and pipe lining) for the resulting process, as well as structural and temporal logic constraints for minimizing the inherent search space. We illustrate the impact of adequate synthesis tailoring by contrasting two real-life case studies with diametric characteristics.

This paper systematically evaluates four different APIs provided by popular ERP systems (SAP BAPI, SAP eSOA, Microsoft Dynamics NAV and Intuit Quick books) according to their potential for service-oriented enterprise application integration. Central is here the quality of access to and control of their business objects for developing complex business processes in a service oriented landscape. In an ideal world this development should be directly in the hands of the application/business experts, and thus be possible without coding. This can only work if the technical APIs can (semi-) automatically be bridged to a level an application expert can master, which leads to additional API requirements. Our evaluation reveals that the currently still quite unsatisfactory quality of the APIs very much reflects the business profile of each ERP solution. We are therefore convinced that, with changing market conditions, future ERP solutions will live up to the identified requirements.

Leading goal for the EU-project ITSy is to explore the power of simplicity for achieving robustness, flexibility and trust. A number of scenarios have been investigated in this direction, comprising looking at different notions of complexity, in particular distinguishing the actual complexity, the objective notion of complexity associated with a task as such, from the felt complexity, the subjective notion of complexity associated with the difficulty for some person satisfy his personal task. Division of labor is the typical way of decomposing the actual complexity in manageable or small piece of felt complexity. Or in other words, standing on the shoulder of giants we may reach impressive goals. A completely different way to achieve simplicity is to change the rules of the game. A good example here is the change from object tracking via image recognition to RFID-based object tracking. Whereas the former is intrinsically difficult, the latter, much simpler solution much better serves the purpose. In this session we consider three scenarios which propose such a change of perspective.

In this paper we present a novel approach to the test-based validation of complex heterogeneous applications which is tailored to simplify the requirements for the responsible personnel. Key to our approach is to automate the corresponding testing procedure by means of active automata learning. This replaces typical prerequisites like manual test construction or the provision of adequate test models by the definition of an adequate learning alphabet. In practice this typically means by providing representative data for the parameters of the relevant API calls. Besides its simplicity this approach also guarantees that the testing procedure automatically adapts to system modifications, which makes it an ideal tool for dealing with evolving systems of unknown emergent behaviour, as will be illlustrated along the Online Conference System (OCS), a model-driven and service-oriented online conference manuscript submission and review system.

Abstract Automatic code generation is an essential cornerstone of today’s model-driven approaches to software engineering. Thus a key requirement for the success of this technique is the reliability and correctness of code generators. This article describes how we employ standard model checking-based verification to check that code generator models developed within our code generation framework Genesys conform to (temporal) properties. Genesys is a graphical framework for the high-level construction of code generators on the basis of an extensible library of well-defined building blocks along the lines of the Extreme Model-Driven Development paradigm. We will illustrate our verification approach by examining complex constraints for code generators, which even span entire model hierarchies. We also show how this leads to a knowledge base of rules for code generators, which we constantly extend by e.g. combining constraints to bigger constraints, or by deriving common patterns from structurally similar constraints. In our experience, the development of code generators with Genesys boils down to re-instantiating patterns or slightly modifying the graphical process model, activities which are strongly supported by verification facilities presented in this article.

The CONNECT European project that started in February 2009 aims at dropping the interoperability barrier faced by todaypsilas distributed systems. It does so by adopting a revolutionary approach to the seamless networking of digital systems, that is, synthesizing on the fly the connectors via which networked systems communicate. CONNECT then investigates formal foundations for connectors together with associated automated support for learning, reasoning about and adapting the interaction behavior of networked systems.

Bio-jETI is a framework for model-based, graphical development and execution of bioinformatics analysis processes. With the GeneSys code generation framework we can automatically compile the workflow models into native, stand-alone program code. We show via a phylogenetic analysis workflow designed by the DNA Data Bank of Japan (DDBJ) how we generate 6 variants of Java code from the corresponding process model realized in Bio-jETI. Performance measurements show that 1) the overall workflow execution time is dominated by the remote services it uses, and thus 2)all 6 variants are almost as fast as the handwritten Java of DDBJ. This way, we obtain efficient native code essentially without program- ming. Thus, we demonstrate in this paper that model- based workflow development in Bio-jETI offers several advantages over manual implementation – including higher agility, greater transparency and better maintainability – without compromising the runtime performance.

Agility is a must, in particular for business applications. Complex systems and processes must be continuously updated in order to meet the ever changing market conditions. Continuous Model Driven Engineering is based on our eXtreme Model-Driven Design (XMDD) framework, which has been designed to continuously involve the customer/application expert throughout the whole systems' life cycle including software maintenance and evolution. Conceptually it is based on the One Thing Approach (OTA), which combines the simplicity of the waterfall development paradigm with a maximum of agility. The key to OTA is to view the whole development process simply as a complex hierarchical and interactive decision process, where each stakeholder, including the application expert, is allowed to continuously place his/her decisions in term of constraints. Thus semantically, at any time, the state of the development or evolution process can simply be regarded as the current set of constraints, and each development or evolution step can be regarded simply as a transformation of this very constraint set. This approach, conceptually, allows one 1) to monitor globally and at any time the consistency of the development or evolution process simply via constraint checking, and 2) to impose a kind of decision hierarchy by mapping areas of competencies to roles of individuals, in order to identify required actions in case of constraint violation. The essence and power of this approach, which is technically supported by the jABC development and execution framework, will be illustrated along a number of real life application.

Service orientation leads to a completely new understanding and a much more end-user oriented tailoring of software design. We advocate a new software development paradigm: eXtreme Model-Driven Design (XMDD), designed to continuously involve the customer/application expert throughout the whole system's life cycle, including development and software maintenance. As maintenance is predominantly an adaption to new user requirements or to other global conditions, empowering the application expert would change the scene: Customer/application experts could rapidly adapt the system to their changing requirements. Source code becomes "only" a by-product and the development focuses on the model level. This paper presents a new development paradigm which realizes these ideas.

BACKGROUND: The development of bioinformatics databases, algorithms, and tools throughout the last years has lead to a highly distributed world of bioinformatics services. Without adequate management and development support, in silico researchers are hardly able to exploit the potential of building complex, specialized analysis processes from these services. The Semantic Web aims at thoroughly equipping individual data and services with machine-processable meta-information, while workflow systems support the construction of service compositions. However, even in this combination, in silico researchers currently would have to deal manually with the service interfaces, the adequacy of the semantic annotations, type incompatibilities, and the consistency of service compositions. RESULTS: In this paper, we demonstrate by means of two examples how Semantic Web technology together with an adequate domain modelling frees in silico researchers from dealing with interfaces, types, and inconsistencies. In Bio-jETI, bioinformatics services can be graphically combined to complex services without worrying about details of their interfaces or about type mismatches of the composition. These issues are taken care of at the semantic level by Bio-jETI's model checking and synthesis features. Whenever possible, they automatically resolve type mismatches in the considered service setting. Otherwise, they graphically indicate impossible/incorrect service combinations. In the latter case, the workflow developer may either modify his service composition using semantically similar services, or ask for help in developing the missing mediator that correctly bridges the detected type gap. Newly developed mediators should then be adequately annotated semantically, and added to the service library for later reuse in similar situations. CONCLUSION: We show the power of semantic annotations in an adequately modelled and semantically enabled domain setting. Using model checking and synthesis methods, users may orchestrate complex processes from a wealth of heterogeneous services without worrying about interfaces and (type) consistency. The success of this method strongly depends on a careful semantic annotation of the provided services and on its consequent exploitation for analysis, validation, and synthesis. We are convinced that these annotations will become standard, as they will become preconditions for the success and widespread use of (preferred) services in the Semantic Web.

BACKGROUND: PCR primer design is an everyday, but not trivial task requiring state-of-the-art software. We describe the popular tool GeneFisher and explain its recent restructuring using workflow techniques. We apply a service-oriented approach to model and implement GeneFisher-P, a process-based version of the GeneFisher web application, as a part of the Bio-jETI platform for service modeling and execution. We show how to introduce a flexible process layer to meet the growing demand for improved user-friendliness and flexibility. RESULTS: Within Bio-jETI, we model the process using the jABC framework, a mature model-driven, service-oriented process definition platform. We encapsulate remote legacy tools and integrate web services using jETI, an extension of the jABC for seamless integration of remote resources as basic services, ready to be used in the process. Some of the basic services used by GeneFisher are in fact already provided as individual web services at BiBiServ and can be directly accessed. Others are legacy programs, and are made available to Bio-jETI via the jETI technology. The full power of service-based process orientation is required when more bioinformatics tools, available as web services or via jETI, lead to easy extensions or variations of the basic process. This concerns for instance variations of data retrieval or alignment tools as provided by the European Bioinformatics Institute (EBI). CONCLUSIONS: The resulting service- and process-oriented GeneFisher-P demonstrates how basic services from heterogeneous sources can be easily orchestrated in the Bio-jETI platform and lead to a flexible family of specialized processes tailored to specific tasks.

BACKGROUND: With Bio-jETI, we introduce a service platform for interdisciplinary work on biological application domains and illustrate its use in a concrete application concerning statistical data processing in R and xcms for an LC/MS analysis of FAAH gene knockout. METHODS: Bio-jETI uses the jABC environment for service-oriented modeling and design as a graphical process modeling tool and the jETI service integration technology for remote tool execution. CONCLUSIONS: As a service definition and provisioning platform, Bio-jETI has the potential to become a core technology in interdisciplinary service orchestration and technology transfer. Domain experts, like biologists not trained in computer science, directly define complex service orchestrations as process models and use efficient and complex bioinformatics tools in a simple and intuitive way.

The FMICS-jETI platform is a collaborative, service- based demonstrator of tools and techniques for the analysis of industrial critical systems. It is the FMICS Working Group contribution to the Verified Software Initiative. In this paper, we extend the scope of the FMICS-jETI platform to address the integration of heterogeneous and legacy tools and technologies. We show how to integrate 1) CORBA, a language independent standard for the inter-operability of heterogeneous functionalities distributed over a network, 2) active model learning technologies, via the LearnLib, as a model extrapolation technique that uses testing to explore a black box system and CORBA as a communication mechanism, and 3) third party applications built on top of the LearnLib, in this case Smyle, a tool that synthesizes design models by learning from examples, that uses the LearnLib as learner core.

In this paper we present the FormulaBuilder, a flexible tool for graph-based modelling and generation of formulae. The FormulaBuilder allows easy and intuitive creation of formulae by using basic components called Formula Building Blocks (FBBs) and arranging them as graphs according to the syntactic structure of a formula. Such a graph can then be validated and used to generate the corresponding formula on the basis of a specific syntax which is chosen from a list of syntaxes supported by the FormulaBuilder.An important application of the FormulaBuilder is the formal specification of properties that describe the requirements of a system. Such property specifications are usually needed by verification tools like model checkers, that help software engineers to detect errors in a specified system. The FormulaBuilder allows users to model property specifications as formula graphs by using commonly-occurring specification patterns.

In today's business the availability of services is of central importance. To guarantee a higher availability of a service, like a Web-service, it can be installed on several machines, which are running in a hot-standby operation. In case of a fault one hot-standby service can take over the work of the faulty service. Novel to our approach is that this kind of redundancy can be applied to services, that normally do not support service availability concepts. The switching of one machine running in hot-standby mode to active can be done from an external system monitoring the service. MaTRICS is an architecture that allows the configuration of any service provided by a specific server. The specification is done by service logic graphs, which can be validated by model checking.

LC/MS is a successful analysis technique for the statistical analysis used in several branches of biology. It requires an intense screening and combination of the raw data, which is usually done with programs and libraries invoked by scripts in the domain-specific statistics language S or R. We show here how to model and implement this complex workflow in a service-oriented fashion, using the jABC service definition environment and jETI for remote service integration and execution.

One of the goals of FMICS, the ERCIM Working Group on Formal Methods for Industrial Critical Systems (FMICS) [8], is to transfer and promote the use formal methods technology in industry. The ongoing Verified Software Repository Grand Challenge [11] offers a great opportunity to reach this goal, resulting in a more robust and solid software industry in Europe. We demonstrate here the current status of the FMICS-jETIplatform1, a collaborative demonstrator based on the jETI technology2, that provides as repository a collection of verification tools stemming from the activities of the FMICS working group and facilities to orchestrate them in a remote and simple way. At the same time FMICS-jETI itself is a contribution to the VSR repository and thus to the Grand Challenge.

Summary form only given. Service-oriented design has long driven the development of the telecommunications infrastructure and applications, especially intelligent network services. Applying the same principles of domain specificity, virtualization, loose coupling, and seamless vertical integration to business processes has the potential to lead to a new generation of personalized, secure, and highly available Web services

In this paper we present the LearnLib, a library for automata learning and experimentation. Its modular structure allows users to configure their tailored learning scenarios, which exploit specific properties of the envisioned applications. As has been shown earlier, exploiting application-specific structural features enables optimizations that may lead to performance gains of several orders of magnitude, a necessary precondition to make automata learning applicable to realistic scenarios.

Test-based model generation by classical automata learning is very expensive. It requires an impractically large number of queries to the system, each of which must be implemented as a system-level test case. Key towards the tractability of observation based model generation are powerful optimizations exploiting different kinds of expert knowledge in order to drastically reduce the number of required queries, and thus the testing effort. In this paper, we present a thorough experimental analysis of the second-order effects between such optimizations in order to maximize their combined impact

We propose a framework for top-down Web service interoperation based on an aggressive version of model-driven development (AMDD). The point here is to govern the construction and customization of complex Web applications at the model level in a framework that allows application experts to directly formulate their desires in an adequate way. Adequate means in this context that applications can be automatically validated, executed, tested, and deployed by the application experts, inside a framework that takes care also of second-order concerns. Our approach, which focuses on functionalities as the basic entities of the design space is tailored to make second order issues like interoperation, distribution, and compatibility simple for the many, difficult for the few: simple for the many, as the advocated approach hides most of the intricate second-order issues from the application designer, and difficult for the few, as these issues must be dealt with by means of complex compilation, synthesis or technology mappings. Our experience indicates that this approach has the potential to cover and thereby drastically simplify the bulk of modern Web application development and customization

We study the extension of applicability of system-level testing techniques to the construction of a consistent model of (legacy) systems under test, which are seen as black boxes. We gather observations via an automated test environment and systematically extend available test suites according to learning procedures. Testing plays two roles here: (i) as an application domain and (ii) as the enabling technology for the adopted learning technique. The benefits include enhanced error detection and diagnosis, both during the testing phase and the online test of deployed systems at customer sites. 1

In this article, we add a third dimension to partial redundancy elimination by considering code size as a further optimization goal in addition to the more classical consideration of computation costs and register pressure. This results in a family of sparse code motion algorithms coming as modular extensions of the algorithms for busy and lazy code motion. Each of them optimally captures a predefined choice of priority between these three optimization goals, e.g. code size can be minimized while (1) guaranteeing at least the performance of the argument program, or (2) even computational optimality. Each of them can further be refined to simultaneously reduce the lifetimes of temporaries to a minimum. These algorithms are well-suited for size-critical application areas like smart cards and embedded systems, as they provide a handle to control the code replication problem of classical code motion techniques. In fact, we believe that our systematic, priority-based treatment of trade-offs between optimization goals may substantially decrease development costs of size-critical applications: users may “play” with the priorities until the algorithm automatically delivers a satisfactory solution.

In comparison to automatic parallelization, which is thoroughly studied in the literature [31, 33], classical analyses and optimizations of explicitly parallel programs were more or less neglected. This may be due to the fact that naive adaptations of the sequential techniques fail [24], and their straightforward correct ones have unacceptable costs caused by the interleavings, which manifest the possible executions of a parallel program. Recently, however, we showed that unidirectional bitvector analyses can be performed for parallel programs as easily and as efficiently as for sequential ones [17], a necessary condition for the successful transfer of the classical optimizations to the parallel setting.In this article we focus on possible subsequent code motion transformations, which turn out to require much more care than originally conjectured [17]. Essentially, this is due to the fact that interleaving semantics, although being adequate for correctness considerations, fails when it comes to reasoning about efficiency of parallel programs. This deficiency, however, can be overcome by strengthening the specific treatment of synchronization points.

Abstract We present a method for thecompositional constructionof theminimal transition systemthat represents the semantics of a given distributed system. Our aim is to control thestate explosioncaused by the interleavings of actions of communicating parallel components byreduction stepsthat exploitglobalcommunication constraints given in terms ofinterface specifications.Theeffectof the method, which is developed forbisimulation semanticshere, depends on the structure of the distributed system under consideration, and theaccuracyof the interface specifications. However, itscorrectnessis independent of the correctness of the interface specifications provided by the program designer.

Abstract We extend the stratified model of probabilistic processes to obtain a very general notion of process priority. The main idea is to allow probability guards of value 0 to be associated with alternatives of a probabilistic summation expression. Such alternatives can be chosen only if the non-zero alternatives are precluded by contextual constraints. We refer to this model as one of “extremal probability” and to its signature as PCCS ζ . We provide PCCS ζ with a structural operational semantics and a notion of probabilistic bisimulation , which is shown to be a congruence. Of particular interest is the abstraction PCCS π of PCCS ζ in which all non-zero probability guards are identified. PCCS π represents a customized framework for reasoning about priority, and covers all features of process algebras proposed for reasoning about priority that we know of.

We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Whereas the complexity result is rather obvious, our optimality result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus using our method, the standard algorithms for sequential programs computing liveness, availability, very busyness, reaching definitions, definition-use chains, or the analyses for performing code motion, assignment motion, partial dead-code elimination or strength reduction, can straightforward be transferred to the parallel setting at almost no cost.

Assignment motion (AM) and expression motion (EM) are the basis of powerful and at the first sight incomparable techniques for removing partially redundant code from a program. Whereas AM aims at the elimination of complete assignments, a transformation which is always desirable, the more flexible EM requires temporaries to remove partial redundancies. Based on the observation that a simple program transformation enhances AM to subsume EM, we develop an algorithm that for the first time captures all second order effects between AM and EM transformations. Under usual structural restrictions, the worst case time complexity of our algorithm is essentially quadratic, a fact which explains the promising experience with our implementation. Topics: data flow analysis, program optimization, partially redundant assignment and expression elimination, code motion, assignment motion, bit-vector data flow analyses. 1 Motivation A major source for improving the runtime efficiency of a program is...

A new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. Besides being more powerful than the usual approaches to dead code elimination, this algorithm is optimal in the following sense: partially dead code remaining in the resulting program cannot be eliminated without changing the branching structure or the semantics of the program, or without impairing some program executions.

An implementation-oriented algorithm for lazy code motion is presented that minimizes the number of computations in programs while suppressing any unnecessary code motion in order to avoid superfluous register pressure. In particular, this variant of the original algorithm for lazy code motion works on flowgraphs whose nodes are basic blocks rather than single statements, since this format is standard in optimizing compilers. The theoretical foundations of the modified algorithm are given in the first part, where t -refined flowgraphs are introduced for simplifying the treatment of flow graphs whose nodes are basic blocks. The second part presents the “basic block” algorithm in standard notation and gives directions for its implementation in standard compiler environments.

The Concurrency Workbench is an automated tool for analyzing networks of finite-state processes expressed in Milner's Calculus of Communicating Systems. Its key feature is its breadth: a variety of different verification methods, including equivalence checking, preorder checking, and model checking, are supported for several different process semantics. One experience from our work is that a large number of interesting verification methods can be formulated as combinations of a small number of primitive algorithms. The Workbench has been applied to the verification of communications protocols and mutual exclusion algorithms and has proven a valuable aid in teaching and research.

We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. Moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. This laziness of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.

A technique is presented for ascertaining when a (finite-state) partial process specification is adequate, in the sense of being specified enough, for contexts in which it is to be used. The method relies on the automatic generation of a modal formula from the partial specification; if the remainder of the network satisfies this formula, then any process that meets the specification is guaranteed to ensure correct behavior of the overall system. Using the results, the authors develop compositional proof rules for establishing the correctness of networks of parallel processes and illustrate their use with several examples. >

Reactive, generative, and stratified models are considered within the framework of PCCS, a specification language for probabilistic processes. A structural operational semantics of PCCS, given as a set of inference rules for each of the models, a notion of bisimulation semantics, and some conference proofs are presented.>