This thesis is about coalgebraic methods in software specification and verification. It extends known techniques of coalgebraic specification to a more general level to pave the way for real world applications of software verification. There are two main contributions of the present thesis: 1. Chapter 3 proposes a generalisation of the familiar notion of coalgebra such that classes containing methods with arbitrary types (including binary methods) can be modelled with these generalised coalgebras. 2. Chapter 4 presents the specification language CCSL (short for Coalgebraic Class Specification Language), its syntax, its semantics, and a prototype compiler that translates CCSL into higher-order logic. / Die Dissertation beschreibt coalgebraische Mittel und Methoden zur Softwarespezifikation und -verifikation. Die Ergebnisse dieser Dissertation vereinfachen die Anwendung coalgebraischer Spezifikations- und Verifikationstechniken und erweitern deren Anwendbarkeit. Damit werden Softwareverifikation im Allgemeinen und im Besonderen coalgebraische Methoden zur Softwareverifikation der praktischen Anwendbarkeit ein Stück nähergebracht. Diese Dissertation enthält zwei wesentliche Beiträge: 1. Im Kapitel 3 wird eine Erweiterung des klassischen Begriffs der Coalgebra vorgestellt. Diese Erweiterung erlaubt die coalgebraische Modellierung von Klassenschnittstellen mit beliebigen Methodentypen (insbesondere mit binären Methoden). 2. Im Kapitel 4 wird die coalgebraische Spezifikationssprache CCSL (Coalgebraic Class Specification Language) vorgestellt. Die Bescheibung umfasst Syntax, Semantik und einen Prototypcompiler, der CCSL Spezifikationen in Logik höherer Ordnung (passend für die Theorembeweiser PVS und Isabelle/HOL) übersetzt.

No description available.

Hämatopoetische Stammzellen besitzen die Fähigkeit, die dauerhafte Erhaltung ihrer eigenen Population im Knochenmark zu gewährleisten und gleichzeitig zur Neubildung der verschiedenen Zelltypen des peripheren Blutes beizutragen. Die Sequenz von Entscheidungsprozessen, die den Übergang einer undifferenzierten Stammzelle in eine funktionale ausgereifte Zelle beschreibt, wird als Linienspezifikation bezeichnet. Obwohl viele Details zu den molekularen Mechanismen dieser Entscheidungsprozesse mittlerweile erforscht sind, bestehen noch immer große Unklarheiten, wie die komplexen phänotypischen Veränderungen hervorgerufen und reguliert werden. Im Rahmen dieser Dissertation wird ein geeignetes mathematisches Modell der Linienspezifikation hämatopoetischer Stammzellen entwickelt, welches dann in ein bestehendes Modell der hämatopoetischen Stammzellorganisation auf Gewebsebene integriert wird. Zur Verifizierung des theoretischen Modells werden Simulationsergebnisse mit verschiedenen experimentellen Daten verglichen. Der zweite Teil dieser Arbeit konzentriert sich auf die Beschreibung und Analyse der Entwick- lungsprozesse von Einzelzellen, die aus diesem integrierten Modell hervorgehen. Aufbauend auf den entsprechenden Modellsimulationen wird dazu eine topologische Charakterisierung der resultierenden zellulären Genealogien etabliert, welche durch verschiedener Maße für deren Quantifizierung ergänzt wird. Das vorgestellte mathematische Modell stellt eine neuartige Verknüpfung der intrazellulären Linienspezifikation mit der Beschreibung der hämatopoetischen Stammzellorganisation auf Populationsebene her. Dadurch wird das Stammzellm- odell von Röder und Löffler um die wichtige Dimension der Linienspezifikation ergänzt und damit in seinem Anwendungsbereich deutlich ausgedehnt. Durch die Analyse von Einzelzellverläufen trägt das Modell zu einem grundlegenden Verständnis der inhärenten Heterogenität hämatopoetischer Stammzellen bei.

Runtime enforcement mechanisms are an important and well-employed method for ensuring an execution only exhibits acceptable behavior, as dictated by a security policy. Wherever interaction occurs between two or more parties that do not completely trust each other, it is most often the case that a runtime enforcement mechanism is between them in some form, monitoring the exchange. Considering the ubiquity of such scenarios in the computing world, there has been an increased effort to build formal models of runtime monitors that closely capture their capabilities so that their effectiveness can be analysed more precisely. While models have grown more faithful to their real-life counterparts, is- sues concerning complexity and manageability (a common concern for software engineers) of centralized policies remains to be fully addressed. The goal of this thesis is to provide a principled approach to policy construction that is modular, intuitive, and backed by formal methods. This thesis introduces a class of policy combinators adequate for use with runtime en- forcement policies and analyses a particular instance of them called Static Committee Com- binators (SCCs). SCCs present a model of policy composition where combinators act as committees that vote on events passing through the monitor. They were conceptualized in collaboration with Jay Ligatti and Daniel Lomsak. The general class of combinators are called Static Decision Combinators (SDCs), which share key features with SCCs such as allowing combinators to respond with alternative events when polled, in addition to re- sponding with grants or denials. SDCs treat the base-level policies they compose as black boxes, which helps decouple the system of combinators from the underlying policy model. The base policies could be modelled by automata but the combinators would not maintain their own state, being "static". This allows them to be easily defined and understood using truth tables, as well as analysed using logic tools. In addition to an analysis of SDCs and SCCs, we provide useful examples and a reusable combinator library.

Many physical systems break symmetry in their evolution. Biophysical systems, such as cells, developing organisms, and even entire populations, are no exception. Developing neurons represent a striking example of a biophysical system that breaks symmetry: neurons cultured in vitro begin as cell bodies with several tendrils (“neurites”) growing outward. A few days later, these same neurons invariably have the same new morphology: exactly one of the neurites (the “axon”) has grown hundreds of microns in length, while the others (the “dendrites”) are much shorter and are more branched. Previous work has shown that any of the neurites can become the axon, and so neurons must break symmetry during their development. The mechanisms underlying neuronal symmetry breaking and axon specification have recently attracted attention, with multiple groups proposing biophysical models to explain the phenomena. In this thesis, we perform the first analytical comparisons of these models by conducting multiple phenotypic and morphological studies of neurite growth in developing neurons. Studying neurite dynamics is technically challenging because neurites have unpredictable morphologies. In Chapter 4, we study neurite competition and neuronal symmetry breaking in hundreds of neurons by optically patterning micron-wide stripes to which the neurons adhere, and on which they grow exactly two neurites. We then use our measurements to test the accuracy of the models in the simple case when a neuron has exactly two neurites. In Chapter 5, we no longer constrain neuronal morphology. One characteristic of symmetry breaking systems is how the system’s complexity affects the symmetry breaking. We find that a majority of the models predict that neurons with more neurites break symmetry much slower than neurons with fewer neurites. Experimentally, we find that neurons with different neurite counts break symmetry at the same rate, consistent with previous observations. We then determine why the models disagree in their predictions, and rectify the models using our own experimental data. In particular, we find that neurons with higher neurite counts have higher concentrations of key proteins involved in symmetry breaking, so that neurons, regardless of neurite count, can break symmetry at the same rate. / Physics

This dissertation investigates the embryonic specification of a specific group of cells: the germ cells. Germ cells, which give rise to sperm and egg, are the only cells in sexually-reproducing animals that directly contribute hereditary information to the next generation. Germ cells are therefore a universal cell type across animals, and represent a profound novelty that likely arose near the base of the animal phylogeny. Yet despite their conserved, essential function in all animals, there is surprising diversity in the mechanisms that specify these cells during embryonic development. In this dissertation, I address the diversity of germ cell specification mechanisms in insects. I focus on two species, the milkweed bug Oncopeltus fasciatus (Hemiptera) and the cricket Gryllus bimaculatus (Orthoptera), which both branch basally to the Holometabola (those insects which undergo metamorphosis, including the well-studied fruit fly Drosophila melanogaster), and thus provide important phylogenetic breadth to our understanding of germ cell specification across insects. Using functional genetic approaches, I show that germ cell specification in both Oncopeltus and Gryllus differs fundamentally from germ cell specification in Drosophila. Specifically, I provide evidence that germ cells arise via inductive cell signaling during mid-embryogenesis, rather than via maternally-supplied cytoplasmic determinants localized in the oocyte, as is the case for Drosophila. These data suggest that Drosophila employs an evolutionarily derived mode of germ cell specification. In further support of this hypothesis, I show that several of the genes required for Drosophila germ cell specification perform other functions in both Oncopeltus and Gryllus. I demonstrate that one of these genes, oskar, which is the only gene both necessary and sufficient for germ cell specification in Drosophila, instead functions in nervous system of the cricket, both during embryonic development and in the adult brain. I suggest that the evolution of the derived mode of germ cell specification seen in Drosophila may have involved co-opting oskar into the germ cell specification pathway from an ancestral role in the nervous system.

Workflow technology has become a standard solution for managing increasingly complex business processes. Successful business process management depends on effective workflow modeling, which has been limited mainly to modeling the control and coordination of activities, i.e. the control flow perspective. However, given a workflow specification that is flawless from the control flow perspective, errors can still occur due to incorrect dataflow specification, which is referred to as dataflow anomalies.Currently, there are no sufficient formalisms for discovering and preventing dataflow anomalies in a workflow specification. Therefore, the goal of this dissertation is to develop formal methods for automatically detecting dataflow anomalies from a given workflow model and a rigorous approach for workflow design, which can help avoid dataflow anomalies during the design stage.In this dissertation, we first propose a formal approach for dataflow verification, which can detect dataflow anomalies such as missing data, redundant data, and potential data conflicts. In addition, we propose to use the dataflow matrix, a two-dimension table showing the operations each activity has on each data item, as a way to specify dataflow in workflows. We believe that our dataflow verification framework has added more analytical rigor to business process management by enabling systematic elimination of dataflow errors.We then propose a formal dependency-analysis-based approach for workflow design. A new concept called "activity relations" and a matrix-based analytical procedure are developed to enable the derivation of workflow models in a precise and rigorous manner. Moreover, we decouple the correctness issue from the efficiency issue as a way to reduce the complexity of workflow design and apply the concept of inline blocks to further simplify the procedure. These novel techniques make it easier to handle complex and unstructured workflow models, including overlapping patterns.In addition to proving the core theorems underlying the formal approaches and illustrating the validity of our approaches by applying them to real world cases, we provide detailed algorithms and system architectures as a roadmap for the implementation of dataflow verification and workflow design procedures.

The target of this project was to generate a prototype, which would model the elements of the user interface based on the information flow specification. The system is programmed using MS Visual Basic for Applications, its’ graphical environment is MS Visio 2000 and the elements of GUI for modeling are taken from MS Visio 2000 stencil WUI (wui.vss). The created module allows for easy modeling of graphical user interface elements for the data source, which is selected from the database. The processing stages of the data sources are illustrated using MS Visio 2000 documents’ windows, – one window for each stage. In the database, the elements of GUI are associated with the data source processing stages they are related to, i.e. the ones that they are present in. It means, that when working with the system, after selecting the desired data source and its processing stages one wants to model, the system generates the forms with associated GUI elements. This work was being done in the order of the scientific group of Information systems design, which analyses the design of the Information systems in the wide context of requirements engineering, process and data structures specification. This designed and realized model is going to be a part of a CASE tool meant for designing computerized information systems. Once the CASE tool is finished, it is planned to use it for educational purposes in Kaunas University of Technology in the department of Information systems. It is going to... [to full text]

Requirements engineers have to elicit, document, and validate how stakeholders act and interact to achieve their common goals in collaborative scenarios. Only after gathering all information concerning who interacts with whom to do what and why, can a software system be designed and realized which supports the stakeholders to do their work. To capture and structure requirements of different (groups of) stakeholders, scenario-based approaches have been widely used and investigated. Still, the elicitation and validation of requirements covering collaborative scenarios remains complicated, since the required information is highly intertwined, fragmented, and distributed over several stakeholders. Hence, it can only be elicited and validated collaboratively. In times of globally distributed companies, scheduling and conducting workshops with groups of stakeholders is usually not feasible due to budget and time constraints. Talking to individual stakeholders, on the other hand, is feasible but leads to fragmented and incomplete stakeholder scenarios. Going back and forth between different individual stakeholders to resolve this fragmentation and explore uncovered alternatives is an error-prone, time-consuming, and expensive task for the requirements engineers. While formal modeling methods can be employed to automatically check and ensure consistency of stakeholder scenarios, such methods introduce additional overhead since their formal notations have to be explained in each interaction between stakeholders and requirements engineers. Tangible prototypes as they are used in other disciplines such as design, on the other hand, allow designers to feasibly validate and iterate concepts and requirements with stakeholders. This thesis proposes a model-based approach for prototyping formal behavioral specifications of stakeholders who are involved in collaborative scenarios. By simulating and animating such specifications in a remote domain-specific visualization, stakeholders can experience and validate the scenarios captured so far, i.e., how other stakeholders act and react. This interactive scenario simulation is referred to as a model-based virtual prototype. Moreover, through observing how stakeholders interact with a virtual prototype of their collaborative scenarios, formal behavioral specifications can be automatically derived which complete the otherwise fragmented scenarios. This, in turn, enables requirements engineers to elicit and validate collaborative scenarios in individual stakeholder sessions – decoupled, since stakeholders can participate remotely and are not forced to be available for a joint session at the same time. This thesis discusses and evaluates the feasibility, understandability, and modifiability of model-based virtual prototypes. Similarly to how physical prototypes are perceived, the presented approach brings behavioral models closer to being tangible for stakeholders and, moreover, combines the advantages of joint stakeholder sessions and decoupled sessions. / Anforderungsingenieure erheben, dokumentieren und validieren wie Bedarfsträger in einzelnen und gemeinsamen Aktivitäten die Ziele ihrer kollaborativen Szenarios erreichen. Auf Grundlage von Angaben darüber, wer warum mit wem zusammen was erledigt, kann anschließend ein Softwaresystem spezifiziert und umgesetzt werden, welches die Bedarfsträger bei der Durchführung ihrer Abläufe unterstützt. Um Anforderungen verschiedener (Gruppen von) Bedarfsträger zu erfassen und zu strukturieren, werden szenariobasierte Ansätze genutzt und erforscht. Die Erhebung und Validierung von Anforderungen, die kollaborative Szenarios abdecken, ist dennoch kompliziert, da derartige Informationen hochgradig verknüpft, fragmentiert und über mehrere Bedarfsträger verteilt sind, wodurch sie nur in Gruppensitzungen effizient erhoben und validiert werden können. In Zeiten global verteilter Firmen ist die Planung und Durchführung solcher Workshops mit Gruppen von Bedarfsträgern nur selten praktikabel. Mit einzelnen Bedarfsträgern zu sprechen ist hingegen oft realisierbar, führt aber zu fragmentierten, unvollständigen Szenariobeschreibungen. Durch eine Vielzahl von Einzelgesprächen mit wechselnden Bedarfsträgern kann diese Fragmentierung aufgelöst werden – dies ist aber eine fehleranfällige und zeitaufwändige Aufgabe. Zwar bieten formale Modellierungsmethoden z.B. automatische Konsistenzchecks für Szenarios, doch führen derartige Methoden zu Mehraufwand in allen Gesprächen mit Bedarfsträgern, da diesen die verwendeten formalen Notationen jedes Mal erläutert werden müssen. Handfeste Prototypen, wie sie in anderen Disziplinen eingesetzt werden, ermöglichen es Designern, ihre Konzepte und erhobenen Anforderungen ohne viel Aufwand mit Bedarfsträgern zu validieren und zu iterieren. In dieser Dissertation wird ein modellbasierter Generierungsansatz vorgeschlagen, der kollaborative Szenarios prototypisch auf Grundlage von formalen Verhaltensmodellen für die beteiligten Bedarfsträger darstellt. Durch die Simulation dieses Verhaltens und dessen Animation innerhalb einer webbasierten, domänenspezifischen Visualisierung, können Bedarfsträger diese Modelle erleben und die bisher erfassten Szenarios validieren. Eine derartige interaktive Szenariosimulation wird als modellbasierter virtueller Prototyp bezeichnet. Basierend auf den Interaktionen zwischen Bedarfsträgern und einem virtuellen Prototypen ihrer Szenarios können zudem formale Verhaltensspezifikationen automatisch abgeleitet werden, die wiederum die fragmentierten kollaborativen Szenarios vervollständigen. Dies ermöglicht es den Anforderungsingenieuren, die kollaborativen Szenarios in individuellen Sitzungen mit einzelnen Bedarfsträgern zu erheben und zu validieren – entkoppelt voneinander, da Bedarfsträger webbasiert teilnehmen können und dabei nicht darauf angewiesen sind, dass andere Bedarfsträger ebenfalls in der gleichen Sitzung teilnehmen. Diese Dissertation diskutiert und evaluiert die Machbarkeit, Verständlichkeit sowie die Änderbarkeit der modellbasierten virtuellen Prototypen. Auf die gleiche Art wie physikalische Prototypen wahrgenommen werden, erlaubt es der vorgestellte Ansatz, Verhaltensmodelle für Bedarfsträger erlebbar zu machen und so die Vorteile von Gruppensitzungen mit denen entkoppelter Sitzungen zu verbinden.

Automatic verification has nowadays become a central domain of investigation in computer science. Over 25 years, a rich theory has been developed leading to numerous tools, both in academics and industry, allowing the verification of Boolean properties - those that can be either true or false. Current needs evolve to a finer analysis, a more quantitative one. Extension of verification techniques to quantitative domains has begun 15 years ago with probabilistic systems. However, many other quantitative properties are of interest, such as the lifespan of an equipment, energy consumption of an application, the reliability of a program, or the number of results matching a database query. Expressing these properties requires new specification languages, as well as algorithms checking these properties over a given structure. This thesis aims at investigating several formalisms, equipped with weights, able to specify such properties: denotational ones - like regular expressions, first-order logic with transitive closure, or temporal logics - or more operational ones, like navigating automata, possibly extended with pebbles. A first objective of this thesis is to study expressiveness results comparing these formalisms. In particular, we give efficient translations from denotational formalisms to the operational one. These objects, and the associated results, are presented in a unified framework of graph structures. This permits to handle finite words and trees, nested words, pictures or Mazurkiewicz traces, as special cases. Therefore, possible applications are the verification of quantitative properties of traces of programs (possibly recursive, or concurrent), querying of XML documents (modeling databases for example), or natural language processing. Second, we tackle some of the algorithmic questions that naturally arise in this context, like evaluation, satisfiability and model checking. In particular, we study some decidability and complexity results of these problems depending on the underlying semiring and the structures under consideration (words, trees...). Finally, we consider some interesting restrictions of the previous formalisms. Some permit to extend the class of semirings on which we may specify quantitative properties. Another is dedicated to the special case of probabilistic specifications: in particular, we study syntactic fragments of our generic specification formalisms generating only probabilistic behaviors.