Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Enclosure method for the p-Laplace equation
2014
We study the enclosure method for the p-Calder\'on problem, which is a nonlinear generalization of the inverse conductivity problem due to Calder\'on that involves the p-Laplace equation. The method allows one to reconstruct the convex hull of an inclusion in the nonlinear model by using exponentially growing solutions introduced by Wolff. We justify this method for the penetrable obstacle case, where the inclusion is modelled as a jump in the conductivity. The result is based on a monotonicity inequality and the properties of the Wolff solutions.
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…
One-Counter Verifiers for Decidable Languages
2013
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…
Characteristic Sturmian words are extremal for the Critical Factorization Theorem
2012
We prove that characteristic Sturmian words are extremal for the Critical Factorization Theorem (CFT) in the following sense. If p x ( n ) denotes the local period of an infinite word x at point n , we prove that x is a characteristic Sturmian word if and only if p x ( n ) is smaller than or equal to n + 1 for all n ≥ 1 and it is equal to n + 1 for infinitely many integers n . This result is extremal with respect to the \{CFT\} since a consequence of the \{CFT\} is that, for any infinite recurrent word x, either the function p x is bounded, and in such a case x is periodic, or p x ( n ) ≥ n + 1 for infinitely many integers n . As a byproduct of the techniques used in the paper we extend a r…
On real-time algorithms for the location search of discontinuous conductivities with one measurement
2008
We discuss, and compare, two simple methods that provide coordinates of a point in the vicinity of one inclusion within some object with homogeneous electrical properties. In the context of nondestructive testing such an inclusion may correspond to a material defect, whereas in medicine this may correspond to a lesion in the brain, to name only two possible applications. Both methods use only one pair of voltage/current measurements on the entire boundary of the object to determine a single pair of coordinates that is considered to be close to the center of the inclusion. The first method has been proposed previously by Kwon, Seo and Yoon; the second method, called here the effective dipole…
Versatile Direct and Transpose Matrix Multiplication with Chained Operations: An Optimized Architecture Using Circulant Matrices
2016
With growing demands in real-time control, classification or prediction, algorithms become more complex while low power and small size devices are required. Matrix multiplication (direct or transpose) is common for such computation algorithms. In numerous algorithms, it is also required to perform matrix multiplication repeatedly, where the result of a multiplication is further multiplied again. This work describes a versatile computation procedure and architecture: one of the matrices is stored in internal memory in its circulant form, then, a sequence of direct or transpose multiplications can be performed without timing penalty. The architecture proposes a RAM-ALU block for each matrix c…
HPG-HMapper: A DNA hydroxymethylation analysis tool
2019
DNA methylation (mC) and hydroxymethylation (hmC) can significantly affect the normal human development, as well as health and disease status. hmC studies require not only specific treatment of DNA, but also software tools for their analysis. However, there are no software tools capable of analyzing DNA hmC currently. In this article, we propose HPG-HMapper, a parallel software tool for analyzing the DNA hmC data obtained by ten-eleven translocation–assisted bisulfite sequencing. This tool takes as input data the output files of mC aligner tools, and it yields mC maps and the accounting of methylated and hydroxymethylated bases on each chromosome. The design of this tool includes the consi…
New results for finding common neighborhoods in massive graphs in the data stream model
2008
AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. Our results correct and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding common neighborhoods in massive graphs, Theoretical Computer Science, 299 (1–3) 707–718 (2004)]
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…
Iterative Symmetry Detection: Shrinking vs. Decimating Patterns
2005
This paper introduces a new mechanism that consists of applying a symmetry operator on an iteratively transformed version of the input image. The nature of the transformation characterizes the operator. Here, we consider the Object Symmetry Transform combined with the morphological operator erosion and the pyramid decimation respectively. The derived operators have been applied on both binary and gray levels images, comparing their ability to grasp the internal structure of a digital object. We present some experiments to evaluate their performances and check them for result quality versus computing complexity.