Primitivity and Local Primitivity of Digraphs and Nonnegative Matrices

The article surveys the main results on the primitivity and local primitivity of digraphs and matrices from the inception of this research area in 1912 by now. We review the universal and special criteria for primitivity and local primitivity as well as universal and special bounds on the exponents and local exponents of digraphs and matrices. We describe some cryptographic applications of this mathematical apparatus for analyzing the mixing properties of block ciphers and keystream generators. The new promising research directions are formulated in the study of primitivity and local primitivity of digraphs and matrices.     

Mixing properties of modified additive generators

We develop amatrix-graph approach to estimating themixing properties of bijective shift registers over a set of binary vectors. Such shift registers generalize, on the one hand, the class of ciphers based on the Feistel network and, on the other hand, the class of transformations of additive generators (the additive generators are the base for the Fish, Pike, andMush algorithms). It is worth noting that the original schemes of additive generators are found insecure due to their weak mixing properties. The article contains the results of investigations for the mixing properties of modified additive generators. For the mixing directed graph of a modified additive generator, we define the sets of arcs and cycles, obtain primitivity conditions, and give a bound for the exponent. We show that, the determination of parameters for the modified additive generator allows us to achieve a full mixing in a number of iterations that is substantially less than the number of vertices in the mixing digraph.     

The Theory of SML Schema-Directed Query

SML is a modeling language for the structured modeling framework, which represents the semantics as well as the mathematical structure of a model. This paper uses an SML approach to improve the object based universal relation data model. By this approach, both the relational structure of a database and the objects in relations are automatically derived by the associated SML schema. The interpretation part of an SML schema allows users to easily learn the meanings of the data before performing universal relation queries; the queries are then computed by using the automatically derived objects. With a goal of making queries simpler, this paper presents theories, table naming conventions, a confirmation approach, and a unified example illustrating many different concepts. It helps lay the foundation for the eventual development of a remarkably easy user interface for ad hoc query in computer-based modeling systems. We are hopeful that the results may in the future contribute to real applications in databases as well as in management science/operations research.     

Global Properties of Kovalevskaya Exponents

This paper contains a collection of properties of Kovalevskaya exponents which are eigenvalues of a linearization matrix of weighted homogeneous nonlinear systems along certain straight-line particular solutions. Relations in the form of linear combinations of Kovalevskaya exponents with nonnegative integers related to the presence of first integrals of the weighted homogeneous nonlinear systems have been known for a long time. As a new result other nonlinear relations between Kovalevskaya exponents calculated on all straight-line particular solutions are presented. They were obtained by an application of the Euler–Jacobi–Kronecker formula specified to an appropriate n-form in a certain weighted homogeneous projective space.     

Computing special powers in finite fields

We study exponentiation in nonprime finite fields with very special exponents such as they occur, for example, in inversion, primitivity tests, and polynomial factorization. Our algorithmic approach improves the corresponding exponentiation problem from about quadratic to about linear time.

     

Necessary and sufficient conditions for a graph to be three-terminal series-parallel-cascade

A “three-terminal series-parallel-cascade graph” is defined as a three-terminal graph which is constructed by means of cascade connections in addition to series and parallel connections which were used in constructing a three-terminal series-parallel graph in our previous paper. Some properties of the graph are presented, and a theorem of the Kuratowski type is given stating that a three-terminal nonseparable graph is three-terminal series-parallel-cascade if and only if none of certain three graphs can be obtained from it by opening or shorting some of the edges. This theorem characterizes a three-terminal series-parallel-cascade graph completely, and clarifies its structual limitation.     

Possibility-theoretic extension of derivation operators in formal concept analysis over fuzzy lattices

Formal concept analysis (FCA) associates a binary relation between a set of objects and a set of properties to a lattice of formal concepts defined through a Galois connection. This relation is called a formal context, and a formal concept is then defined by a pair made of a subset of objects and a subset of properties that are put in mutual correspondence by the connection. Several fuzzy logic approaches have been proposed for inducing fuzzy formal concepts from L-contexts based on antitone L-Galois connections. Besides, a possibility-theoretic reading of FCA which has been recently proposed allows us to consider four derivation powerset operators, namely sufficiency, possibility, necessity and dual sufficiency (rather than one in standard FCA). Classically, fuzzy FCA uses a residuated algebra for maintaining the closure property of the composition of sufficiency operators. In this paper, we enlarge this framework and provide sound minimal requirements of a fuzzy algebra w.r.t. the closure and opening properties of antitone L-Galois connections as well as the closure and opening properties of isotone L-Galois connections. We apply these results to particular compositions of the four derivation operators. We also give some noticeable properties which may be useful for building the corresponding associated lattices.     

The combinatorics of Coxeter categories

We present an alternative construction of Soergel's category of bimodules associated to a reflection faithful representation of a Coxeter system. We show that its objects can be viewed as sheaves on the associated moment graph. We introduce an exact structure and show that Soergel's ``special' bimodules are the projective objects. Then we construct the indecomposable projectives by both a global and a local method, discuss a version of the Kazhdan-Lusztig conjecture and prove it for universal Coxeter systems.

     

Concepts and Perceptual Belief: How (Not) to Defend Recognitional Concepts

Recognitional concepts have the following characteristic property: thinkers are disposed to apply them to objects merely on the basis of undergoing certain perceptual experiences. I argue that a prominent strategy for defending the existence of constitutive connections among concepts, which appeals to thinkers’ semantic-cum-conceptual intuitions, cannot be used to defend the existence of recognitional concepts. I then outline and defend an alternative argument for the existence of recognitional concepts, which appeals to certain psychological laws.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

Primitive matrices over polynomial semirings

An extension of the definition of primitivity of a real nonnegative matrix to matrices with univariate polynomial entries is presented. Based on a suitably adapted notion of irreducibility an analogue of the classical characterization of real nonnegative primitive matrices by irreducibility and aperiodicity for matrices with univariate polynomial entries is given. In particular, univariate polynomials with nonnegative coefficients which admit a power with strictly positive coefficients are characterized. Moreover, a primitivity criterion based on almost linear periodic matrices over dioids is presented.     

Smash Product， Morita Context Rings and Extended Centroids

ＳｍａｓｈＰｒｏｄｕｃｔ，ＭｏｒｉｔａＣｏｎｔｅｘｔＲｉｎｇｓａｎｄＥｘｔｅｎｄｅｄＣｅｎｔｒｏｉｄｓ￥ＹａｎｇＳｈｉｌｉｎ杨士林（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＢｅｉｊｉｎｇＣｏｍｐｕｔｅｒＩｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ，１０...     

Isoperimetric inequalities in simplicial complexes

In graph theory there are intimate connections between the expansion properties of a graph and the spectrum of its Laplacian. In this paper we define a notion of combinatorial expansion for simplicial complexes of general dimension, and prove that similar connections exist between the combinatorial expansion of a complex, and the spectrum of the high dimensional Laplacian defined by Eckmann. In particular, we present a Cheeger-type inequality, and a high-dimensional Expander Mixing Lemma. As a corollary, using the work of Pach, we obtain a connection between spectral properties of complexes and Gromov’s notion of geometric overlap. Using the work of Gundert and Wagner, we give an estimate for the combinatorial expansion and geometric overlap of random Linial-Meshulam complexes.     

Volume entropy,weighted girths and stable balls on graphs

We prove new isoperimetric inequalities on graphs involving quantities linked with concepts from differential geometry. First, we bound from above the product of the volume entropy (defined as the log of the exponential growth rate of the universal cover) and the girth of weighted graphs in terms of their cyclomatic number. In a second part, we study a natural polyhedron associated to a weighted graph: the stable ball. In particular, we relate the volume of this polyhedron, the weight of the graph and its cyclomatic number. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 291–305, 2007     

Supereulerian graphs: A survey

A graph is supereulerian if it has a spanning eulerian subgraph. There is a rduction method to determine whether a graph is supereulerian, and it can also be applied to study other concepts, e.g., hamiltonian line graphs, a certain type of double cycle cover, and the total interval number of a graph. We outline the research on supereulerian graphs, the reduction method, and its applications.     

A multi-objective modeling approach for energetic material evaluation decisions

To develop ordnance for military applications requires a decision process of selecting materials. Once selected a performance evaluation of the material composite formulations energetic properties is required. Tailoring the composite materials for a particular ordnance application requires selecting reactants that seek an optimized combination of economic costs and performance properties (e.g., energy release, temperature, and gas generation). A successful energetic material evaluation must identify reactants offering a good fit with performance requirements and an overall materials selection strategy. To aid energetic material users in making complex reactant selection decisions we introduce a modeling approach that combines the concepts of thermodynamics, economic costs, and goal programming. This study is unique in its application of goal programming in exploring this type of decision situation. A case study is used to illustrate the modeling approach. The results demonstrate the efficacy of the approach for evaluating formulations where performance properties are important.     

Bipartite graphs and completely 0-simple semigroups

In a manner similar to the construction of the fundamental group of a connected graph, this article introduces the construction of a fundamental semigroup associated with a bipartite graph. This semigroup is a 0-direct union of idempotent generated completely 0-simple semigroups. The maximal nonzero subgroups are the corresponding fundamental groups of the connected components. Adding labelled edges to the graph leads to a more general completely 0-simple semigroup. The basic properties of such semigroups are examined and they are shown to have certain universal properties as illustrated by the fact that the free completely simple semigroup on n generators and its idempotent generated subsemigroup appear as special cases.     

ASSESSMENT OF LOCAL INFLUENCE IN MULTIVARIATE ANALYSIS

ＡＳＳＥＳＳＭＥＮＴＯＦＬＯＣＡＬＩＮＦＬＵＥＮＣＥＩＮＭＵＬＴＩＶＡＲＩＡＴＥＡＮＡＬＹＳＩＳ￥（石磊，王学仁）ＳｈｉＬｅｉ；ＷａｎｇＸｕｅｒｅｎ（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓｏｆＹｕｎｎａｎＰｒｏｖｉｎｃｅＤｅｐａｒ...     

Formalization of a synthesis problem and methods for its solution

A formal formulation is proposed for the synthesis problem of finding objects with certain properties described only by a collection of precedents. A key feature of this formalization is that it is closely related to the pattern recognition theory. A general approach to solving the synthesis problem is described, and particular solution methods are presented in two important cases. For this purpose, a new recognition method is proposed that exhibits a high speed as applied to the data of the structure under study. The performance of the methods is demonstrated on actual data.