Search results for "Theory of Computation"
showing 10 items of 42 documents
Handling precedence constraints in scheduling problems by the sequence pair representation
2015
In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations…
Duality for constrained multifacility location problems with mixed norms and applications
1989
A dual problem is developed for the constrained multifacility minisum location problems involving mixed norms. General optimality conditions are also obtained providing new algorithms based on the concept of partial inverse of a multifunction. These algorithms which are decomposition methods, generate sequences globally converging to a primal and a dual solution respectively. Numerical results are reported.
A New Combinatorial Approach to Sequence Comparison
2008
In this paper we introduce a new alignment-free method for comparing sequences which is combinatorial by nature and does not use any compressor nor any information-theoretic notion. Such a method is based on an extension of the Burrows-Wheeler Transform, a transformation widely used in the context of Data Compression. The new extended transformation takes as input a multiset of sequences and produces as output a string obtained by a suitable rearrangement of the characters of all the input sequences. By using such a transformation we give a general method for comparing sequences that takes into account how much the characters coming from the different input sequences are mixed in the output…
A Smoothed Particle Image Reconstruction method
2010
Many image processing techniques work with scattered data distribution usually employing grid based methods leading to numerical problems. To address this issue, a numerical method avoiding mesh generation can be used. Such a method performs an integral representation by means of a smoothing kernel function and, in the discrete formulation, involves domain particles. In this paper the meshless Smoothed Particle Hydrodynamics method is proposed in the Image Reconstruction context and a new computational strategy called Smoothed Particle Image Reconstruction is presented; the new method is based on a scatter approach and several innovative ideas are introduced in order to improve the computat…
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
On Fibrations Between Internal Groupoids and Their Normalizations
2018
We characterize fibrations and $$*$$ -fibrations in the 2-category of internal groupoids in terms of the comparison functor from certain pullbacks to the corresponding strong homotopy pullbacks. As an application, we deduce the internal version of the Brown exact sequence for $$*$$ -fibrations from the internal version of the Gabriel–Zisman exact sequence. We also analyse fibrations and $$*$$ -fibrations in the category of arrows and study when the normalization functor preserves and reflects them. This analysis allows us to give a characterization of protomodular categories using strong homotopy kernels and a generalization of the Snake Lemma.
On Approximate Jumbled Pattern Matching in Strings
2011
Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t) = q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u, v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u <= q <= v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem …
Theory of Computation, Fuzziness and a physics of the immaterial
2013
In this paper we advance three clear-cut proposals as a contribution to the discussion on the role of notions of Computation and Fuzziness as a bridge between Hard and Soft Sciences. We suggest that an important difference between the two great fami- lies of science lies in their subject or research having a grounding in nature or not, and that Theory of Computation is a glaring exception to this classifi- cation, being a textbook hard science but dealing with the immaterial. We further advance that such unicity is strongly connected with Church-Turing thesis, and discuss about the role of Computation and Fuzziness as pillars of immaterial sciences
Fluted Logic with Counting
2021
The fluted fragment is a fragment of first-order logic in which the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that the fluted fragment possesses the finite model property. In this paper, we extend the fluted fragment by the addition of counting quantifiers. We show that the resulting logic retains the finite model property, and that the satisfiability problem for its (m+1)-variable sub-fragment is in m-NExpTime for all positive m. We also consider the satisfiability and finite satisfiability problems for the extension of any of these fragments in which the fluting requirement applies only to sub-form…
Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited
2014
International audience; We present an extension of Eilenberg's variety theorem, a well-known result connecting algebra to formal languages. We prove that there is a bijective correspondence between formations of finite monoids and certain classes of languages, the formations of languages. Our result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. We also prove a similar result for ordered monoids.; Nous présentons une extension du théorème des variétés d'Eilenberg, un résultat célèbre reliant l'algèbre à la théorie des langages formels. Nous montrons qu'il existe une correspondance bijective entre les form…