Search results for "Crete"

Sturmian Graphs and a conjecture of Moser

2004

In this paper we define Sturmian graphs and we prove that all of them have a “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.

On the Power of Tree-Walking Automata

2000

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …

Sensitivity Versus Certificate Complexity of Boolean Functions

2016

Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $…

A note on the support of block idempotents

1994

Witness computation for solving geometric constraint systems

2014

International audience; In geometric constraint solving, the constraints are represented with an equation system F(U, X) = 0, where X denotes the unknowns and U denotes a set of parameters. The target solution for X is noted XT. A witness is a couple (U_W, X_W) such that F(U_W, X_W) = 0. The witness is not the target solution, but they share the same combinatorial features, even when the witness and the target lie on two distinct connected components of the solution set of F(U, X) = 0. Thus a witness enables the qualitative study of the system: the detection of over- and under-constrained systems, the decomposition into irreducible subsystems, the computation of subsystems boundaries. This …

Topological invariants of stable immersions of oriented 3-manifolds in R4

2012

Abstract We show that the Z -module of first order local Vassiliev type invariants of stable immersions of oriented 3-manifolds into R 4 is generated by 3 topological invariants: The number of pairs of quadruple points and the positive and negative linking invariants l + and l − introduced by V. Goryunov (1997) [7] . We obtain the expression for the Euler characteristic of the immersed 3-manifold in terms of these invariants. We also prove that the total number of connected components of the triple points curve is a non-local Vassiliev type invariant.

Introduction to generalized topological spaces

2011

[EN] We introduce the notion of generalized topological space (gt-space). Generalized topology of gt-space has the structure of frame and is closed under arbitrary unions and finite intersections modulo small subsets. The family of small subsets of a gt-space forms an ideal that is compatible with the generalized topology. To support the definition of gt-space we prove the frame embedding modulo compatible ideal theorem. Weprovide some examples of gt-spaces and study key topological notions (continuity, separation axioms, cardinal invariants) in terms of generalized spaces.

Factorization of homomorphisms through H∞(D)

2003

AbstractWeakly compact homomorphisms between (URM) algebras with connected maximal ideal space are shown to factor through H∞(D) by means of composition operators and to be strongly nuclear. The spectrum of such homomorphisms is also described. Strongly nuclear composition operators between algebras of bounded analytic functions are characterized. The path connected components of the space of endomorphisms on H∞(D) in the uniform operator topology are determined.

Sturmian graphs and integer representations over numeration systems

2012

AbstractIn this paper we consider a numeration system, originally due to Ostrowski, based on the continued fraction expansion of a real number α. We prove that this system has deep connections with the Sturmian graph associated with α. We provide several properties of the representations of the natural integers in this system. In particular, we prove that the set of lazy representations of the natural integers in this numeration system is regular if and only if the continued fraction expansion of α is eventually periodic. The main result of the paper is that for any number i the unique path weighted i in the Sturmian graph associated with α represents the lazy representation of i in the Ost…

General duality in vector optimization

1993

Vector minimization of a relation F valued in an ordered vector space under a constraint A consists in finding x 0 ∊ A w,0 ∊ Fx$0 such that w,0 is minimal in FA. To a family of vector minimization problemsminimize , one associates a Lagrange relation where ξ belongs to an arbitrary class Ξ of mappings, the main purpose being to recover solutions of the original problem from the vector minimization of the Lagrange relation for an appropriate ξ. This ξ turns out to be a solution of a dual vector maximization problem. Characterizations of exact and approximate duality in terms of vector (generalized with respect to Ξ) convexity and subdifferentiability are given. They extend the theory existin…