004 Datenverarbeitung; Informatik
Refine
Year of publication
Document Type
- Working Paper (119)
- Article (72)
- Doctoral Thesis (71)
- Diploma Thesis (46)
- Bachelor Thesis (34)
- Conference Proceeding (33)
- diplomthesis (28)
- Preprint (19)
- Report (12)
- Part of a Book (11)
Has Fulltext
- yes (471)
Is part of the Bibliography
- no (471)
Keywords
Institute
- Informatik (471) (remove)
This volume contains the proceedings of the 12th International Workshop on Termination (WST 2012), to be held February 19–23, 2012 in Obergurgl, Austria. The goal of the Workshop on Termination is to be a venue for presentation and discussion of all topics in and around termination. In this way, the workshop tries to bridge the gaps between different communities interested and active in research in and around termination. The 12th International Workshop on Termination in Obergurgl continues the successful workshops held in St. Andrews (1993), La Bresse (1995), Ede (1997), Dagstuhl (1999), Utrecht (2001), Valencia (2003), Aachen (2004), Seattle (2006), Paris (2007), Leipzig (2009), and Edinburgh (2010). The 12th International Workshop on Termination did welcome contributions on all aspects of termination and complexity analysis. Contributions from the imperative, constraint, functional, and logic programming communities, and papers investigating applications of complexity or termination (for example in program transformation or theorem proving) were particularly welcome. We did receive 18 submissions which all were accepted. Each paper was assigned two reviewers. In addition to these 18 contributed talks, WST 2012, hosts three invited talks by Alexander Krauss, Martin Hofmann, and Fausto Spoto.
1D-3D hybrid modeling : from multi-compartment models to full resolution models in space and time
(2014)
Investigation of cellular and network dynamics in the brain by means of modeling and simulation has evolved into a highly interdisciplinary field, that uses sophisticated modeling and simulation approaches to understand distinct areas of brain function. Depending on the underlying complexity, these models vary in their level of detail, in order to cope with the attached computational cost. Hence for large network simulations, single neurons are typically reduced to time-dependent signal processors, dismissing the spatial aspect of each cell. For single cell or networks with relatively small numbers of neurons, general purpose simulators allow for space and time-dependent simulations of electrical signal processing, based on the cable equation theory. An emerging field in Computational Neuroscience encompasses a new level of detail by incorporating the full three-dimensional morphology of cells and organelles into three-dimensional, space and time-dependent, simulations. While every approach has its advantages and limitations, such as computational cost, integrated and methods-spanning simulation approaches, depending on the network size could establish new ways to investigate the brain. In this paper we present a hybrid simulation approach, that makes use of reduced 1D-models using e.g., the NEURON simulator—which couples to fully resolved models for simulating cellular and sub-cellular dynamics, including the detailed three-dimensional morphology of neurons and organelles. In order to couple 1D- and 3D-simulations, we present a geometry-, membrane potential- and intracellular concentration mapping framework, with which graph- based morphologies, e.g., in the swc- or hoc-format, are mapped to full surface and volume representations of the neuron and computational data from 1D-simulations can be used as boundary conditions for full 3D simulations and vice versa. Thus, established models and data, based on general purpose 1D-simulators, can be directly coupled to the emerging field of fully resolved, highly detailed 3D-modeling approaches. We present the developed general framework for 1D/3D hybrid modeling and apply it to investigate electrically active neurons and their intracellular spatio-temporal calcium dynamics.
Contents:
Yuki Chiba, Santiago Escobar, Naoki Nishida, and David Sabel, and Manfred Schmidt-Schauß : Preface:
The Collection of all Abstracts of the Talks at WPTE 2015 xi
Brigitte Pientka : Mechanizing Meta-Theory in Beluga
Giulio Guerrieri : Head reduction and normalization in a call-by-value lambda-calculus
Adrián Palacios and Germán Vidal : Towards Modelling Actor-Based Concurrency in Term Rewriting
David Sabel and Manfred Schmidt-Schauß : Observing Success in the Pi-Calculus
Sjaak Smetsers, Ken Madlener, and Marko van Eekelen : Formalizing Bialgebraic Semantics in PVS 6.0
Klassische Bildmanipulation spielt sich meist im Zweidimensionalen, also in der reinen Bild-ebene ab. So werden beispielsweise Objekte aus Fotos entfernt, indem die dahinterliegende Struktur nachgezeichnet wird, oder es werden mehrere Teilbilder zu einem neuen, verfälschten Motiv zusammengesetzt. Bei der sogenannten Bildretuschierung werden unschöne Bereiche übermalt, um einen besseren Gesamteindruck zu erreichen. All diese Manipulationen haben im Grunde das gleiche Ziel: Das Erstellen einer möglichst realistischen Verfälschung der darge-stellten Szene indem die eigentlich dreidimensionalen Elemente in 2D imitiert werden.
Ziel dieser Arbeit ist es, von der reinen Zweidimensionalität eines Bildes Abstand zu nehmen und ein neues Verfahren zu entwickeln, Manipulationen im wirklichen 3D-Inhalt des Fotogra-fierten vorzunehmen. Dazu wird die klassische Bildmanipulation mit aktuellen Verfahren aus dem Bereich Multi View Stereo verknüpft. In einem ersten Schritt wird aus einer Fotoserie ein 3D-Modell mit passenden Texturen erstellt, welches anschließend nach Belieben manipuliert werden kann. Diese Veränderungen werden schließlich wieder in die Originalbilder übertragen, wodurch eine 3D-unterstützte Bildmanipulation realisiert wird.
Die praktische Umsetzung des vorgestellten Verfahrens basiert teilweise auf bereits vorhan-dener Software, die mit dem Ziel der Bildmanipulation neu kombiniert und durch eigene Um-setzungen ergänzt wird. So entsteht eine funktionierende Implementierung, die den kompletten Weg vom Original bis hin zum manipulierten Bild abdeckt.
We present a higher-order call-by-need lambda calculus enriched with constructors, case-expressions, recursive letrec-expressions, a seq-operator for sequential evaluation and a non-deterministic operator amb that is locally bottom-avoiding. We use a small-step operational semantics in form of a single-step rewriting system that defines a (nondeterministic) normal order reduction. This strategy can be made fair by adding resources for bookkeeping. As equational theory we use contextual equivalence, i.e. terms are equal if plugged into any program context their termination behaviour is the same, where we use a combination of may- as well as must-convergence, which is appropriate for non-deterministic computations. We show that we can drop the fairness condition for equational reasoning, since the valid equations w.r.t. normal order reduction are the same as for fair normal order reduction. We evolve different proof tools for proving correctness of program transformations, in particular, a context lemma for may- as well as mustconvergence is proved, which restricts the number of contexts that need to be examined for proving contextual equivalence. In combination with so-called complete sets of commuting and forking diagrams we show that all the deterministic reduction rules and also some additional transformations preserve contextual equivalence.We also prove a standardisation theorem for fair normal order reduction. The structure of the ordering <=c a is also analysed: Ω is not a least element, and <=c already implies contextual equivalence w.r.t. may-convergence.
We present a higher-order call-by-need lambda calculus enriched with constructors, case-expressions, recursive letrec-expressions, a seq-operator for sequential evaluation and a non-deterministic operator amb that is locally bottom-avoiding. We use a small-step operational semantics in form of a single-step rewriting system that defines a (nondeterministic) normal order reduction. This strategy can be made fair by adding resources for bookkeeping. As equational theory we use contextual equivalence, i.e. terms are equal if plugged into any program context their termination behaviour is the same, where we use a combination of may- as well as must-convergence, which is appropriate for non-deterministic computations. We show that we can drop the fairness condition for equational reasoning, since the valid equations w.r.t. normal order reduction are the same as for fair normal order reduction. We evolve different proof tools for proving correctness of program transformations, in particular, a context lemma for may- as well as mustconvergence is proved, which restricts the number of contexts that need to be examined for proving contextual equivalence. In combination with so-called complete sets of commuting and forking diagrams we show that all the deterministic reduction rules and also some additional transformations preserve contextual equivalence.We also prove a standardisation theorem for fair normal order reduction. The structure of the ordering <=c a is also analysed: Ω is not a least element, and <=c already implies contextual equivalence w.r.t. may-convergence.
We present a higher-order call-by-need lambda calculus enriched with constructors, case-expressions, recursive letrec-expressions, a seq-operator for sequential evaluation and a non-deterministic operator amb, which is locally bottom-avoiding. We use a small-step operational semantics in form of a normal order reduction. As equational theory we use contextual equivalence, i.e. terms are equal if plugged into an arbitrary program context their termination behaviour is the same. We use a combination of may- as well as must-convergence, which is appropriate for non-deterministic computations. We evolve different proof tools for proving correctness of program transformations. We provide a context lemma for may- as well as must- convergence which restricts the number of contexts that need to be examined for proving contextual equivalence. In combination with so-called complete sets of commuting and forking diagrams we show that all the deterministic reduction rules and also some additional transformations keep contextual equivalence. In contrast to other approaches our syntax as well as semantics does not make use of a heap for sharing expressions. Instead we represent these expressions explicitely via letrec-bindings.
This paper proves correctness of Nöcker's method of strictness analysis, implemented in the Clean compiler, which is an effective way for strictness analysis in lazy functional languages based on their operational semantics. We improve upon the work of Clark, Hankin and Hunt did on the correctness of the abstract reduction rules. Our method fully considers the cycle detection rules, which are the main strength of Nöcker's strictness analysis. Our algorithm SAL is a reformulation of Nöcker's strictness analysis algorithm in a higher-order call-by-need lambda-calculus with case, constructors, letrec, and seq, extended by set constants like Top or Inf, denoting sets of expressions. It is also possible to define new set constants by recursive equations with a greatest fixpoint semantics. The operational semantics is a small-step semantics. Equality of expressions is defined by a contextual semantics that observes termination of expressions. Basically, SAL is a non-termination checker. The proof of its correctness and hence of Nöcker's strictness analysis is based mainly on an exact analysis of the lengths of normal order reduction sequences. The main measure being the number of 'essential' reductions in a normal order reduction sequence. Our tools and results provide new insights into call-by-need lambda-calculi, the role of sharing in functional programming languages, and into strictness analysis in general. The correctness result provides a foundation for Nöcker's strictness analysis in Clean, and also for its use in Haskell.
In this paper we analyze the semantics of a higher-order functional language with concurrent threads, monadic IO and synchronizing variables as in Concurrent Haskell. To assure declarativeness of concurrent programming we extend the language by implicit, monadic, and concurrent futures. As semantic model we introduce and analyze the process calculus CHF, which represents a typed core language of Concurrent Haskell extended by concurrent futures. Evaluation in CHF is defined by a small-step reduction relation. Using contextual equivalence based on may- and should-convergence as program equivalence, we show that various transformations preserve program equivalence. We establish a context lemma easing those correctness proofs. An important result is that call-by-need and call-by-name evaluation are equivalent in CHF, since they induce the same program equivalence. Finally we show that the monad laws hold in CHF under mild restrictions on Haskell’s seq-operator, which for instance justifies the use of the do-notation.
Context unification is a variant of second-order unification and also a generalization of string unification. Currently it is not known whether context uni cation is decidable. An expressive fragment of context unification is stratified context unification. Recently, it turned out that stratified context unification and one-step rewrite constraints are equivalent. This paper contains a description of a decision algorithm SCU for stratified context unification together with a proof of its correctness, which shows decidability of stratified context unification as well as of satisfiability of one-step rewrite constraints.
The paper proposes a variation of simulation for checking and proving contextual equivalence in a non-deterministic call-by-need lambda-calculus with constructors, case, seq, and a letrec with cyclic dependencies. It also proposes a novel method to prove its correctness. The calculus’ semantics is based on a small-step rewrite semantics and on may-convergence. The cyclic nature of letrec bindings, as well as nondeterminism, makes known approaches to prove that simulation implies contextual equivalence, such as Howe’s proof technique, inapplicable in this setting. The basic technique for the simulation as well as the correctness proof is called pre-evaluation, which computes a set of answers for every closed expression. If simulation succeeds in finite computation depth, then it is guaranteed to show contextual preorder of expressions.
The paper proposes a variation of simulation for checking and proving contextual equivalence in a non-deterministic call-by-need lambda-calculus with constructors, case, seq, and a letrec with cyclic dependencies. It also proposes a novel method to prove its correctness. The calculus' semantics is based on a small-step rewrite semantics and on may-convergence. The cyclic nature of letrec bindings, as well as non-determinism, makes known approaches to prove that simulation implies contextual equivalence, such as Howe's proof technique, inapplicable in this setting. The basic technique for the simulation as well as the correctness proof is called pre-evaluation, which computes a set of answers for every closed expression. If simulation succeeds in finite computation depth, then it is guaranteed to show contextual preorder of expressions.
A framework for the analysis and visualization of multielectrode spike trains / von Ovidiu F. Jurjut
(2009)
The brain is a highly distributed system of constantly interacting neurons. Understanding how it gives rise to our subjective experiences and perceptions depends largely on understanding the neuronal mechanisms of information processing. These mechanisms are still poorly understood and a matter of ongoing debate remains the timescale on which the coding process evolves. Recently, multielectrode recordings of neuronal activity have begun to contribute substantially to elucidating how information coding is implemented in brain circuits. Unfortunately, analysis and interpretation of multielectrode data is often difficult because of their complexity and large volume. Here we propose a framework that enables the efficient analysis and visualization of multielectrode spiking data. First, using self-organizing maps, we identified reoccurring multi-neuronal spike patterns that evolve on various timescales. Second, we developed a color-based visualization technique for these patterns. They were mapped onto a three-dimensional color space based on their reciprocal similarities, i.e., similar patterns were assigned similar colors. This innovative representation enables a quick and comprehensive inspection of spiking data and provides a qualitative description of pattern distribution across entire datasets. Third, we quantified the observed pattern expression motifs and we investigated their contribution to the encoding of stimulus-related information. An emphasis was on the timescale on which patterns evolve, covering the temporal scales from synchrony up to mean firing rate. Using our multi-neuronal analysis framework, we investigated data recorded from the primary visual cortex of anesthetized cats. We found that cortical responses to dynamic stimuli are best described as successions of multi-neuronal activation patterns, i.e., trajectories in a multidimensional pattern space. Patterns that encode stimulus-specific information are not confined to a single timescale but can span a broad range of timescales, which are tightly related to the temporal dynamics of the stimuli. Therefore, the strict separation between synchrony and mean firing rate is somewhat artificial as these two represent only extreme cases of a continuum of timescales that are expressed in cortical dynamics. Results also indicate that timescales consistent with the time constants of neuronal membranes and fast synaptic transmission (~10-20 ms) appear to play a particularly salient role in coding, as patterns evolving on these timescales seem to be involved in the representation of stimuli with both slow and fast temporal dynamics.
Network graphs have become a popular tool to represent complex systems composed of many interacting subunits; especially in neuroscience, network graphs are increasingly used to represent and analyze functional interactions between multiple neural sources. Interactions are often reconstructed using pairwise bivariate analyses, overlooking the multivariate nature of interactions: it is neglected that investigating the effect of one source on a target necessitates to take all other sources as potential nuisance variables into account; also combinations of sources may act jointly on a given target. Bivariate analyses produce networks that may contain spurious interactions, which reduce the interpretability of the network and its graph metrics. A truly multivariate reconstruction, however, is computationally intractable because of the combinatorial explosion in the number of potential interactions. Thus, we have to resort to approximative methods to handle the intractability of multivariate interaction reconstruction, and thereby enable the use of networks in neuroscience. Here, we suggest such an approximative approach in the form of an algorithm that extends fast bivariate interaction reconstruction by identifying potentially spurious interactions post-hoc: the algorithm uses interaction delays reconstructed for directed bivariate interactions to tag potentially spurious edges on the basis of their timing signatures in the context of the surrounding network. Such tagged interactions may then be pruned, which produces a statistically conservative network approximation that is guaranteed to contain non-spurious interactions only. We describe the algorithm and present a reference implementation in MATLAB to test the algorithm’s performance on simulated networks as well as networks derived from magnetoencephalographic data. We discuss the algorithm in relation to other approximative multivariate methods and highlight suitable application scenarios. Our approach is a tractable and data-efficient way of reconstructing approximative networks of multivariate interactions. It is preferable if available data are limited or if fully multivariate approaches are computationally infeasible.
We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.
The human brain achieves visual object recognition through multiple stages of nonlinear transformations operating at a millisecond scale. To predict and explain these rapid transformations, computational neuroscientists employ machine learning modeling techniques. However, state-of-the-art models require massive amounts of data to properly train, and to the present day there is a lack of vast brain datasets which extensively sample the temporal dynamics of visual object recognition. Here we collected a large and rich dataset of high temporal resolution EEG responses to images of objects on a natural background. This dataset includes 10 participants, each with 82,160 trials spanning 16,740 image conditions. Through computational modeling we established the quality of this dataset in five ways. First, we trained linearizing encoding models that successfully synthesized the EEG responses to arbitrary images. Second, we correctly identified the recorded EEG data image conditions in a zero-shot fashion, using EEG synthesized responses to hundreds of thousands of candidate image conditions. Third, we show that both the high number of conditions as well as the trial repetitions of the EEG dataset contribute to the trained models’ prediction accuracy. Fourth, we built encoding models whose predictions well generalize to novel participants. Fifth, we demonstrate full end-to-end training of randomly initialized DNNs that output M/EEG responses for arbitrary input images. We release this dataset as a tool to foster research in visual neuroscience and computer vision.
The human brain achieves visual object recognition through multiple stages of linear and nonlinear transformations operating at a millisecond scale. To predict and explain these rapid transformations, computational neuroscientists employ machine learning modeling techniques. However, state-of-the-art models require massive amounts of data to properly train, and to the present day there is a lack of vast brain datasets which extensively sample the temporal dynamics of visual object recognition. Here we collected a large and rich dataset of high temporal resolution EEG responses to images of objects on a natural background. This dataset includes 10 participants, each with 82,160 trials spanning 16,740 image conditions. Through computational modeling we established the quality of this dataset in five ways. First, we trained linearizing encoding models that successfully synthesized the EEG responses to arbitrary images. Second, we correctly identified the recorded EEG data image conditions in a zero-shot fashion, using EEG synthesized responses to hundreds of thousands of candidate image conditions. Third, we show that both the high number of conditions as well as the trial repetitions of the EEG dataset contribute to the trained models’ prediction accuracy. Fourth, we built encoding models whose predictions well generalize to novel participants. Fifth, we demonstrate full end-to-end training of randomly initialized DNNs that output EEG responses for arbitrary input images. We release this dataset as a tool to foster research in visual neuroscience and computer vision.
In the last years, much effort went into the design of robust anaphor resolution algorithms. Many algorithms are based on antecedent filtering and preference strategies that are manually designed. Along a different line of research, corpus-based approaches have been investigated that employ machine-learning techniques for deriving strategies automatically. Since the knowledge-engineering effort for designing and optimizing the strategies is reduced, the latter approaches are considered particularly attractive. Since, however, the hand-coding of robust antecedent filtering strategies such as syntactic disjoint reference and agreement in person, number, and gender constitutes a once-for-all effort, the question arises whether at all they should be derived automatically. In this paper, it is investigated what might be gained by combining the best of two worlds: designing the universally valid antecedent filtering strategies manually, in a once-for-all fashion, and deriving the (potentially genre-specific) antecedent selection strategies automatically by applying machine-learning techniques. An anaphor resolution system ROSANA-ML, which follows this paradigm, is designed and implemented. Through a series of formal evaluations, it is shown that, while exhibiting additional advantages, ROSANAML reaches a performance level that compares with the performance of its manually designed ancestor ROSANA.
In contrast to the symbolic approach, neural networks seldom are designed to explain what they have learned. This is a major obstacle for its use in everyday life. With the appearance of neuro-fuzzy systems which use vague, human-like categories the situation has changed. Based on the well-known mechanisms of learning for RBF networks, a special neuro-fuzzy interface is proposed in this paper. It is especially useful in medical applications, using the notation and habits of physicians and other medically trained people. As an example, a liver disease diagnosis system is presented.
Relying on the theory of Saward (2010) and Disch (2015), we study political representation through the lens of representative claim-making. We identify a gap between the theoretical concept of claim-making and the empirical (quantitative) assessment of representative claims made in the real world’s representative contexts. Therefore, we develop a new approach to map and quantify representative claims in order to subsequently measure the reception and validation of the claims by the audience. To test our method, we analyse all the debates of the German parliament concerned with the introduction of the gender quota in German supervisory boards from 2013 to 2017 in a two-step process. At first, we assess which constituencies the MPs claim to represent and how they justify their stance. Drawing on multiple correspondence analysis, we identify different claim patterns. Second, making use of natural language processing techniques and logistic regression on social media data, we measure if and how the asserted claims in the parliamentary debates are received and validated by the respective audience. We come to the conclusion that the constituency as ultimate judge of legitimacy has not been comprehensively conceptualized yet.
In this paper we present a non-deterministic call-by-need (untyped) lambda calculus lambda nd with a constant choice and a let-syntax that models sharing. Our main result is that lambda nd has the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambdalifting using deterministic maximal free expressions. These results show that lambda nd is a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation. An intended application of lambda nd is as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
In this dissertation a non-deterministic lambda-calculus with call-by-need evaluation is treated. Call-by-need means that subexpressions are evaluated at most once and only if their value must be known to compute the overall result. Also called "sharing", this technique is inevitable for an efficient implementation. In the lambda-ND calculus of chapter 3 sharing is represented explicitely by a let-construct. Above, the calculus has function application, lambda abstractions, sequential evaluation and pick for non-deterministic choice. Non-deterministic lambda calculi play a major role as a theoretical foundation for concurrent processes or side-effected input/output. In this work, non-determinism additionally makes visible when sharing is broken. Based on the bisimulation method this work develops a notion of equality which respects sharing. Using bisimulation to establish contextual equivalence requires substitutivity within contexts, i.e., the ability to "replace equals by equals" within every program or term. This property is called congruence or precongruence if it applies to a preorder. The open similarity of chapter 4 represents a new concept, insofar that the usual definition of a bisimulation is impossible in the lambda-ND calculus. So in section 3.2 a further calculus lambda-Approx has to be defined. Section 3.3 contains the proof of the so-called Approximation Theorem which states that the evaluation in lambda-ND and lambda-Approx agrees. The foundation for the non-trivial precongruence proof is set out in chapter 2 where the trailblazing method of Howe is extended to be capable with sharing. By the use of this (extended) method, the Precongruence Theorem proves open similarity to be a precongruence, involving the so-called precongruence candidate relation. Joining with the Approximation Theorem we obtain the Main Theorem which says that open similarity of the lambda-Approx calculus is contained within the contextual preorder of the lambda-ND calculus. However, this inclusion is strict, a property whose non-trivial proof involves the notion of syntactic continuity. Finally, chapter 6 discusses possible extensions of the base calculus such as recursive bindings or case and constructors. As a fundamental study the calculus lambda-ND provides neither of these concepts, since it was intentionally designed to keep the proofs as simple as possible. Section 6.1 illustrates that the addition case and constructors could be accomplished without big hurdles. However, recursive bindings cannot be represented simply by a fixed point combinator like Y, thus further investigations are necessary.
This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order logic with a linear order and this permutation is as expressive as FO(Bit).
A partial rehabilitation of side-effecting I/O : non-determinism in non-strict functional languages
(1996)
We investigate the extension of non-strict functional languages like Haskell or Clean by a non-deterministic interaction with the external world. Using call-by-need and a natural semantics which describes the reduction of graphs, this can be done such that the Church-Rosser Theorems 1 and 2 hold. Our operational semantics is a base to recognise which particular equivalencies are preserved by program transformations. The amount of sequentialisation may be smaller than that enforced by other approaches and the programming style is closer to the common one of side-effecting programming. However, not all program transformations used by an optimising compiler for Haskell remain correct in all contexts. Our result can be interpreted as a possibility to extend current I/O-mechanism by non-deterministic deterministic memoryless function calls. For example, this permits a call to a random number generator. Adding memoryless function calls to monadic I/O is possible and has a potential to extend the Haskell I/O-system.
Non-coding variations located within regulatory elements may alter gene expression by modifying Transcription Factor (TF) binding sites and thereby lead to functional consequences like various traits or diseases. To understand these molecular mechanisms, different TF models are being used to assess the effect of DNA sequence variations, such as Single Nucleotide Polymorphisms (SNPs). However, few statistical approaches exist to compute statistical significance of results but they often are slow for large sets of SNPs, such as data obtained from a genome-wide association study (GWAS) or allele-specific analysis of chromatin data.
Results We investigate the distribution of maximal differential TF binding scores for general computational models that assess TF binding. We find that a modified Laplace distribution can adequately approximate the empirical distributions. A benchmark on in vitro and in vivo data sets showed that our new approach improves on an existing method in terms of performance and speed. In applications on large sets of eQTL and GWAS SNPs we could illustrate the usefulness of the novel statistic to highlight cell type specific regulators and TF target genes.
Conclusions Our approach allows the evaluation of DNA changes that induce differential TF binding in a fast and accurate manner, permitting computations on large mutation data sets. An implementation of the novel approach is freely available at https://github.com/SchulzLab/SNEEP.
We introduce a new method for representing and solving a general class of non-preemptive resource-constrained project scheduling problems. The new approach is to represent scheduling problems as de- scriptions (activity terms) in a language called RSV, which allows nested expressions using pll, seq, and xor. The activity-terms of RSV are similar to concepts in a description logic. The language RSV generalizes previous approaches to scheduling with variants insofar as it permits xor's not only of atomic activities but also of arbitrary activity terms. A specific semantics that assigns their set of active schedules to activity terms shows correctness of a calculus normalizing activity terms RSV similar to propositional DNF-computation. Based on RSV, this paper describes a diagram-based algorithm for the RSV-problem which uses a scan-line principle. The scan-line principle is used for determining and resolving the occurring resource conflicts and leads to a nonredundant generation of all active schedules and thus to a computation of the optimal schedule.
The well-known proof of termination of reduction in simply typed calculi is adapted to a monomorphically typed lambda-calculus with case and constructors and recursive data types. The proof differs at several places from the standard proof. Perhaps it is useful and can be extended also to more complex calculi.
One of the most interesting domains of feedforward networks is the processing of sensor signals. There do exist some networks which extract most of the information by implementing the maximum entropy principle for Gaussian sources. This is done by transforming input patterns to the base of eigenvectors of the input autocorrelation matrix with the biggest eigenvalues. The basic building block of these networks is the linear neuron, learning with the Oja learning rule. Nevertheless, some researchers in pattern recognition theory claim that for pattern recognition and classification clustering transformations are needed which reduce the intra-class entropy. This leads to stable, reliable features and is implemented for Gaussian sources by a linear transformation using the eigenvectors with the smallest eigenvalues. In another paper (Brause 1992) it is shown that the basic building block for such a transformation can be implemented by a linear neuron using an Anti-Hebb rule and restricted weights. This paper shows the analog VLSI design for such a building block, using standard modules of multiplication and addition. The most tedious problem in this VLSI-application is the design of an analog vector normalization circuitry. It can be shown that the standard approaches of weight summation will not give the convergence to the eigenvectors for a proper feature transformation. To avoid this problem, our design differs significantly from the standard approaches by computing the real Euclidean norm. Keywords: minimum entropy, principal component analysis, VLSI, neural networks, surface approximation, cluster transformation, weight normalization circuit.
Current deep learning methods are regarded as favorable if they empirically perform well on dedicated test sets. This mentality is seamlessly reflected in the resurfacing area of continual learning, where consecutively arriving data is investigated. The core challenge is framed as protecting previously acquired representations from being catastrophically forgotten. However, comparison of individual methods is nevertheless performed in isolation from the real world by monitoring accumulated benchmark test set performance. The closed world assumption remains predominant, i.e. models are evaluated on data that is guaranteed to originate from the same distribution as used for training. This poses a massive challenge as neural networks are well known to provide overconfident false predictions on unknown and corrupted instances. In this work we critically survey the literature and argue that notable lessons from open set recognition, identifying unknown examples outside of the observed set, and the adjacent field of active learning, querying data to maximize the expected performance gain, are frequently overlooked in the deep learning era. Hence, we propose a consolidated view to bridge continual learning, active learning and open set recognition in deep neural networks. Finally, the established synergies are supported empirically, showing joint improvement in alleviating catastrophic forgetting, querying data, selecting task orders, while exhibiting robust open world application.
The early prediction of mortality is one of the unresolved tasks in intensive care medicine. This contribution models medical symptoms as observations cased by transitions between hidden markov states. Learning the underlying state transition probabilities results in a prediction probability success of about 91%. The results are discussed and put in relation to the model used. Finally, the rationales for using the model are reflected: Are there states in the septic shock data?
We present the FPGA implementation of an algorithm [4] that computes implications between signal values in a boolean network. The research was performed as a masterrsquos thesis [5] at the University of Frankfurt. The recursive algorithm is rather complex for a hardware realization and therefore the FPGA implementation is an interesting example for the potential of reconfigurable computing beyond systolic algorithms. A circuit generator was written that transforms a boolean network into a network of small processing elements and a global control logic which together implement the algorithm. The resulting circuit performs the computation two orders of magnitudes faster than a software implementation run by a conventional workstation.
Active efficient coding explains the development of binocular vision and its failure in amblyopia
(2020)
The development of vision during the first months of life is an active process that comprises the learning of appropriate neural representations and the learning of accurate eye movements. While it has long been suspected that the two learning processes are coupled, there is still no widely accepted theoretical framework describing this joint development. Here, we propose a computational model of the development of active binocular vision to fill this gap. The model is based on a formulation of the active efficient coding theory, which proposes that eye movements as well as stimulus encoding are jointly adapted to maximize the overall coding efficiency. Under healthy conditions, the model self-calibrates to perform accurate vergence and accommodation eye movements. It exploits disparity cues to deduce the direction of defocus, which leads to coordinated vergence and accommodation responses. In a simulated anisometropic case, where the refraction power of the two eyes differs, an amblyopia-like state develops in which the foveal region of one eye is suppressed due to inputs from the other eye. After correcting for refractive errors, the model can only reach healthy performance levels if receptive fields are still plastic, in line with findings on a critical period for binocular vision development. Overall, our model offers a unifying conceptual framework for understanding the development of binocular vision.
Efficient algorithms for object recognition are crucial for the newly robotics and computer vision applications that demand real-time and on-line methods. Some examples are autonomous systems, navigating robots, autonomous driving. In this work, we focus on efficient semantic segmentation, which is the problem of labeling each pixel of an image with a semantic class.
Our aim is to speed-up all of the parts of the semantic segmentation pipeline. We also aim at delivering a labeling solution on a time budget, that can be decided on-the-fly. For this purpose, we analyze all the components of the semantic segmentation pipeline, and identify the computational bottleneck of each of them. The different components of the pipeline are over-segmenting the image with local regions, extracting features and classify the local regions, and the final inference of the image labeling with semantic classes. We focus on each of these steps.
First, we introduce a new superpixel algorithm to over-segment the image. Our superpixel method runs in real-time and can deliver a solution at any time budget. Then, for feature extraction, we focus on the framework that computes descriptors and encodes them, followed by a pooling step. We see that the encoding step is the bottleneck, for computational efficiency and performance. We present a novel assignment-based encoding formulation, that allows for the design of a new, very efficient, encoding. Finally, the image labeling output is obtained modeling the dependencies with a Conditional Random Field (CRF). In semantic image segmentation, the computational cost of instantiating the potentials is much higher than MAP inference. We introduce Active MAP inference to on-the-fly select a subset of potentials to be instantiated in the energy function, leaving the rest as unknown, and to estimate the MAP labeling from such incomplete energy function.
We perform experiments on all proposed methods for the different parts of the semantic segmentation pipeline. We show that our superpixel extraction achieves higher accuracy than state-of-the-art on standard superpixel benchmark, while it runs in real-time. We test our feature encoding on standard image classification and segmentation benchmarks, and we show that our method achieves competitive results with the state-of-the-art, and requires less time and memory. Finally, results for semantic segmentation benchmark show that Active MAP inference achieves similar levels of accuracy but with major efficiency gains.
The Internet as the biggest human library ever assembled keeps on growing. Although all kinds of information carriers (e.g. audio/video/hybrid file formats) are available, text based documents dominate. It is estimated that about 80% of all information worldwide stored electronically exists in (or can be converted into) text form. More and more, all kinds of documents are generated by means of a text processing system and are therefore available electronically. Nowadays, many printed journals are also published online and may even discontinue to appear in print form tomorrow. This development has many convincing advantages: the documents are both available faster (cf. prepress services) and cheaper, they can be searched more easily, the physical storage only needs a fraction of the space previously necessary and the medium will not age. For most people, fast and easy access is the most interesting feature of the new age; computer-aided search for specific documents or Web pages becomes the basic tool for information-oriented work. But this tool has problems. The current keyword based search machines available on the Internet are not really appropriate for such a task; either there are (way) too many documents matching the specified keywords are presented or none at all. The problem lies in the fact that it is often very difficult to choose appropriate terms describing the desired topic in the first place. This contribution discusses the current state-of-the-art techniques in content-based searching (along with common visualization/browsing approaches) and proposes a particular adaptive solution for intuitive Internet document navigation, which not only enables the user to provide full texts instead of manually selected keywords (if available), but also allows him/her to explore the whole database.
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. In this paper, for the small, important example of inflammation modeling a network is constructed and different learning algorithms are proposed. It turned out that due to the nonlinear dynamics evolutionary approaches are necessary to fit the parameters for sparse, given data. Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2003
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. In this paper, for the small, important example of inflammation modeling a network is constructed and different learning algorithms are proposed. It turned out that due to the nonlinear dynamics evolutionary approaches are necessary to fit the parameters for sparse, given data. Keywords: model parameter adaption, septic shock. coupled differential equations, genetic algorithm.
This paper describes the problems and an adaptive solution for process control in rubber industry. We show that the human and economical benefits of an adaptive solution for the approximation of process parameters are very attractive. The modeling of the industrial problem is done by the means of artificial neural networks. For the example of the extrusion of a rubber profile in tire production our method shows good results even using only a few training samples.
In der vorliegenden Arbeit wurde ein klinisches Alarmsystem für septische Schock-Patienten aufgebaut. Zweckmäßigerweise wurden hierfür metrische körpereigene Variablen verwendet, da Analysen belegt haben, dass die metrischen Daten besser zur Alarmgenerierung geeignet sind als die symbolischen Daten. Für das Training des adaptiven Neuro-Fuzzy-Systems wurden die Daten der letzten Tage des Intensivaufenthalts verwendet, da in diesem Zeitraum, im Gegensatz zu den ersten Tagen, eine gute Klassifikationsperformanz erreicht wurde. Die daraus resultierenden Alarmhistorien liefern zuverlässige Hinweise für den Intensivmediziner auf besonders kritische Patienten. Durch diese Arbeit wird es möglich werden, den medizinischen SOFA-Score, der aus 10 Variablen zusammengesetzt ist, durch die einfachere Kombination "Systolischer Blutdruck / Diastolischer Blutdruck / Thrombozyten" zu ersetzen mit einer mindestens genauso guten Performanz. Durch die Hinzunahme weiterer Variablen ist es möglich, die Performanz des SOFA-Scores zu überbieten, wobei der SOFA-Score bereits die beste Klassifikationsperformanz unter den getesteten Scores erreichte. Die erzeugten Regeln konnten die Klassifikationsentscheidung sinnvoll untermauern. Im Gegensatz zur automatischen Regelgenerierung war es Ärzten nicht möglich ahnlich sinnvolle formale Regeln zu formulieren.
We investigate methods and tools for analyzing translations between programming languages with respect to observational semantics. The behavior of programs is observed in terms of may- and mustconvergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extensions.
We investigate methods and tools for analyzing translations between programming languages with respect to observational semantics. The behavior of programs is observed in terms of may- and mustconvergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extensions.
We investigate methods and tools for analysing translations between programming languages with respect to observational semantics. The behaviour of programs is observed in terms of may- and mustconvergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extensions.
We investigate methods and tools for analysing translations between programming languages with respect to observational semantics. The behaviour of programs is observed in terms of may- and mustconvergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extensions.
We investigate methods and tools for analysing translations between programming languages with respect to observational semantics. The behaviour of programs is observed in terms of may- and must-convergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extension.
From 12.12.2010 to 17.12.2010, the Dagstuhl Seminar 10501 "Advances and Applications of Automata on Words and Trees" was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Seminar: 10501 - Advances and Applications of Automata on Words and Trees. The aim of the seminar was to discuss and systematize the recent fast progress in automata theory and to identify important directions for future research. For this, the seminar brought together more than 40 researchers from automata theory and related fields of applications. We had 19 talks of 30 minutes and 5 one-hour lectures leaving ample room for discussions. In the following we describe the topics in more detail.
Motivated by tools for automaed deduction on functional programming languages and programs, we propose a formalism to symbolically represent $\alpha$-renamings for meta-expressions. The formalism is an extension of usual higher-order meta-syntax which allows to $\alpha$-rename all valid ground instances of a meta-expression to fulfill the distinct variable convention. The renaming mechanism may be helpful for several reasoning tasks in deduction systems. We present our approach for a meta-language which uses higher-order abstract syntax and a meta-notation for recursive let-bindings, contexts, and environments. It is used in the LRSX Tool -- a tool to reason on the correctness of program transformations in higher-order program calculi with respect to their operational semantics. Besides introducing a formalism to represent symbolic $\alpha$-renamings, we present and analyze algorithms for simplification of $\alpha$-renamings, matching, rewriting, and checking $\alpha$-equivalence of symbolically $\alpha$-renamed meta-expressions.
Gegenstand dieser Arbeit war die Analyse der Komplexität von Kosten- und Erlösrechnungssystemen und ihrer Auswirkung auf die Auswahl geeigneter Instrumente für die EDV-gestützte Realisierung dieser Systeme, wobei insbesondere auf die bisherigen Ansätze der Datenbank- und Wissensuntersrutzung der Kosten- und Erlösrechnung eingegangen werden sollte. Das zweite Kapitel befaßt sich mit einer Analyse der Komplexität der in Deutschland am weitesten verbreiteten Kosten- und Erlösrechnungssysteme. Die Untersuchung der grundlegenden Gestaltungsmerkmale von Kosten- und Erlösrechnungssystemen auf ihre Komplexitätsrelevanz zeigte, daß einige Merkmale die Komplexität sehr stark beeinflussen, andere dagegen kaum, darunter auch in der betriebswirtschaftlichen Diskussion so wesentliche wie der verwendete Kostenbegriff. Den größten Einfluß auf die Komplexität von Kosten- und Erlösrechnungssystemen besitzen die Kosten- und Erlösstrukturierung sowie die Verarbeitungsarten, -methoden und -inhalte. Ein Vergleich der Grenzplankostenrechnung nach Kn.GER und FLAUT, stellvertretend Im überwiegend zweckmonistische Kostenrechnungssysteme, und der Einzelkostenrechnung nach RIEBEL als zweckpluralistischem Kosten- und Erlösrechnungssystem bezüglich der komplexitätsrelevanten Merkmale ergab eindeutige Unterschiede zwischen diesen Systemen. Während die Grenzplankostenrechnung polynomiale Platz- und Funktionskomplexitäten niedriger Grade (überwiegend quadratisch und nur im Rahmen der innerbetrieblichen Leistungsverrechnung kubisch) aufweist, treten in der Einzelkostenrechnung an mehreren entscheidenden Stellen exponentielle Komplexitäten auf. Die Analyse der Komplexität dieser beiden Kosten- und Erlösrechnungssystemen zeigt einen eindeutigen Zusammenhang zwischen vielseitiger Auswertbarkeit und der Komplexität eines Systems auf, der bei einer Beurteilung von Kosten- und Erlösrechnungssystemen berücksichtigt werden muß. Für die Gestaltung von Kosten- und Erlösrechnungssystemen bedeutet dies eine grundsätzliche Wahlmöglichkeit zwischen Systemen begrenzter Auswertbarkeit und niedriger Komplexität sowie Systemen mit größerer Auswertungsvielfalt, aber deutlich höherer Komplexität. Die Komplexität von Kosten- und Erlösrechnungssystemen ist jedoch nicht als eine Folge der Auswahl eines Rechnungssystems zu betrachten, sondern resultiert letztlich aus der Komplexität einer Unternehmung und ihrer Umwelt, die unterschiedlich detailliert abgebildet werden können. Da diese Komplexitäten in Zukunft eher noch zunehmen werden, ist grundSätzlich mit einem Trend zu universelleren und komplexeren Systemen zu rechnen. Die Erweiterung der Grenzplankostenrechnung hin zu größerer Komplexität sowie die Entwicklung neuerer Ansätze wie der Prozeßkostenrechnung bestätigen beide diesen Trend. Für die weitere Untersuchung wird vorausgesetzt, daß die Grenzplankostenrechnung und die Einzelkostenrechnung die entgegengesetzten Enden eines Komplexitätsspektrums von Kosten- und Erlösrechnungssystemen bilden und daher auch das Spektrum der Anforderungen an die Instrumente zu ihrer EDV-Implementierung begrenzen. Unter einer Anzahl von neueren Entwicklungen in der EDV wurden daher zwei Konzepte ausgewählt, die zur Behandlung verschiedener Aspekte der Komplexität geeignet sind: Datenbanksysteme zur Behandlung der Platzkomplexität und Wissenssysteme zur Behandlung der Funktionskomplexität. Im folgenden werden die Erfahrungen, die bei der Realisierung von Datenbank- und Wissenssystemen für die Kosten- und Erlösrechnung gemacht wurden, unter dem Gesichtspunkt der Komplexität von Kosten- und Erlösrechnungssystemen bewertet. Bei der Betrachtung von Datenbanksystemen ist zu berücksichtigen, daß sich im Laufe der Zeit zwei unterschiedliche Anwendungstypen herauskristallisiert haben: konventionelle Datenbankanwendungen, die den herkömmlichen Paradigmen von Datenbanksystemen entsprechen, und neuere Datenbankanwendungen, die z.T. wesentlich höhere Anforderungen stellen und so die Entwicklung neuer Datenbanksysteme erforderlich machten. Beide Systeme der Kosten- und Erlösrechnung eignen sich grundSätzlich als Datenbankanwendungen, d.h. sie rechtfertigen den Einsatz von Datenbanksystemen zur Verwaltung ihrer Datenmengen. Während die Grenzplankostenrechnung aber den konventionellen Datenbankanwendungen zuzurechnen ist, weist die Einzelkostenrechnung bereits wesentliche Merkmale neuerer Datenbankanwendungen auf. Im Gegensatz zu Datenbanksystemen sind die Anforderungen an Wissenssysteme und ihre Eigenschaften sehr unpräzise, z.T. sogar widersprüchlich formuliert. Auf der Basis der gängigen Eigenschaftskataloge erscheint die Kosten- und Erlösrechnung nicht als typische Wissenssystemanwendung. Trotzdem wurden bereits mehrere Wissenssysteme für Kosten- und Erlösrechnungsprobleme (Abweichungsanalyse, Betriebsergebnisanalyse, Bestimmung von Preisuntergrenzen, konstruktionsbegleitende Kalkulation und Teilprobleme der Prozeßkostenrechnung) realisiert, von denen jedes einige der Eignungskriterien für Wissenssystemanwendungen erfüllt. Die behandelten Beispiele für Wissenssysteme im Rahmen der Kosten- und Erlösrechnung basieren überwiegend auf der Grenzplankostenrechnung. Es ist daher anzunehmen, daß die Einzelkostenrechnung auf Grund ihrer höheren Komplexität weitere Anwendungsprobleme für Wissenssysteme enthält. Insgesamt sind jedoch die Unterschiede zwischen der Grenzplankostenrechnung und der Einzelkostenrechnung im Hinblick auf den Einsatz von Wissenssystemen wesentlich weniger ausgeprägt als dies für den Einsatz von Datenbanksystemen der Fall war. Nachdem beide Systeme der Kosten- und Erlösrechnung sowohl als Datenbankanwendungen geeignet sind als auch Anwendungsprobleme für Wissenssysteme aufweisen, ist auch die Verbindung von Wissenssystemen und Datenbanksystemen in Betracht zu ziehen. Daher wurde im Anschluß die jeweiligen Vor- und Nachteile von Datenbank- und Wissenssysteme gegenübergestellt. Die Vorteile von Datenbanksystemen liegen auf den maschinennäheren Ebenen, auf denen die Vorkehrungen für Datenschutz, Datensicherung, reibungslosen Mehrbenutzerbetrieb sowie die effiziente Ausführung der Operationen geschaffen werden. Die Vorteile von Wissenssystemen liegen in der größeren Mächtigkeit der Problemlösungskomponente, der Wissenserweiterungskomponente und der Erklärungskomponente. Ein neueres Beispiel für eine Zusammenarbeit von Datenbank- und Wissenssystemen ist die Auswertung eines speziell für derartige Zwecke angelegten Data Warehouse durch das Data Mining sowie andere Analysesysteme. Ein Data Warehouse stimmt in wesentlichen Merkmalen mit der Grundrechnung der Einzelkostenrechnung überein und zeigt, daß eine Grundrechnung auf der Basis heutiger EDV -Systeme realisierbar ist. Zur Auswertung einer Datenbank dieser Größe sind spezielle Analysesysteme notwendig. Für standardisierte Auswertungen eines Data Warehouse wurden OLAP-Systeme entwickelt, deren Operationen Verallgemeinerungen mehrdimensionaler Deckungsbeitragsrechnungen sind. Bei nicht standardisierbaren Auswertungen empfiehlt sich dagegen der Einsatz von Wissenssystemen, für den das Data Mining ein Beispiel liefert. Diese Kombination von Datenbanksystem, konventionellen und Kl-Auswertungen erscheint für eine Verwendung in der Kosten- und Erlösrechnung bestens geeignet. Das vierte Kapitel befaßt sich mit Ansätzen zur Strukturierung von Daten- und Wissensbasen, die bei Datenbanksystemen als Datenmodelle, bei Wissenssystemen als Wissensrepräsentationstechniken bezeichnet werden. Dabei wurde der Unterteilung des dritten Kapitels gefolgt und zwischen konventionellen und neueren Datenmodellen sowie Wissensrepräsentationstechniken unterschieden. Die Betrachtung des Relationenmodells als Vertreters der konventionellen Datenmodelle ergab, daß es für die Grenzplankostenrechnung völlig ausreicht. Die Erfahrungen mit der Realisierung einer Grundrechnung auf der Basis des Relationenmodells haben dagegen gezeigt, daß seine syntaktischen und semantischen Mängel zu weitgehenden Vereinfachungen beim Schemaentwurf zwingen, die wiederum die Operationen der Auswertungsrechnungen unnötig komplizieren. Aus der Vielzahl semantischer und objektorientierter Datenmodelle, die für neuere Datenbankanwendungen entwickelt wurden, hat sich trotz Unterschieden in Details eine Anzahl von Konzepten herauskristallisiert, die den meisten dieser DatenmodelIe gemeinsam sind. Mit Hilfe dieser Konzepte sind die Probleme, die bei der Verwendung des Relationenmodelis auftraten, vermeidbar. Im Grunde sind daher fast alle semantischen und objektorientierten Entwurfsmodelle zur ModelIierung einer Grundrechnung geeignet. Wichtig ist jedoch,daß die Grundrechnung auch mit einem Datenbanksystem realisiert wird, dem eines dieser Datenmodelle zugrunde liegt, da bei einer Transformation auf ein relationales Datenmodell wesentliche Entwurfsüberlegungen - und damit der größte Teil des Vorteils,den semantische und objektorientierte Entwurfsmodelle bieten -, verloren gehen. Zur Realisierung einer Grundrechnung erscheinen objektrelationale Datenbanksysteme am besten geeignet, da sie einerseits objektorientierte Konzepte mit mächtigen und komfortablen Anfragesprachen verbinden und andererseits aufwärtskompatibel zu den weitverbreiteten relationalen Datenbanksystemen sind. Da sich die objektorientierten Datenmodelle als für die Modellierung einer Grundrechnung geeignet erwiesen haben, wurden unter dem Gesichtspunkt der Verbindung von Datenbank- und Wissenssystemen nur objektorientierte Wissensrepräsentationstechniken in Betracht gezogen. Zwischen semantischen und objektorientierten Datenmodellen einerseits und objektorientierten Wissensrepräsentationstechniken, vor allem semantischen Netzen und Frames, andererseits bestehen weitgehende Übereinstimmungen. Daher können z.B. framebasierte Wissenssysteme direkt auf objektorientierten Datenbanksystemen realisiert werden. Inzwischen werden aber auch objektorientierte Programmiersprachen wie C++ oder Smalltalk zur Implementierung von Wissenssystemen verwendet, von denen die objektorientierte Sprache C++ am geeignetsten erscheint, da die meisten objektorientierten und objektrelationalen Datenbanksysteme eine C++-Schnittstelle aufweisen. Abschließend ist daher festzustellen, daß das Paradigma der Objektorientierung, das in Entwurfssprachen, Datenmodellen, Wissensrepräsentationstechniken und Programmiersprachen wesentliche Einflüsse ausgeübt hat, für die Realisierung der datenbankgestützten Grundrechnung eines zweckpluralistischen Kosten- und Erlösrechnungssystems wie der Einzelkostenrechnung sowie darauf aufbauender Auswertungsrechnungen, die z.T. als Wissenssysteme realisiert werden, wesentliche Vorteile besitzt. Über die adäquatere ModelIierung der Strukturen hinaus entsteht durch den Einsatz objektorientierter Techniken zum Entwurf und zur Implementierung aller System teile ein möglichst homogenes System, das nicht zusätzlich zu der inhärenten Komplexität noch weitere Probleme durch ungeeignete Darstellungskonzepte oder schlechte Abstimmung schafft.
Ambiguity and communication
(2009)
The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k which can be recognized by NFA's with size k poly(r) and ambiguity O(nk), but Lr,k has only NFA's with exponential size, if ambiguity o(nk) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998).