Search results for "Discrete Mathematics"

2003

In this article we apply the S(M, g)–calculus of L. Hormander and, in particular, results concerning the spectral invariance of the algebra of operators of order zero in ℒ(L2(ℝn)) to study generators of Feller semigroups. The core of the article is the proof of the invertibility of λ Id + P for a strongly elliptic operator P in Ψ(M, g) and suitable weight functions M and metrics g. The proof depends highly on precise estimates of the remainder term in asymptotic expansions of the product symbol in Weyl and Kohn–Nirenberg quantization. Due to the Hille–Yosida–Ray theorem and a theorem of Courrege, the result concerning the invertibility of λ Id + P is applicable to obtain sufficient conditio…

Mappings of finite distortion: Monotonicity and continuity

2001

We study mappings f = ( f1, ..., fn) : Ω → Rn in the Sobolev space W loc (Ω,R n), where Ω is a connected, open subset of Rn with n ≥ 2. Thus, for almost every x ∈ Ω, we can speak of the linear transformation D f(x) : Rn → Rn, called differential of f at x. Its norm is defined by |D f(x)| = sup{|D f(x)h| : h ∈ Sn−1}. We shall often identify D f(x) with its matrix, and denote by J(x, f ) = det D f(x) the Jacobian determinant. Thus, using the language of differential forms, we can write

On the regularity of the Hardy-Littlewood maximal operator on subdomains of ℝn

2010

AbstractWe establish the continuity of the Hardy-Littlewood maximal operator on W1,p(Ω), where Ω ⊂ ℝn is an arbitrary subdomain and 1 < p < ∞. Moreover, boundedness and continuity of the same operator is proved on the Triebel-Lizorkin spaces Fps,q (Ω) for 1 < p,q < ∞ and 0 < s < 1.

Norm continuity and related notions for semigroups on Banach spaces

1996

We find some conditions on a c0-semigroup on a Banach space and its resolvent connected with the norm continuity of the semigroup. We use them to get characterizations of norm continuous, eventually norm continuous and eventually compact semigroups on Hilbert spaces in terms of the growth of the resolvent of their generator.

Estimates of maximal functions measuring local smoothness

1999

Letη be a nondecreasing function on (0, 1] such thatη(t)/t decreases andη(+0)=0. Letf ∈L(I n ) (I≡[0,1]. Set $${\mathcal{N}}_\eta f(x) = \sup \frac{1}{{\left| Q \right|\eta (\left| Q \right|^{1/n} )}} \smallint _Q \left| {f(t) - f(x)} \right|dt,$$ , where the supremum is taken over all cubes containing the pointx. Forη=t α (0<α≤1) this definition was given by A.Calderon. In the paper we prove estimates of the maximal functions $${\mathcal{N}}_\eta f$$ , along with some embedding theorems. In particular, we prove the following Sobolev type inequality: if $$1 \leqslant p< q< \infty , \theta \equiv n(1/p - 1/q)< 1, and \eta (t) \leqslant t^\theta \sigma (t),$$ , then $$\parallel {\mathcal{N}}_…

Invertibility of Sobolev mappings under minimal hypotheses

2010

Abstract We prove a version of the Inverse Function Theorem for continuous weakly differentiable mappings. Namely, a nonconstant W 1 , n mapping is a local homeomorphism if it has integrable inner distortion function and satisfies a certain differential inclusion. The integrability assumption is shown to be optimal.

Suffix array and Lyndon factorization of a text

2014

Abstract The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we prop…

Towards Axiomatic Basis of Inductive Inference

2001

The language for the formulation of the interesting statements is, of course, most important. We use first order predicate logic. Our main achievement in this paper is an axiom system which we believe to be more powerful than any other natural general purpose discovery axiom system. We prove soundness of this axiom system in this paper. Additionally we prove that if we remove some of the requirements used in our axiom system, the system becomes not sound. We characterize the complexity of the quantifier prefix which guaranties provability of a true formula via our system. We prove also that if a true formula contains only monadic predicates, our axiom system is capable to prove this formula…

Special factors and the combinatorics of suffix and factor automata

2011

AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.

Radio k-Labelings for Cartesian Products of Graphs

2005

International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…