Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
Conjugacy problem for braid groups and Garside groups
2003
We present a new algorithm to solve the conjugacy problem in Artin braid groups, which is faster than the one presented by Birman, Ko and Lee. This algorithm can be applied not only to braid groups, but to all Garside groups (which include finite type Artin groups and torus knot groups among others).
Decentralized Coordination System for Multiple AGVs in a Structured Environment
2011
Abstract In this paper, we propose a decentralized coordination algorithm for safe and efficient management of a group of mobile robots following predefined paths in a dynamic industrial environment. The proposed algorithm is based on shared resources and proved to guarantee ordered traffic flows avoiding collisions and deadlocks. In consistency with the model of distributed robotic systems (DRS), no centralized mechanism, synchronized clock, shared memory or ground support is needed. A local inter-robot communication is required among a small number of spatially adjacent robotic units.
Elementary Integration of Superelliptic Integrals
2021
Consider a superelliptic integral $I=\int P/(Q S^{1/k}) dx$ with $\mathbb{K}=\mathbb{Q}(\xi)$, $\xi$ a primitive $k$th root of unity, $P,Q,S\in\mathbb{K}[x]$ and $S$ has simple roots and degree coprime with $k$. Note $d$ the maximum of the degree of $P,Q,S$, $h$ the logarithmic height of the coefficients and $g$ the genus of $y^k-S(x)$. We present an algorithm which solves the elementary integration problem of $I$ generically in $O((kd)^{\omega+2g+1} h^{g+1})$ operations.
Automated Synthesis of Application-layer Connectors from Automata-based Specifications
2019
Abstract Ubiquitous and Pervasive Computing, and the Internet of Things, promote dynamic interaction among heterogeneous systems. To achieve this vision, interoperability among heterogeneous systems represents a key enabler, and mediators are often built to solve protocol mismatches. Many approaches propose the synthesis of mediators. Unfortunately, a rigorous characterization of the concept of interoperability is still lacking, hence making hard to assess their applicability and soundness. In this paper, we provide a framework for the synthesis of mediators that allows us to: (i) characterize the conditions for the mediator existence and correctness; and (ii) establish the applicability bo…
Industrial Environment Mapping Using Distributed Static 3D Sensor Nodes
2018
This paper presents a system architecture for mapping and real-time monitoring of a relatively large industrial robotic environment of size 10 m × 15 m × 5 m. Six sensor nodes with embedded computing power and local processing of the 3D point clouds are placed close to the ceiling. The system architecture and data processing is based on the Robot Operating System (ROS) and the Point Cloud Library (PCL). The 3D sensors used are the Microsoft Kinect for Xbox One and point cloud data is collected at 20 Hz. A new manual calibration procedure is developed using reflective planes. The specified range of the used sensor is 0.8 m to 4.2 m, while depth data up to 9 m is used in this paper. Despite t…
Reverse-Safe Text Indexing
2021
We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstruction of the data they encode (i.e., they cannot be easily reversed). A data structure D is called z - reverse-safe when there exist at least z datasets with the same set of answers as the ones stored by D . The main challenge is to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and has size close to the size of the original dataset it encodes. Given a text of length n and an integer z , we propose an algorithm that constructs a z -reverse-safe data structure ( z -RSDS) that has size O(n) and answers decision and counting pattern matc…
Computer-assisted clinical diagnosis in the official European union languages
2016
eHealth services integrate Web Information Retrieval and Intelligent Medical Decision Support for health care professionals based on the range of possible symptoms which a patient reports. However, many symptoms like high temperature, fever, or headache, are ambiguous in terms of suggesting wide variety of possible patient's conditions to the GP, while other symptoms are mutually dependant, which again can be misleading to make an accurate diagnosis. On the other hand, doctor's up-to-date knowledge on the medicaments, drugs, active medical substances included, anticipated range of diseases relating to the symptoms reported, and the most reliable pharmaceutical manufacturers, are of the grea…
Extracting Formal Models from Normative Texts
2016
Normative texts are documents based on the deontic notions of obligation, permission, and prohibition. Our goal is model such texts using the C-O Diagram formalism, making them amenable to formal analysis, in particular verifying that a text satisfies properties concerning causality of actions and timing constraints. We present an experimental, semi-automatic aid to bridge the gap between a normative text and its formal representation. Our approach uses dependency trees combined with our own rules and heuristics for extracting the relevant components. The resulting tabular data can then be converted into a C-O Diagram.
Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems
2014
The ever-growing amount of data requires highly scalable storage solutions. The most flexible approach is to use storage pools that can be expanded and scaled down by adding or removing storage devices. To make this approach usable, it is necessary to provide a solution to locate data items in such a dynamic environment. This article presents and evaluates the Random Slicing strategy, which incorporates lessons learned from table-based, rule-based, and pseudo-randomized hashing strategies and is able to provide a simple and efficient strategy that scales up to handle exascale data. Random Slicing keeps a small table with information about previous storage system insert and remove operations…
Hierarchies of probabilistic and team FIN-learning
2001
AbstractA FIN-learning machine M receives successive values of the function f it is learning and at some moment outputs a conjecture which should be a correct index of f. FIN learning has two extensions: (1) If M flips fair coins and learns a function with certain probability p, we have FIN〈p〉-learning. (2) When n machines simultaneously try to learn the same function f and at least k of these machines output correct indices of f, we have learning by a [k,n]FIN team. Sometimes a team or a probabilistic learner can simulate another one, if their probabilities p1,p2 (or team success ratios k1/n1,k2/n2) are close enough (Daley et al., in: Valiant, Waranth (Eds.), Proc. 5th Annual Workshop on C…