Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Codification schemes and finite automata
2000
This paper is a note on how Information Theory and Codification Theory are helpful in the computational design both of communication protocols and strategy sets in the framework of finitely repeated games played by boundedly rational agents. More precisely, we show the usefulness of both theories to improve the existing automata bounds of Neyman¿s (1998) work on finitely repeated games played by finite automata.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…
Ein Verfahren zur Behandlung von Ausgleichsaufgaben mit Intervallkoeffizienten
1976
Es wird ein Verfahren beschrieben, das die Berechnung einer Intervalleinschliesung der Losungsmenge einer linearen Ausgleichsaufgabe mit Intervallkoeffizienten erlaubt. Es stellt eine Ubertragung des Bjorckschen Algorithmus der iterativen Verbesserung einer Naherungslosung zu einer linearen Ausgleichsaufgabe [5] auf ein bekanntes Verfahren zur Behandlung von Intervallgleichungssystemen dar.
Enhancing Attention’s Explanation Using Interpretable Tsetlin Machine
2022
Explainability is one of the key factors in Natural Language Processing (NLP) specially for legal documents, medical diagnosis, and clinical text. Attention mechanism has been a popular choice for such explainability recently by estimating the relative importance of input units. Recent research has revealed, however, that such processes tend to misidentify irrelevant input units when explaining them. This is due to the fact that language representation layers are initialized by pre-trained word embedding that is not context-dependent. Such a lack of context-dependent knowledge in the initial layer makes it difficult for the model to concentrate on the important aspects of input. Usually, th…
A-stabile Kollokationsverfahren mit mehrfachen Knoten
1982
Die Kollokationsmethoden, die vom Autor in [3] untersucht werden, liefern Spline-Approximationen fur die Losungen von Anfangswertproblemen bei gewohnlichen Differentialgleichungen. Einige allgemeine Resultate uber A-Stabilitat von Wanner, Hairer und Norsett [6] werden fur diese Methoden in dem Fall formuliert, wo sie mit gewissen impliziten Runge-Kutta-Methoden aquivalent sind. Hierbei wird die Abhangigkeit der A-Stabilitat von den Knoten und ihren Vielfachheiten offensichtlich.
Numerische Lösung gewöhnlicher Differentialgleichungen mit Splinefunktionen
1980
In dieser Arbeit wird ein allgemeines Verfahren zur Erzeugung von Splineapproximationen fur die Losungen von Anfangswertproblemen bei gewohnlichen Differentialgleichungen vorgestellt. Einige der bekannten Spline-approximationsmethoden sind als Spezialfalle enthalten. Eine gangige Vorgehensweise besteht darin, das Intervall, uber dem das Anfangswertproblem gegeben ist, in aquidistante Teilintervalle zu zerlegen und dann sukzessive die Splineapproximation zu definieren. Hierbei wird gefordert, das die Spline-approximation in den Knoten gewisse Bedingungen erfullt. Bei dem hier betrachteten allgemeinen Verfahren werden in den einzelnen Teilintervallen noch zusatzliche Zwischenknoten eingefuhrt…
Einige Bemerkungen zur Dualität in der konvexen Optimierung
1975
Die allgemeine Rockafellarsche Dualitatstheorie wird auf eine Reihe konvexer Optimierungsprobleme angewandt, um Dualitats-, Existenz-und Charakterisierungssatze fur Optimallosungen zu erhalten. Unter anderem werden auf diesem Wege einige schon bekannte Ergebnisse in sehr einfacher Weise wiedergewonnen.
On the path representation of networks
1982
A compact data structure for networks is obtained by storing arcs of paths sequentially. This structure allows forward and backward access from a node to its neighbors.
An Analysis of the Influence of Noneffective Instructions in Linear Genetic Programming
2020
Abstract Linear Genetic Programming (LGP) represents programs as sequences of instructions and has a Directed Acyclic Graph (DAG) dataflow. The results of instructions are stored in registers that can be used as arguments by other instructions. Instructions that are disconnected from the main part of the program are called noneffective instructions, or structural introns. They also appear in other DAG-based GP approaches like Cartesian Genetic Programming (CGP). This article studies four hypotheses on the role of structural introns: noneffective instructions (1) serve as evolutionary memory, where evolved information is stored and later used in search, (2) preserve population diversity, (3)…