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.

Função Afifim: Teoria e aplicações

In this work we present a proposal to contribute to the teaching and learning of affine function in the first year of high school having as prerequisite mathematical knowledge of basic education. The proposal focuses on some properties, special cases and applications of affine functions in order to show the importance of the demonstrations while awaken student interest by showing how this function is important to solve everyday problems

Interpolation estimate for a finite-element space with embedded discontinuities

We consider a recently proposed finite-element space that consists of piecewise affine functions with discontinuities across a smooth given interface Γ (a curve in two dimensions, a surface in three dimensions). Contrary to existing extended finite element methodologies, the space is a variant of the standard conforming Formula space that can be implemented element by element. Further, it neither introduces new unknowns nor deteriorates the sparsity structure. It is proved that, for u arbitrary in Formula, the interpolant Formula defined by this new space satisfies Graphic where h is the mesh size, Formula is the domain, Formula, Formula, Formula and standard notation has been adopted for the function spaces. This result proves the good approximation properties of the finite-element space as compared to any space consisting of functions that are continuous across Γ, which would yield an error in the Formula-norm of order Graphic. These properties make this space especially attractive for approximating the pressure in problems with surface tension or other immersed interfaces that lead to discontinuities in the pressure field. Furthermore, the result still holds for interfaces that end within the domain, as happens for example in cracked domains.

Affine Hall-Littlewood Functions for A(1)((1)) And Some Constant Term Identities of Cherednik-Macdonald-Mehta Type

We study t-analogs of string functions for integrable highest weight representations of the affine Kac-Moody algebra A(1)((1)). We obtain closed form formulas for certain t-string functions of levels 2 and 4. As corollaries, we obtain explicit identities for the corresponding affine Hall-Littlewood functions, as well as higher level generalizations of Cherednik's Macdonald and Macdonald-Mehta constant term identities.

Solitons, τ-functions and hamiltonian reduction for non-Abelian conformal affine Toda theories

We consider the Hamiltonian reduction of the two-loop Wess-Zumino-Novikov-Witten model (WZNW) based on an untwisted affine Kac-Moody algebra script Ĝ. The resulting reduced models, called Generalized Non-Abelian Conformal Affine Toda (G-CAT), are conformally invariant and a wide class of them possesses soliton solutions; these models constitute non-Abelian generalizations of the conformal affine Toda models. Their general solution is constructed by the Leznov-Saveliev method. Moreover, the dressing transformations leading to the solutions in the orbit of the vacuum are considered in detail, as well as the τ-functions, which are defined for any integrable highest weight representation of script Ĝ, irrespectively of its particular realization. When the conformal symmetry is spontaneously broken, the G-CAT model becomes a generalized affine Toda model, whose soliton solutions are constructed. Their masses are obtained exploring the spontaneous breakdown of the conformal symmetry, and their relation to the fundamental particle masses is discussed. We also introduce what we call the two-loop Virasoro algebra, describing extended symmetries of the two-loop WZNW models.

Tau-functions and dressing transformations for zero-curvature affine integrable equations

The solutions of a large class of hierarchies of zero-curvature equations that includes Toda- and KdV-type hierarchies are investigated. All these hierarchies are constructed from affine (twisted or untwisted) Kac-Moody algebras g. Their common feature is that they have some special vacuum solutions corresponding to Lax operators lying in some Abelian (up to the central term) subalgebra of g; in some interesting cases such subalgebras are of the Heisenberg type. Using the dressing transformation method, the solutions in the orbit of those vacuum solutions are constructed in a uniform way. Then, the generalized tau-functions for those hierarchies are defined as an alternative set of variables corresponding to certain matrix elements evaluated in the integrable highest-weight representations of g. Such definition of tau-functions applies for any level of the representation, and it is independent of its realization (vertex operator or not). The particular important cases of generalized mKdV and KdV hierarchies as well as the Abelian and non-Abelian affine Toda theories are discussed in detail. © 1997 American Institute of Physics.

The eight variable homogeneous degree three bent functions

We determine the affine equivalence classes of the eight variable degree three homogeneous bent functions using a new algorithm. Our algorithm applies to general bent functions and can systematically determine the automorphism groups. We provide a partial verification of the enumeration of eight variable degree three homogeneous bent functions obtained by Meng et al. We determine the affine equivalence classes of these functions.

End point estimates for Radon transform of radial functions on non-Euclidean spaces

We prove end point estimate for Radon transform of radial functions on affine Grasamannian and real hyperbolic space. We also discuss analogs of these results on the sphere.

The autocorrelation of speckles in deep Fresnel diffraction region and characterizations of random self-affine fractal surfaces

This paper studies the correlation properties of the speckles in the deep Fresnel diffraction region produced by the scattering of rough self-affine fractal surfaces. The autocorrelation function of the speckle intensities is formulated by the combination of the light scattering theory of Kirchhoff approximation and the principles of speckle statistics. We propose a method for extracting the three surface parameters, i.e. the roughness w, the lateral correlation length xi and the roughness exponent alpha, from the autocorrelation functions of speckles. This method is verified by simulating the speckle intensities and calculating the speckle autocorrelation function. We also find the phenomenon that for rough surfaces with alpha = 1, the structure of the speckles resembles that of the surface heights, which results from the effect of the peak and the valley parts of the surface, acting as micro-lenses converging and diverging the light waves.

Geometric and Algebraic Aspects of 3D Affine and Projective Structures from Perspective 2D Views

We investigate the differences --- conceptually and algorithmically --- between affine and projective frameworks for the tasks of visual recognition and reconstruction from perspective views. It is shown that an affine invariant exists between any view and a fixed view chosen as a reference view. This implies that for tasks for which a reference view can be chosen, such as in alignment schemes for visual recognition, projective invariants are not really necessary. We then use the affine invariant to derive new algebraic connections between perspective views. It is shown that three perspective views of an object are connected by certain algebraic functions of image coordinates alone (no structure or camera geometry needs to be involved).

From ensemble forecasts to predictive distribution functions

The translation of an ensemble of model runs into a probability distribution is a common task in model-based prediction. Common methods for such ensemble interpretations proceed as if verification and ensemble were draws from the same underlying distribution, an assumption not viable for most, if any, real world ensembles. An alternative is to consider an ensemble as merely a source of information rather than the possible scenarios of reality. This approach, which looks for maps between ensembles and probabilistic distributions, is investigated and extended. Common methods are revisited, and an improvement to standard kernel dressing, called ‘affine kernel dressing’ (AKD), is introduced. AKD assumes an affine mapping between ensemble and verification, typically not acting on individual ensemble members but on the entire ensemble as a whole, the parameters of this mapping are determined in parallel with the other dressing parameters, including a weight assigned to the unconditioned (climatological) distribution. These amendments to standard kernel dressing, albeit simple, can improve performance significantly and are shown to be appropriate for both overdispersive and underdispersive ensembles, unlike standard kernel dressing which exacerbates over dispersion. Studies are presented using operational numerical weather predictions for two locations and data from the Lorenz63 system, demonstrating both effectiveness given operational constraints and statistical significance given a large sample.

A Character Formula for the Category (O)over-tilde of Modules for Affine sl(2)

One may construct, for any function on the integers, an irreducible module of level zero for affine sl(2) using the values of the function as structure constants. The modules constructed using exponential-polynomial functions realize the irreducible modules with finite-dimensional weight spaces in the category (O) over tilde of Chari. In this work, an expression for the formal character of such a module is derived using the highest weight theory of truncations of the loop algebra.

The eight variable homogeneous degree three bent functions

We determine the affine equivalence classes of the eight variable degree three homogeneous bent functions using a new algorithm. Our algorithm applies to general bent functions and can systematically determine the automorphism groups. We provide a partial verification of the computer enumeration of bent functions by Meng et al.

Affine processes, arbitrage-Free Term structures of legendre polynomials,and option pricing

Multivariate Affine term structure models have been increasingly used for pricing derivatives in fixed income markets. In these models, uncertainty of the term structure is driven by a state vector, while the short rate is an affine function of this vector. The model is characterized by a specific form for the stochastic differential equation (SDE) for the evolution of the state vector. This SDE presents restrictions on its drift term which rule out arbitrages in the market. In this paper we solve the following inverse problem: Suppose the term structure of interest rates is modeled by a linear combination of Legendre polynomials with random coefficients. Is there any SDE for these coefficients which rules out arbitrages? This problem is of particular empirical interest because the Legendre model is an example of factor model with clear interpretation for each factor, in which regards movements of the term structure. Moreover, the Affine structure of the Legendre model implies knowledge of its conditional characteristic function. From the econometric perspective, we propose arbitrage-free Legendre models to describe the evolution of the term structure. From the pricing perspective, we follow Duffie et al. (2000) in exploring Legendre conditional characteristic functions to obtain a computational tractable method to price fixed income derivatives. Closing the article, the empirical section presents precise evidence on the reward of implementing arbitrage-free parametric term structure models: The ability of obtaining a good approximation for the state vector by simply using cross sectional data.

Connection between the affine and conformal affine Toda models and their Hirota solution

It is shown that the affine Toda models (AT) constitute a gauge fixed version of the conformal affine Toda model (CAT). This result enables one to map every solution of the AT models into an infinite number of solutions of the corresponding CAT models, each one associated to a point of the orbit of the conformal group. The Hirota τ-functions are introduced and soliton solutions for the AT and CAT models associated to SL̂ (r+1) and SP̂ (r) are constructed.