CHEVIE — A system for computing and processing generic character tables

CHEVIE is a computer algebra package which collects data and programs for the representation theory of finite groups of Lie type and associated structures. We explain the theoretical and conceptual background of the various parts of CHEVIE and we show the usage of the system by means of explicit examples. More precisely, we have sections on Weyl groups and Iwahori-Hecke algebras, generic character tables of series of finite groups of Lie type, and cyclotomic algebras.The authors Frank Lübeck and Götz Pfeiffer acknowledge financial support by the Deutsche Forschungsgemeinschaft.     

State splitting,strong shift equivalence and stable isomorphism of Cuntz–Krieger algebras

We prove that if two nonnegative matrices are strong shift equivalent, the associated stable Cuntz–Krieger algebras with generalized gauge actions are conjugate. The proof is done by a purely functional analytic method and based on constructing imprimitivity bimodule from bipartite directed graphs through strong shift equivalent matrices, so that we may clarify K-theoretic behaviour of the stable isomorphism between the associated stable Cuntz–Krieger algebras. We also examine our machinery for the matrices obtained by state splitting graphs, so that topological conjugacy of the topological Markov shifts is described in terms of some equivalence relation of the Cuntz–Krieger algebras with canonical masas and the gauge actions without stabilization.     

Computing Levi Decompositions in Lie algebras

 We consider the algorithmic problem of computing Levi decompositions in Lie algebras and Wedderburn–Malcev decompositions in associative algebras over the field of rational numbers. We propose deterministic polynomial time algorithms for both problems. The methods are based on the corresponding classical existence theorems. Computational experiences are discussed at the end of the paper. Received: October 24, 1995; revised version: May 28, 1996     

R_0代数的可证等价类

讨论了R0代数的滤子以及相应的可证等价类.在R0代数里给出了一些滤子的具体例子,得到:F是R0代数M的超滤当且仅当F是M的固执滤子;当F是R0代数的蕴涵滤子时,M/F是布尔代数;当F是R0代数的极大布尔滤子时,M/F是只有两个元的布尔代数.     

验证高层综合操作流图等价性的一种有效形式方法

根据当前高层综合系统不跨越控制边界进行代码移动的特点,提出了临界路径的概念,将行为规范与RTL实现的操作流图分解成模型检查工具可以接受的验证目标。为了便于自动验证高层综合过程,给出了验证自动机模型。实验结果表明,应用该方法．可简化状态空间,得到更高的验证效率,并保证规范与RTL实现的一致性。     

Graph algebras and the graph isomorphism problem

We consider the families of matrix algebras over C associated with graphs. Restricting the multiplicity of the irreducible representations over C produces corresponding classes of graphs. The main result of the paper is a polynomial-time algorithm for recognizing the isomorphism of graphs from these classes. It is a generalization of the well-known Babai-Grigor'ev-Mount algorithm for testing the isomorphism of graphs with bounded eigenvalue multiplicity.     

Effective algorithms for parametrizing linear control systems over Ore algebras

In this paper, we study linear control systems over Ore algebras. Within this mathematical framework, we can simultaneously deal with different classes of linear control systems such as time-varying systems of ordinary differential equations (ODEs), differential time-delay systems, underdetermined systems of partial differential equations (PDEs), multidimensional discrete systems, multidimensional convolutional codes, etc. We give effective algorithms which check whether or not a linear control system over some Ore algebra is controllable, parametrizable, flat or π-free. This paper is dedicated to the memory of our dear friend and colleague Manuel Bronstein. The third author has been financially supported by the Control Training Site grant HPMT-CT-2001-00278 and the Deutsche Forschungsgemeinschaft during his stays at INRIA Sophia Antipolis.     

基于量子逻辑的几类有穷自动机之间的关系

根据初始状态和终止状态是否为分明的,非确定型量子有穷自动机可分为四类,确定型量子有穷自动机可分为三类.本文详细讨论了四类非确定型量子有穷自动机之间的关系以及三类确定型量子有穷自动机之间的关系,并且利用新的构造方法,证明了初态为分明的确定型量子有穷自动机与终态为分明的确定型量子有穷自动机是等价的.这些结论为实际应用中计算模型的合理选取提供了理论依据.     

MTL代数的蕴涵滤子与正蕴涵滤子

在MTL代数M上引入了蕴涵滤子、正蕴涵滤子的概念,研究了它们的性质,给出了M的非空子集成为蕴涵滤子及正蕴涵滤子的充要条件和M的蕴涵滤子成为正蕴涵滤子的充要条件.讨论了蕴涵滤子与正蕴涵滤子的关系,得到了M的每一个正蕴涵滤子都是蕴涵滤子,但反之不真.     

Converting a büchi alternating automaton to a usual nondeterministic one

We first give a method for simulating, in the case of Büchi, an alternating automaton by a usual nondeterministic one. Then, to make the satisfiability problem of Linear Propositional Temporal Logic (LPTL) use this result, we give a method for translating any formula of this logic into an equivalent Büchi alternating automaton. I am indebted to my thesis advisor Professor Ahmed SAOUDI, who has been a major contributor to this work. He passed away on August 11, 1993.     

On the Finiteness of Gröbner Bases Computation in Quotients of the Free Algebra

We investigate, for quotients of the non-commutative polynomial ring, a property that implies finiteness of Gr?bner bases computation, and examine its connection with Noetherianity. We propose a Gr?bner bases theory for our factor algebras, of particular interest for one-sided ideals, and show a few applications, e.g. how to compute (one-sided) syzygy modules. Received: September 29, 1999; revised version: October 25, 2000     

A cellular automaton for segregation during granular avalanches

Segregation is a complex and poorly understood phenomenon that is prevalent in many industrial and natural granular flows. When grains flow down a slope [1–5], are spun in a rotating drum [6–8] or shaken in a box [9], we observe those grains organising into intriguing patterns. Kinetic sieving is the dominant mode of segregation in granular avalanches, where separation of particles occurs according to size. Using a cellular automaton we have modelled kinetic sieving as the swapping of particles in a one-dimensional system. From the cellular automaton we have deduced a continuum model to describe the segregation.     

Image Denoising with Adaptive Weighted Graph Filtering

Graph filtering, which is founded on the theory of graph signal processing, is proved as a useful tool for image denoising. Most graph filtering methods focus on learning an ideal lowpass filter to remove noise, where clean images are restored from noisy ones by retaining the image components in low graph frequency bands. However, this lowpass filter has limited ability to separate the low-frequency noise from clean images such that it makes the denoising procedure less effective. To address this issue, we propose an adaptive weighted graph filtering (AWGF) method to replace the design of traditional ideal lowpass filter. In detail, we reassess the existing low-rank denoising method with adaptive regularizer learning (ARLLR) from the view of graph filtering. A shrinkage approach subsequently is presented on the graph frequency domain, where the components of noisy image are adaptively decreased in each band by calculating their component significances. As a result, it makes the proposed graph filtering more explainable and suitable for denoising. Meanwhile, we demonstrate a graph filter under the constraint of subspace representation is employed in the ARLLR method. Therefore, ARLLR can be treated as a special form of graph filtering. It not only enriches the theory of graph filtering, but also builds a bridge from the low-rank methods to the graph filtering methods. In the experiments, we perform the AWGF method with a graph filter generated by the classical graph Laplacian matrix. The results show our method can achieve a comparable denoising performance with several state-of-the-art denoising methods.     

完全图的剖分图的线图的谱

如果一个图G的邻接矩阵A(G)的特征多项式的所有特征值全为整数,则称图G是整的.设图L2(Kp):L(s(Kp))是完全图Kp的剖分图S(Kp)的线图.在这篇文章里,我们利用图的理论给出了S(Kp)和L2(Kp)的特征多项式及其谱.对于图L2(Kp),得到了其补图、线图、线图的补图及补图的线图的特征多项式.也证明了这些图都是整图.这些整图的发现是对整图的研究的一个新贡献.     

增加结构非循环模糊自动机最小化算法

我们提出了一种新的不完全的增加结构算法,该算法结合了非循环确定模糊自动机的性质。由于该算法与隶属度有关,因此算法给出了与传统方法不同的运算函数,而且通过构造模拟状态使该算法可在有多输入状态的条件下运行。所以这个新的不完全增加结构算法较传统算法更可行和实用。新算法由两部分构成:增加模糊字符串到最小非循环确定模糊自动机和最小化增加模糊字符串后得到的自动机。因为在增加模糊字符串到最小非循环确定模糊自动机的过程中,运用了一些相关的新函数,所以得到的自动机仍然是确定的,而且没有增加任何无关的字符串到自动机的可识别语言。     

复对合Banach代数态的刻划

Gaur(1998)提出并利用g-有界泛函刻划任意复合对Banach代数，但对这类泛函的性质刻划甚少，详细讨论了其具有一些重要性质。     

A combinatorial approach to involution and δ-regularity I: involutive bases in polynomial algebras of solvable type

Involutive bases are a special form of non-reduced Gröbner bases with additional combinatorial properties. Their origin lies in the Janet–Riquier theory of linear systems of partial differential equations. We study them for a rather general class of polynomial algebras including also non-commutative algebras like those generated by linear differential and difference operators or universal enveloping algebras of (finite-dimensional) Lie algebras. We review their basic properties using the novel concept of a weak involutive basis and present concrete algorithms for their construction. As new original results, we develop a theory for involutive bases with respect to semigroup orders (as they appear in local computations) and over coefficient rings, respectively. In both cases it turns out that generally only weak involutive bases exist.     

Towards the simplest hydrodynamic lattice-gas model

It has been known since 1986 that it is possible to construct simple lattice-gas cellular automata whose hydrodynamics are governed by the Navier-Stokes equations in two dimensions. The simplest such model heretofore known has six bits of state per site on a triangular lattice. In this work, we demonstrate that it is possible to construct a model with only five bits of state per site on a Kagome lattice. Moreover, the model has a simple, deterministic set of collision rules and is easily implemented on a computer. In this work, we derive the equilibrium distribution function for this lattice-gas automaton and carry out the Chapman-Enskog analysis to determine the form of the Navier-Stokes equations.     

Multi‐modal parameter identification by automata approach

Abstract

In this paper, we consider the multi‐modal function optimization problem. An automata model with improved learning schemes is proposed to solve the global optimization problem. Theoretically, we prove that the automaton converges to the global optimum with a probability arbitrarily close to 1. The numerical simulation results show that the automata approach is better than both the well‐known gradient approach and the simulated annealing method. The simulation results also show that our automata model converges faster than the other existing models in the literature.     

具有最小距离拉普拉斯谱半径的双圈图（英）

一个连通图的距离拉普拉斯矩阵的最大特征值称为这个图的距离拉普拉斯谱半径．本文中,我们先得到距离拉普拉斯谱半径的一个好的下界,然后利用这个下界确定了单圈图中具有最小距离拉普拉斯谱半径的唯一极图．最后,再次利用这个下界,并结合距离拉普拉斯矩阵的特征多项式确定出了双圈图中具有最小距离拉普拉斯谱半径的极图．