Bamberger Beiträge zur Wirtschaftsinformatik und Angewandten Informatik
Proceedings of the ACM SIGPLAN Workshop on Approaches and Applications of Inductive Programming (AAIP 2009)
- Inductive programming is concerned with the automated construction of declarative, often functional, recursive programs from incomplete specifications such as input/output examples. The inferred program must be correct with respect to the provided examples in a generalising sense: it should be neither equivalent to them, nor inconsistent. Inductive programming algorithms are guided explicitly or implicitly by a language bias (the class of programs that can be induced) and a search bias (determining which generalised program is constructed first). Induction strategies are either generate-and-test or example-driven. In generate-and-test approaches, hypotheses about candidate programs are generated independently from the given specifications. Program candidates are tested against the given specification and one or more of the best evaluated candidates are developed further. In analytical approaches, candidate programs are constructed in an example-driven way. While generate-and-test approaches can -- in principle -- construct any kind of program, analytical approaches have a more limited scope. On the other hand, efficiency of induction is much higher in analytical approaches. Inductive programming is still mainly a topic of basic research, exploring how the intellectual ability of humans to infer generalised recursive procedures from incomplete evidence can be captured in the form of synthesis methods. Intended applications are mainly in the domain of programming assistance -- either to relieve professional programmers from routine tasks or to enable non-programmers to some limited form of end-user programming. Furthermore, in the future, inductive programming techniques might be applied to further areas such as supporting the inference of lemmata in theorem proving or learning grammar rules. Inductive automated program construction has been originally addressed by researchers in artificial intelligence and machine learning. During the last years, some work on exploiting induction techniques has been started also in the functional programming community. Therefore, the third workshop on |Approaches and Applications of Inductive Programming| took place for the first time in conjunction with the ACM SIGPLAN International Conference on Functional Programming (ICFP 2009). The first and second workshop were associated with the International Conference on Machine Learning (ICML 2005) and the European Conference on Machine Learning (ECML 2007). AAIP´09 aimed to bring together researchers from the functional programming and the artificial intelligence communities, working in the field of inductive functional programming, and advance fruitful interactions between these communities with respect to programming techniques for inductive programming algorithms, the identification of challenge problems and potential applications. For everybody interested in inductive programming we recommend to visit the website: www.inductive-programming.org.
Proceedings of the KI 2009 Workshop on Complex Cognition
- The KI ´09 workshop on Complex Cognition was a joint venture of the Cognition group of the Special Interest Group Artificial Intelligence of the German Computer Science Society (Gesellschaft für Informatik) and the German Cognitive Science Association. Dealing with complexity has become one of the great challenges for modern information societies. To reason and decide, plan and act in complex domains is no longer limited to highly specialized professionals in restricted areas such as medical diagnosis, controlling technical processes, or serious game playing. Complexity has reached everyday life and affects people in such mundane activities as buying a train ticket, investing money, or connecting a home desktop to the internet. Research in cognitive AI can contribute to supporting people navigating through the jungle of everyday reasoning, decision making, planning and acting by providing intelligent support technology. Lessons learned from expert systems research of the nineteen-eighties show that the aim should not be to provide for fully automated systems which can solve specialized tasks autonomously but instead to develop interactive assistant systems where user and system work together by taking advantage of the respective strengths of human and machine. To accomplish a smooth collaboration between humans and intelligent systems, basic research in cognition is a necessary precondition. Insights into cognitive structures and processes underlying successful human reasoning and planning can provide suggestions for algorithm design. Even more important, insights into restrictions and typical errors and misconceptions of the cognitive systems provide information about those parts of a complex task from which the human should be relieved. For successful human-computer interaction in complex domains it has, furthermore, to be decided which information should be presented when, in what way, to the user. We strongly believe that symbolic approaches of AI and psychological research of higher cognition are at the core of success for the endeavor to create intelligent assistant system for complex domains. While insight into the neurological processes of the brain and into the realization of basic processes of perception, attention and senso-motoric coordination are important for the basic understanding of the principles of human intelligence, these processes have a much too fine granularity for the design and realization of interactive systems which must communicate with the user on knowledge level. If human system users are not to be incapacitated by a system, system decisions must be transparent for the user and the system must be able to provide explanations for the reasons of its proposals and recommendations. Therefore, even when some of the underlying algorithms are based on statistical or neuronal approaches, the top-level of such systems must be symbolical and rule-based. The papers presented at this workshop on complex cognition give an inspiring and promising overview of current work in the field which can provide first building stones for our endeavor to create knowledge level intelligent assistant systems for complex domains. The topics cover modelling basic cognitive processes, interfacing subsymbolic and symbolic representations, dealing with continuous time, Bayesian identification of problem solving strategies, linguistically inspired methods for assessing complex cognitive processes and complex domains such as recognition of sketches, predicting changes in stocks, spatial information processing, and coping with critical situations.
Grounding Synchronous Deterministic Concurrency in Sequential Programming
Reinhard Von Hanxleden
- In this report, we introduce an abstract interval domain I(D; P) and associated fixed point semantics for reasoning about concurrent and sequential variable accesses within a synchronous cycle-based model of computation. The interval domain captures must (lower bound) and cannot (upper bound) information to approximate the synchronisation status of variables consisting of a value status D and an init status P. We use this domain for a new behavioural definition of Berry’s causality analysis for Esterel. This gives a compact and uniform understanding of Esterel-style constructiveness for shared-memory multi-threaded programs. Using this new domain-theoretic characterisation we show that Berry’s constructive semantics is a conservative approximation of the recently proposed sequentially constructive (SC) model of computation. We prove that every Berry-constructive program is sequentially constructive, i.e., deterministic and deadlock-free under sequentially admissible scheduling. This gives, for the first time, a natural interpretation of Berry-constructiveness for main-stream imperative programming in terms of scheduling, where previous results were cast in terms of synchronous circuits. It also opens the door to a direct mapping of Esterel’s signal mechanism into boolean variables that can be set and reset arbitrarily within a tick.
We illustrate the practical usefulness of this mapping by discussing how signal reincarnation is handled efficiently by this transformation, which is of complexity that is linear in program
Konzeption einer Komponentenarchitektur für prozessorientierte OLTP- & OLAP-Anwendungssysteme
- Prozessorientierte Data-Warehouse-Systeme (DWH-Systeme) stellen, im Vergleich zu klassischen DWH-Systemen, neben entscheidungsunterstützenden Daten zum Ergebnis von Geschäftsprozessen auch Daten zu deren Ablauf bereit. Sie sind dabei auf zwei wesentliche Szenarien ausgerichtet: Das erste Szenario hat die Bereitstellung multidimensionaler, prozessbezogener Daten zum Ziel, mit denen die Gestaltung von Prozessen unterstützt werden kann. Das zweite Szenario hat die Datenbereitstellung und die Entscheidungsfindung mit niedriger Latenz zum Ziel. Es ist auf steuernde Maßnahmen in laufenden Prozessinstanzen ausgerichtet. Zur Unterstützung beider Szenarien wird im vorliegenden Beitrag ein Architekturkonzept für prozessorientierte OLTP- & OLAP-Anwendungssysteme, auf der Basis von Komponenten, vorgeschlagen. Das Architekturkonzept berücksichtigt dabei neben der Realisierung der Funktionen eines prozessorientierten DWH-Systems auch deren Integration mit Funktionen operativer Teilsysteme sowie Funktionen zur automatisierten Entscheidungsfindung.
Weitere im Architekturkonzept berücksichtigte Anforderungen sind die zeit- und bedarfsgerechte Informationsversorgung heterogener Nutzergruppen sowie die flexible Anpassbarkeit an Veränderungen in Geschäftsprozessen.
QoS-Enabled B2B Integration
- Business-To-Business Integration (B2Bi) is a key mechanism for enterprises to gain competitive advantage. However, developing B2Bi applications is far from trivial. Inter alia, agreement among integration partners about the business documents and the control flow of business document exchanges as well as applying suitable communication technologies for overcoming heterogeneous IT landscapes are major challenges. At the same time, choreography languages such as ebXML BPSS (ebBP), orchestration languages such as WS-BPEL and Web Services are promising to provide the foundations for seamless interactions among business partners. Automatically translating choreography agreements of integration partners into partner-specific orchestrations is an obvious idea for ensuring conformance of orchestration models to choreography models. Moreover, the application of such model-driven development methods facilitates productivity and cost-effectiveness whereas applying a service oriented architecture (SOA) based on WS-BPEL and Web Services leverages standardization and decoupling. By now, the realization of QoS attributes has not yet received the necessary attention that makes such approaches suitable for B2Bi. In this report, we describe a proof-of-concept implementation of the translation of ebBP choreographies into WS-BPEL orchestrations that respects B2Bi-relevant QoS attributes.
Concealing Presence Information in Instant Messaging Systems
- Information about online presence allows participants of instant messaging (IM) systems to determine whether their prospective communication partners will be able to answer their requests in a timely manner, or not. That is why presence information, combined with the ability to send instant messages, makes IM more personal and closer than other forms of communication such as e-mail. On the other hand, revelation of presence constitutes a potential of misuse by untrustworthy entities. A possible risk is the generation of online logs disclosing user habits. This makes presence information a resource worth protecting. We argue, however, that current IM systems do not take reasonable precautions to protect presence information. We implemented an IM system designed to be robust against attacks to disclose a user’s presence. In contrast to existing systems, it stores presence information in a registry in a way that is only detectable and applicable for intended users and not comprehensible even for the registry itself. We use a distributed hash table (DHT) as registry and apply an anonymous communication network to protect the physical addresses of both senders and receivers of messages.
A Generalised Theory of Interface Automata, Component Compatibility and Error
- Interface theories allow systems designers to reason about the composability and compatibility of concurrent system components. Such theories often extend both de Alfaro and Henzinger’s Interface Automata and Larsen’s Modal Transition Systems, which leads, however, to several issues that are undesirable in practice: an unintuitive treatment of specified unwanted behaviour, a binary compatibility concept that does not scale to multi-component assemblies, and compatibility guarantees that are insufficient for software product lines.
In this paper we show that communication mismatches are central to all these problems and, thus, the ability to represent such errors semantically is an important feature of an interface theory. Accordingly, we present the error-aware interface theory EMIA, where the above shortcomings are remedied by introducing explicit fatal error states. In addition, we prove via a Galois insertion that EMIA is a conservative generalisation of the established MIA (Modal Interface Automata) theory.
Decentralized Reputation Management for Cooperating Software Agents in Open Multi-Agent Systems
- Multi-Agent Systems (MAS) promise a new advance in distributed computing. In MAS autonomous software agents flexibly cooperate, coordinate, and compete to provide the desired function(s) of such a system. If some components of a MAS fail or do not provide the desired functionality, the system is expected to autonomously deal with these situations. It is desirable to reduce occurrences of such situations by selecting trustworthy cooperation partners before cooperating with them. This becomes even more desirable and important in an open MAS where arbitrary heterogeneous software agents, deployed by different parties, participate in the MAS, as it becomes more likely that these agents fail or try to exploit the MAS for their own purposes without reciprocation. In order to monitor agent behavior and enable selection of trustworthy cooperation partners, trust or reputation management services can be applied. As there is no central control in an open MAS and it is completely distributed these services themselves have to be distributed. This paper proposes a fully distributed reputation management service for open MAS based on peer-to-peer technology (especially distributed hash tables). A Java-based implementation of that service, which is intended as a plug-in for multi-agent platforms, is also described.
BPMN 2.0 Process Model Serialization Constraints
- Correct and standard compliant serializations of BPMN process models are crucial for model exchange between tools, automatic application of academic verification approaches and executability on BPMN engines. The official standard document does not provide an extensive set of all constraints regarding the correctness of model serializations. This technical reports fills this gap by presenting a categorized list of generic, technology independent constraints stated by the standard. Furthermore it is analyzed which rules are already covered when the standardized XSD-based serialization format is used.
Betsy - A BPEL Engine Test System
- More than five years have passed since the final release of the long-desired OASIS standard of a process language for web service orchestration, the Web Services Business Process Execution Language (BPEL). The aim of this standard is to establish a universally accepted orchestration language that forms a core part of current service-oriented architectures and, because of standardisation, avoids vendor lock-in. High expectations, in academia and practice alike, have been set on it. By now, several fully conformant and highly scalable engines should have arrived in the market. The perception of many however, is that standard conformance in current engines is far from given. It is our aim to shed light on this situation. In this study, we present the tool betsy, a BPEL Engine Test System that allows for a fully-automatic assessment of the standard conformance of a given BPEL engine. We use it to examine the five most important open source BPEL engines available today. Betsy comes with a large set of engineindependent conformance test cases for assessing BPEL standard conformance. This enables us to give a view of the state of the art in BPEL support.