Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Spectral and variational characterizations of solutions to semilinear eigenvalue problems

Die vorliegende Arbeit befaßt sich mit einer Klasse von nichtlinearen Eigenwertproblemen mit Variationsstrukturin einem reellen Hilbertraum. Die betrachteteEigenwertgleichung ergibt sich demnach als Euler-Lagrange-Gleichung eines stetig differenzierbarenFunktionals, zusätzlich sei der nichtlineare Anteil desProblems als ungerade und definit vorausgesetzt.Die wichtigsten Ergebnisse in diesem abstrakten Rahmen sindKriterien für die Existenz spektral charakterisierterLösungen, d.h. von Lösungen, deren Eigenwert gerade miteinem vorgegeben variationellen Eigenwert eines zugehörigen linearen Problems übereinstimmt. Die Herleitung dieserKriterien basiert auf einer Untersuchung kontinuierlicher Familien selbstadjungierterEigenwertprobleme und erfordert Verallgemeinerungenspektraltheoretischer Konzepte.Neben reinen Existenzsätzen werden auch Beziehungen zwischenspektralen Charakterisierungen und denLjusternik-Schnirelman-Niveaus des Funktionals erörtert.Wir betrachten Anwendungen auf semilineareDifferentialgleichungen (sowieIntegro-Differentialgleichungen) zweiter Ordnung. Diesliefert neue Informationen über die zugehörigenLösungsmengen im Hinblick auf Knoteneigenschaften. Diehergeleiteten Methoden eignen sich besonders für eindimensionale und radialsymmetrische Probleme, während einTeil der Resultate auch ohne Symmetrieforderungen gültigist.

Increased Levels of NOTCH1, NF-kappa B, and Other Interconnected Transcription Factors Characterize Primitive Sets of Hematopoietic Stem Cells

As previously shown, higher levels of NOTCH1 and increased NF-kappa B signaling is a distinctive feature of the more primitive umbilical cord blood (UCB) CD34+ hematopoietic stem cells (HSCs), as compared to bone marrow ( BM). Differences between BM and UCB cell composition also account for this finding. The CD133 marker defines a more primitive cell subset among CD34+ HSC with a proposed hemangioblast potential. To further evaluate the molecular basis related to the more primitive characteristics of UCB and CD133+ HSC, immunomagnetically purified human CD34+ and CD133+ cells from BM and UCB were used on gene expression microarrays studies. UCB CD34+ cells contained a significantly higher proportion of CD133+ cells than BM (70% and 40%, respectively). Cluster analysis showed that BM CD133+ cells grouped with the UCB cells ( CD133+ and CD34+) rather than to BM CD34+ cells. Compared with CD34+ cells, CD133+ had a higher expression of many transcription factors (TFs). Promoter analysis on all these TF genes revealed a significantly higher frequency ( than expected by chance) of NF-kappa B-binding sites (BS), including potentially novel NF-kappa B targets such as RUNX1, GATA3, and USF1. Selected transcripts of TF related to primitive hematopoiesis and self-renewal, such as RUNX1, GATA3, USF1, TAL1, HOXA9, HOXB4, NOTCH1, RELB, and NFKB2 were evaluated by real-time PCR and were all significantly positively correlated. Taken together, our data indicate the existence of an interconnected transcriptional network characterized by higher levels of NOTCH1, NF-kappa B, and other important TFs on more primitive HSC sets.

LOCAL WELL POSEDNESS, ASYMPTOTIC BEHAVIOR AND ASYMPTOTIC BOOTSTRAPPING FOR A CLASS OF SEMILINEAR EVOLUTION EQUATIONS OF THE SECOND ORDER IN TIME

A class of semilinear evolution equations of the second order in time of the form u(tt)+Au+mu Au(t)+Au(tt) = f(u) is considered, where -A is the Dirichlet Laplacian, 92 is a smooth bounded domain in R(N) and f is an element of C(1) (R, R). A local well posedness result is proved in the Banach spaces W(0)(1,p)(Omega)xW(0)(1,P)(Omega) when f satisfies appropriate critical growth conditions. In the Hilbert setting, if f satisfies all additional dissipativeness condition, the nonlinear Semigroup of global solutions is shown to possess a gradient-like attractor. Existence and regularity of the global attractor are also investigated following the unified semigroup approach, bootstrapping and the interpolation-extrapolation techniques.

Extremal problems on sum-free sets and coverings in tridimensional spaces

Given a prime power q, define c (q) as the minimum cardinality of a subset H of F 3 q which satisfies the following property: every vector in this space di ff ers in at most 1 coordinate from a multiple of a vector in H. In this work, we introduce two extremal problems in combinatorial number theory aiming to discuss a known connection between the corresponding coverings and sum-free sets. Also, we provide several bounds on these maps which yield new classes of coverings, improving the previous upper bound on c (q)

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

A minimal defining set of a Steiner triple system on a points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v + 1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on, 3" points; we construct minimal defining sets of volumes varying by as much as 7(n-/-).

On a semilinear Schrodinger equation with critical Sobolev exponent

We consider the semilinear Schrodinger equation -Deltau+V(x)u= K(x) \u \ (2*-2 u) + g(x; u), u is an element of W-1,W-2 (R-N), where N greater than or equal to4, V, K, g are periodic in x(j) for 1 less than or equal toj less than or equal toN, K>0, g is of subcritical growth and 0 is in a gap of the spectrum of -Delta +V. We show that under suitable hypotheses this equation has a solution u not equal 0. In particular, such a solution exists if K equivalent to 1 and g equivalent to 0.

Effect of oral creatine supplementation on near-maximal strength and repeated sets of high-intensity bench press exercise

This study examined the effects of 26 days of oral creatine monohydrate (Cr) supplementation on near-maximal muscular strength, high-intensity bench press performance, and body composition. Eighteen male powerlifters with at least 2 years resistance training experience took part in this 28-day experiment. Pre and postmeasurements (Days 1 and 28) were taken of near-maximal muscular strength, body mass, and % body fat. There were two periods of supplementation Days 2 to 6 and Days 7 to 27. ANOVA and t-tests revealed that Cr supplementation significantly increased body mass and lean body mass with no changes in % body fat. Significant increases in 3-RM strength occurred in both groups, both absolute and relative to body mass; the increases were greater in the Cr group. The change in total repetitions also increased significantly with Cr supplementation both in absolute terms and relative to body mass, while no significant change was seen in the placebo (P) group. Creatine supplementation caused significant changes in the number of BP reps in Sets 1, 4, and 5. No changes occurred in the P group. It appears that 26 days of Cr supplementation significantly improves muscular strength and repeated near-maximal BP performance, and induces changes in body composition.

Critical sets for families of Latin squares

In this paper I give details of new constructions for critical sets in latin squares. These latin squares, of order n, are such that they can be partitioned into four subsquares each of which is based on the addition table of the integers module n/2, an isotopism of this or a conjugate.

Maximal sets of Hamilton cycles in Kn,n

In this article, we prove that there exists a maximal set of m Hamilton cycles in K-n,K-n if and only if n/4 < m less than or equal to n/2. (C) 2000 John Wiley & Sons, Inc.

Slant or occlusion: global factors resolve stereoscopic ambiguity in sets of horizontal lines

Perceived slant was measured for horizontal lines aligned on one side and of varying lengths whose length disparity was either a constant linear amount for all lines (consistent with uniocular occlusion) or proportional to line length (consistent with global slant). Although the disparity of any line was ambiguous with respect to these two possibilities, slant of individual lines did not occur in the former case, but a subjective contour in depth was reported along the alignment. For proportional disparity of the set, global slant was seen. Adding a constant length to each line on the invalid eye for occlusion resulted in multiple slants. Smooth uniocular variations in alignment shape elicited subjective contours slanting or curving in depth. Global context can disambiguate the depth status of individual disparate lines. (C) 2004 Elsevier Ltd. All rights reserved.

Critical sets in direct products of back circulant Latin squares

To date very Few families of critical sets for latin squares are known. The only previously known method for constructing critical sets involves taking a critical set which is known to satisfy certain strong initial conditions and using a doubling construction. This construction can be applied to the known critical sets in back circulant latin squares of even order. However, the doubling construction cannot be applied to critical sets in back circulant latin squares of odd order. In this paper a family of critical sets is identified for latin squares which are the product of the latin square of order 2 with a back circulant latin square of odd order. The proof that each element of the critical set is an essential part of the reconstruction process relies on the proof of the existence of a large number of latin interchanges.