Search results for "combinatoric"
showing 10 items of 1776 documents
Three-page encoding and complexity theory for spatial graphs
2004
We construct a series of finitely presented semigroups. The centers of these semigroups encode uniquely up to rigid ambient isotopy in 3-space all non-oriented spatial graphs. This encoding is obtained by using three-page embeddings of graphs into the product of the line with the cone on three points. By exploiting three-page embeddings we introduce the notion of the three-page complexity for spatial graphs. This complexity satisfies the properties of finiteness and additivity under natural operations.
Three cyclic branched covers suffice to determine hyperbolic knots.
2005
Let n > m > 2 be two fixed coprime integers. We prove that two Conway reducible, hyperbolic knots sharing the 2-fold, m-fold and n-fold cyclic branched covers are equivalent. Using previous results by Zimmermann we prove that this implies that a hyperbolic knot is determined by any three of its cyclic branched covers.
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
Elements with square roots in compact groups
2010
The probability that a randomly chosen element has a square root is studied in [1, 2, 8] in the finite case. Here we deal with the infinite case.
Finitary Representations and Images of Transitive Finitary Permutation Groups
1999
Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.
Set-valued mappings in partially ordered fuzzy metric spaces
2014
Abstract In this paper, we provide coincidence point and fixed point theorems satisfying an implicit relation, which extends and generalizes the result of Gregori and Sapena, for set-valued mappings in complete partially ordered fuzzy metric spaces. Also we prove a fixed point theorem for set-valued mappings on complete partially ordered fuzzy metric spaces which generalizes results of Mihet and Tirado. MSC:54E40, 54E35, 54H25.
The Hamilton–Jacobi Equation
2001
We already know that canonical transformations are useful for solving mechanical problems. We now want to look for a canonical transformation that transforms the 2N coordinates (q i , p i ) to 2N constant values (Q i , P i ), e.g., to the 2N initial values \((q_{i}^{0},p_{i}^{0})\) at time t = 0. Then the problem would be solved, q = q(q0, p0, t), p = p(q0, p0, t).
Periodic and quasi-periodic orbits of the dissipative standard map
2011
We present analytical and numerical investigations of the dynamics of the dissipative standard map. We first study the existence of periodic orbits by using a constructive version of the implicit function theorem; then, we introduce a parametric representation, which provides the interval of the drift parameter ensuring the existence of a periodic orbit with a given period. The determination of quasi--periodic attractors is efficiently obtained using the parametric representation combined with a Newton's procedure, aimed to reduce the error of the approximate solution provided by the parametric representation. These methods allow us to relate the drift parameter of the periodic orbits to th…
On multiples of divisors associated to Veronese embeddings with defective secant variety
2009
In this note we consider multiples aD, where D is a divisor of the blow-up of P^n along points in general position which appears in the Alexander and Hirschowitz list of Veronese embeddings having defective secant varieties. In particular we show that there is such a D with h^1(X,D) > 0 and h^1(X,2D) = 0.
Longest Common Subsequence from Fragments via Sparse Dynamic Programming
1998
Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…