Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Statistically validated networks in bipartite complex systems.
2011
Many complex systems present an intrinsic bipartite nature and are often described and modeled in terms of networks [1-5]. Examples include movies and actors [1, 2, 4], authors and scientific papers [6-9], email accounts and emails [10], plants and animals that pollinate them [11, 12]. Bipartite networks are often very heterogeneous in the number of relationships that the elements of one set establish with the elements of the other set. When one constructs a projected network with nodes from only one set, the system heterogeneity makes it very difficult to identify preferential links between the elements. Here we introduce an unsupervised method to statistically validate each link of the pr…
Gl-learning
2016
In this paper, we present a new open-source software library, Gl-learning, for grammatical inference. The rise of new application scenarios in recent years has required optimized methods to address knowledge extraction from huge amounts of data and to model highly complex systems. Our library implements the main state-of-the-art algorithms in the grammatical inference field (RPNI, EDSM, L*), redesigned through the OpenMP library for a parallel execution that drastically decreases execution times. To our best knowledge, it is also the first comprehensive library including a noise tolerance learning algorithm, such as Blue*, that significantly broadens the range of the potential application s…
Rough Sets and Vague Sets
2007
The subject-matter of the consideration touches the problem of vagueness. The notion of the rough set, originated by Zdzislaw Pawlak, was constructed under the influence of vague information and methods of shaping systems of notions leading to conceptualization and representation of vague knowledge, so also systems of their scopes as some vague sets. This paper outlines some direction of searching for a solution to this problem. In the paper, in connection to the notion of the rough set, the notion of a vague set is introduced. Some operations on these sets and their properties are discussed. The considerations intend to take into account a classical approach to reasoning, based on vague pr…
Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing
2020
The Tsetlin Machine (TM) is a machine learning algorithm founded on the classical Tsetlin Automaton (TA) and game theory. It further leverages frequent pattern mining and resource allocation principles to extract common patterns in the data, rather than relying on minimizing output error, which is prone to overfitting. Unlike the intertwined nature of pattern representation in neural networks, a TM decomposes problems into self-contained patterns, represented as conjunctive clauses. The clause outputs, in turn, are combined into a classification decision through summation and thresholding, akin to a logistic regression function, however, with binary weights and a unit step output function. …
ENFORCEMENT OF INTER-TASK DEPENDENCIES IN WORKFLOWS, CHARACTERIZATION AND PARADIGM
1998
Workflow techniques have gained a lot of attention as a means to support advanced business applications such as cooperative information systems and process re-engineering but also as a means to integrate legacy systems. Inter-task dependencies, described separately from the other parts of the workflow, have been recognized as a valuable method in describing certain restrictions on the executions of workflows. In this paper, we study the issue of pre-analysing and enforcing inter-task dependencies. The protocol and the theory behind it are presented, along with examples and discussions on ways to improve the performance. The idea is to present the meaning of a dependency through an automato…
Fragtique: Applying an OO Database Distribution Strategy to Data Warehouse
2001
We propose a strategy for distribution of a relational data warehouse organized according to a star schema. We adapt fragmentation and allocation strategies that were developed for OO databases. We split the most-often-accessed dimension table into fragments by using primary horizontal fragmentation. The derived fragmentation then divides the fact table into fragments. Other dimension tables are not fragmented since they are presumed to be sufficiently small. Allocation of fragments encompasses duplication of non-fragmented dimension tables that we call a closure.
Invisible Graffiti on Your Buildings: Blind and Squaring-Proof Watermarking of Geographical Databases
2007
Due to the ease of digital copy, watermarking is crucial to protect the intellectual property of rights owners. We propose an effective watermarking method for vectorial geographical databases, with the focus on the buildings layer. Embedded watermarks survive common geographical filters, including the essential squaring and simplification transformations, as well as deliberate removal attempts, e.g. by noise addition, cropping or over-watermarking. Robustness against the squaring transformation is not adressed by existing approaches. The impact on the quality of the datasets, defined as a composition of point accuracy and angular quality, is assessed through an extensive series of experime…
Random Tanglegram Partitions (Random TaPas): An Alexandrian Approach to the Cophylogenetic Gordian Knot
2018
Abstract Symbiosis is a key driver of evolutionary novelty and ecological diversity, but our understanding of how macroevolutionary processes originate extant symbiotic associations is still very incomplete. Cophylogenetic tools are used to assess the congruence between the phylogenies of two groups of organisms related by extant associations. If phylogenetic congruence is higher than expected by chance, we conclude that there is cophylogenetic signal in the system under study. However, how to quantify cophylogenetic signal is still an open issue. We present a novel approach, Random Tanglegram Partitions (Random TaPas) that applies a given global-fit method to random partial tanglegrams of …
Supervised learning of time-independent Hamiltonians for gate design
2018
We present a general framework to tackle the problem of finding time-independent dynamics generating target unitary evolutions. We show that this problem is equivalently stated as a set of conditions over the spectrum of the time-independent gate generator, thus transforming the task to an inverse eigenvalue problem. We illustrate our methodology by identifying suitable time-independent generators implementing Toffoli and Fredkin gates without the need for ancillae or effective evolutions. We show how the same conditions can be used to solve the problem numerically, via supervised learning techniques. In turn, this allows us to solve problems that are not amenable, in general, to direct ana…
Distributed Consensus on Boolean Information
2009
Abstract In this paper we study the convergence towards consensus on information in a distributed system of agents communicating over a network. The particularity of this study is that the information on which the consensus is seeked is not represented by real numbers, rather by logical values or sets. Whereas the problems of allowing a network of agents to reach a consensus on logical functions of input events, and that of agreeing on set–valued information, have been separately addressed in previous work, in this paper we show that these problems can indeed be attacked in a unified way in the framework of Boolean distributed information systems. Based on a notion of contractivity for Bool…