No description available.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第23688号 / 理博第4778号 / 新制||理||1684(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)教授 柳瀬 陽一, 教授 川上 則雄, 教授 松田 祐司 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

For $n\geq2$, a variety $\mathcal{V}$ is said to be congruence $n$-permutable if every algebra $\mathbf{A}\in\mathcal{V}$ satisfies $\alpha\circ^n\beta=\beta\circ^n\alpha$, for all $\alpha,\beta\in \Con(\mathbf{A})$. Furthermore, given any algebra $\mathbf{A}$ and $k\geq1$, a $k$-dimensional Hagemann relation on $\mathbf{A}$ is a reflexive compatible relation $R\subseteq A\times A$ such that $R^{-1}\not\subseteq R\circ^k R$. A famous result of J. Hagemann and A. Mitschke shows that a variety $\mathcal{V}$ is congruence $n$-permutable if and only if $\mathcal{V}$ has no member carrying an $(n-1)$-dimensional Hagemann relation: by using this criterion, we provide another Maltsev characterization of congruence $n$-permutability, equivalent to the well-known Schmidt's and Hagemann-Mitschke's (\cite{HagMit}) term-based descriptions. We further establish that the omission by varieties of certain special configurations of Hagemann relations induces the satisfaction of suitable Maltsev conditions. These omission properties may be used to characterize congruence $n$-permutable idempotent varieties for some $n\geq2$, congruence 2-permutable idempotent varieties and congruence 3-permutable locally finite idempotent varieties, yielding that the following are prime Maltsev conditions: \begin{enumerate} \item congruence $n$-permutability for some $n\geq2$ with respect to idempotent varieties; \item congruence 2-permutability with respect to idempotent varieties; \item congruence 3-permutability with respect to locally finite idempotent varieties. \end{enumerate} Finally, we focus on the analysis of a family of strong Maltsev conditions, which we denote by $\{\mathcal{D}_n:2\leq n<\omega\}$, such that any variety $\mathcal{V}$ is congruence $n$-permutable whenever $\mathcal{D}_n$ is interpretable in $\mathcal{V}$. Among various other properties, we also show that the $\mathcal{D}_n$'s with odd $n\geq3$ generate decomposable strong Maltsev filters in the lattice of interpretability types. / Thesis / Doctor of Philosophy (PhD)

A significant part of the System-on-a-Chip (SoC) design problem is in the correct composition of intellectual property (IP) blocks. Ever increasing clock frequencies make it impossible for signals to reach from one end of the chip to the other end within a clock cycle; this invalidates the so-called synchrony assumption, where the timing of computation and communication are assumed to be negligible, and happen within a clock cycle. Missing the timing deadline causes this violation, and may have ramifications on the overall system reliability. Although latency insensitive protocols (LIPs) have been proposed as a solution to the problem of signal propagation over long interconnects, they have their own limitations. A more generic solution comes in the form of globally asynchronous locally synchronous (GALS) designs. However, composing synchronous IP blocks either over long multicycle delay interconnects or over asynchronous communication links for a GALS design is a challenging task, especially for ensuring the functional correctness of the overall design. In this thesis, we analyze various solutions for solving the synchronization problems related with IP composition. We present alternative LIPs, and provide a validation framework for ensuring their correctness. Our notion of correctness is that of latency equivalence between a latency insensitive design and its synchronous counterpart. We propose a trace-based framework for analyzing synchronous behaviors of different IPs, and provide a correct-by-construction protocol for their transformation to a GALS design. We also present a design framework for facilitating GALS designs. In the framework, Kahn process network specifications are refined into correct-by-construction GALS designs. We present formal definitions for the refinements towards different GALS architectures. For facilitating GALS in distributed embedded software, we analyze certain subclasses of synchronous designs using a Pomset-based semantic model that allows for desynchronization toward GALS. / Ph. D.

Codes from curves over finite fields were first developed in the late 1970's by V. D. Goppa and are known as algebraic geometry codes. Since that time, the construction has been tailored to fit particular applications, such as erasure recovery and error correction using less received information than in the classical case. The Hermitian-lifted code construction of L'opez, Malmskog, Matthews, Piñero-González, and Wootters (2021) provides codes from the Hermitian curve over $F_{q^2}$ which have the same locality as the well-known one-point Hermitian codes but with a rate bounded below by a positive constant independent of the field size. However, obtaining explicit expressions for the code is challenging. In this dissertation, we consider codes from norm-trace curves, which are a generalization of the Hermitian curve. We develop norm-trace-lifted codes and demonstrate an explicit basis of the codes. We then consider fractional decoding of codes from norm-trace curves, extending the results obtained for codes from the Hermitian curve by Matthews, Murphy, and Santos (2021). / Doctor of Philosophy / Coding theory focuses on recovering information, whether that data is corrupted and changed (called an error) or is simply lost (called an erasure). Classical codes achieve this goal by accessing all received symbols. Because long codes, meaning those with many symbols, are common in applications, it is useful for codes to be able to correct errors and recover erasures by accessing less information than classical codes allow. That is the focus of this dissertation. Codes with locality are designed for erasure recovery using fewer symbols than in the classical case. Such codes are said to have locality $r$ and availability $s$ if each symbol can be recovered from $s$ disjoint sets of $r$ other symbols. Algebraic curves, such as the Hermitian curve or the more general norm-trace curves, offer a natural structure for designing codes with locality. This is done by considering lines intersected with the curve to form repair groups, which are sets of $r+1$ points where the information from one point can be recovered using the rest of the points in the repair group. An error correction method which uses less data than the classical case is that of fractional decoding. Fractional decoding takes advantage of algebraic properties of the field trace to correct errors by downloading only a $lambda$-proportion of the received information, where $lambda < 1$. In this work, we consider a new family of codes resulting from norm-trace curves, and study their locality and availability, as well as apply the ideas of fractional decoding to these codes.

付記する学位プログラム名: 京都大学卓越大学院プログラム「先端光・電子デバイス創成学」 / 京都大学 / 新制・課程博士 / 博士(理学) / 甲第25103号 / 理博第5010号 / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)教授 柳瀬 陽一, 教授 石田 憲二, 准教授 北川 俊作 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Made available in DSpace on 2014-07-29T16:02:22Z (GMT). No. of bitstreams: 1 dissertacao karoline fernandes.pdf: 700169 bytes, checksum: bbcf93fe91f369b6605215c70576e124 (MD5) Previous issue date: 2010-02-26 / We will study the Finsler metric, on a manifold M, defined as the sum of a Riemannian metric and a 1-form, they are known as Randers metric. We will classify those that are locally dually flat, that is, for all point exists a coordinate system in which the equation of the geodesic has a special form, the coefficients of spray is given in terms of the metric one and a local scalar function, we will also characterize the Randers metric that is locally dually flat with almost isotropic flag curvature / Estudaremos as métricas de Finsler, em uma variedade M, definidas como soma de uma métrica Riemanniana e de uma 1-forma, elas são conhecidas como métricas de Randers. Classificaremos aquelas que são localmente dualmente flat, isto é, para todo ponto existe um sistema de coordenadas no qual a equação das geodésicas tem uma forma especial pois os coeficientes do spray são dados em termos da métrica e de uma função escalar, caracterizaremos também as métricas de Randers que são localmente dualmente flat com curvatura flag quase-isotrópica

Soient K un corps de nombres d'anneau des entiers O_K et G un groupe fini. Grâce à un résultat de E. Noether, l'anneau des entiers d'une extension galoisienne de K modérément ramifiée, de groupe de Galois G, est un O_K[G]-module localement libre de rang 1. Donc, à chaque extension galoisienne L/K modérément ramifiée, de groupe de Galois G, on peut associer une classe [O_L] dans le groupe des classes des modules localement libres Cl(O_K[G]). L'ensemble des classes de Cl(O_K[G]) qui peuvent être obtenues de cette façon est appelé ensemble des classes réalisables et on le note R(O_K[G]).Dans cette thèse, on étudie différents problèmes liés à R(O_K[G]). Dans la première partie, nous nous focalisons sur la question suivante: R(O_K[G]) est-il un sous-groupe de Cl(O_K[G])? Si G est abélien, L. McCulloh a prouvé que R(O_K[G]) coïncide avec le soi-disant sous-groupe de Stickelberger St(O_K[G]) dans Cl(O_K[G]). Dans le Chapitre 2, nous donnons une présentation détaillée d'un travail non publié de L. McCulloh qui étend la définition de St(O_K[G]) au cas non-abélien et montre que R(O_K[G]) est inclus dans St(O_K[G]) (l'inclusion opposée n'est pas encore connue dans le cas non-abélien). Puis, en utilisant sa définition et le Théorème de Stickelberger classique, nous montrons dans le Chapitre 3 que St(O_K[G]) est trivial si K=Q et G est soit un groupe cyclique d'ordre p soit un groupe diédral d'ordre 2p, avec p premier impair. Ceci, lié aux résultats de McCulloh, nous donne une nouvelle preuve de la trivialité de R(O_K[G]) dans les cas considérés.Les résultats originaux les plus importants sont contenus dans la deuxième partie de cette thèse. Dans le Chapitre 4 nous montrons la fonctorialité de St(O_K[G]) par rapport au changement du corps de base. Ceci implique que si N/L est une extension galoisienne modérément ramifiée, de groupe de Galois G, et St(O_K[G]) est connu être trivial pour un certain sous-corps K de L, alors O_N est un O_K[G]-module stablement libre.Dans le dernier chapitre, nous montrons un résultat concernant la distribution des classes réalisables parmi les extensions galoisiennes de K modérément ramifiées, de groupe de Galois G, dans lesquelles un idéal premier de K donné est totalement décomposé. / Let K be a number field with ring of integers O_K and let G be a finite group.By a result of E. Noether, the ring of integers of a tame Galois extension of K with Galois group G is a locally free O_K[G]-module of rank 1.Thus, to any tame Galois extension L/K with Galois group G we can associate a class [O_L] in the locally free class group Cl(O_K[G]). The set of all classes in Cl(O_K[G]) which can be obtained in this way is called the set of realizable classes and is denoted by R(O_K[G]).In this dissertation we study different problems related to R(O_K[G]).The first part focuses on the following question: is R(O_K[G]) a subgroup of Cl(O_K[G])? When the group G is abelian, L. McCulloh proved that R(O_K[G]) coincides with the so-called Stickelberger subgroup St(O_K[G]) of Cl(O_K[G]). In Chapter 2, we give a detailed presentation of unpublished work by L. McCulloh that extends the definition of St(O_K[G]) to the non-abelian case and shows that R(O_K[G]) is contained in St(O_K[G]) (the opposite inclusion is still not known in the non-abelian case).Then, just using its definition and Stickelberger's classical theorem, we prove in Chapter 3 that St(O_K[G]) is trivial if K=Q and G is either cyclic of order p or dihedral of order 2p, where p is an odd prime number. This, together with McCulloh's results, allows us to have a new proof of the triviality of R(O_K[G]) in the cases just considered.The main original results are contained in the second part of this thesis. In Chapter 4, we prove that St(O_K[G]) has good functorial behavior under restriction of the base field. This has the interesting consequence that, if N/L is a tame Galois extension with Galois group G, and St(O_K[G]) is known to be trivial for some subfield K of L, then O_N is stably free as an O_K[G]-module.In the last chapter, we prove an equidistribution result for Galois module classes amongst tame Galois extensions of K with Galois group G in which a given prime p of K is totally split.

On s'intéresse dans ce travail au problème de propagation acoustique dans des guides à parois traitées avec des matériaux absorbants à réaction localisée ou non localisée en présence d'écoulement. En effet, dans les systèmes industriels comme les turboréacteurs d'avions, les silencieux d'échappement et les systèmes de ventilation, le bruit est le plus souvent canalisé vers l'extérieur par des guides de géométries plus ou moins complexes. Une étude des guides d'ondes permet donc de prédire et de comprendre les phénomènes physiques tels que la réfraction, la convection, l'absorption et l'atténuation des ondes. Dans l'étude des guides d'ondes, on considère souvent qu'ils sont infiniment longs afin de s'affranchir de certains phénomènes (réflexion par exemple) à leurs extrémités. Résoudre le problème de propagation dans les guides infinis par la méthode des éléments finis nécessite de tronquer le domaine infini par des frontières artificielles sur lesquelles des conditions limites transparentes doivent être écrites. Dans ce travail, les conditions limites transparentes sont écrites sous forme d'un opérateur Dirichlet-to-Neumann (DtN) basé sur une décomposition de la pression acoustique sur la base des modes propres du guide étudié tout en prenant en compte l'influence des paramètres comme l'écoulement et le traitement acoustique avec des matériaux absorbants. La propagation acoustique dans le guide est régie par un modèle scalaire basé sur l'équation de Helmholtz et les matériaux absorbants utilisés sont des matériaux absorbants d'impédance locale Z et des matériaux poreux. Nous nous sommes intéressés en particulier aux matériaux poreux ? squelette rigide que l'on modélise par un fluide équivalent car la propagation acoustique dans ces matériaux est aussi gouvernée par l'équation de Helmholtz comme dans un milieu fluide. Des résultats d'étude de la propagation acoustique dans des guides rectilignes uniformes traités en présence d'un écoulement uniforme ont permis de valider la méthode développée pour tronquer les domaines infinis. L'étude a aussi été menée avec succés pour des guides non uniformes traités en présence d'un écoulement potentiel. / Our concern in this work is the problem of acoustic propagation in guides lined with locally or non locally reacting materials with the presence of mean fluid flow. In several industrial systems such as aircraft jet engines, mufflers exhaust and ventilation systems, noise is mostly channeled outside by guides of more or less complex geometries. A study of waveguides makes it possible to predict and understand the physical phenomena such as refraction, convection, absorption and wave attenuation. In waveguides studies, guides are often considered infinitely long to get rid of some phenomena (reflection for example) at their ends. Solving the problem of acoustic propagation in infinite guides by finite element method requires to truncate the infinite domain by artificial boundaries on which transparent boundary conditions must be written. In this work, the transparent boundary conditions are written as a Dirichlet-to-Neumann (DtN) operators based on sound pressure decomposition on the eigenmodes basis of the studied guide by taking into account the influence of parameters such as flow and acoustic liners in the guide walls. Acoustic propagation in the guide is governed by a model based on the scalar Helmholtz equation and the used liners are locally reacting materials of local impedance Z and porous materials. In this study, we focused particularly rigid porous materials modelized by an equivalent fluid because the acoustic propagation in these materials is also governed by the Helmholtz equation as in a fluid medium. Results of studies of acoustic propagation in uniform straight lined guides with a uniform flow allowed to validate the method developed to truncate infinite domains. The study was also done successfully for non uniform lined guides with a potential mean flow.

In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied geometric proximity structures. These graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Locally Gabriel Graphs(LGGs) were proposed. A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel graphs are planar graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these graphs for various parameters like edge complexity(the maximum number of edges in these graphs),size of an independent set and dilation. We show that computing an edge maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V). We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance graphs(UDGs) are well studied geometric graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these graphs is 2n−7 when all the points are in convex position. A bipartite graph is called an ordered bipartite graph when the vertex set in each partition has a total order on its vertices. We introduce a family of ordered bipartite graphs with restrictions on some paths called path restricted ordered bi partite graphs (PRBGs)and show that their study is motivated by LGGs and UDGs on convex point sets. We show that a PRBG can be extracted from the UDGs/LGGs on convex point sets. First, we characterize a special kind of paths in PRBGs called forward paths, then we study some structural properties of these graphs. We show that a PRBG on n vertices has O(nlogn) edges and the bound is tight. It gives an alternate proof of O(nlogn)upper bound for the maximum number of edges in UDGs/LGGs on convex point sets. We study PRBGs with restrictions to the length of the forward paths and show an improved bound on the edge complexity when the length of the longest forward path is bounded. Then, we study the hierarchical structure amongst these graphs classes. Notably, we show that the class of UDGs on convex point sets is a strict sub class of LGGs on convex point sets.