Preface

The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L∩R) where h is a morphism, R is a regular language and L is the maximal solution of an equation $\text{?(X) = g(X)}$, where ? is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.     

Riordan 矩阵在广义 Motzkin 路计数中的应用

用Riordan矩阵的方法研究了具有4种步型的加权格路(广义Motzkin路)的计数问题,引入了一类新的计数矩阵,即广义Motzkin矩阵.同时给出了这类矩阵的Riordan表示,也得到了广义Motzkin路的计数公式.Catalan矩阵,Schrder矩阵和Motzkin矩阵都是广义Motzkin矩阵的特殊情形.     

Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

Some primitives for the portable programming of array and vector processors

A high-level language for array and vector processors is analyzed by the methods of denotational semantics. The analysis leads to the identification of a set of primitives suitable for the portable programming of array and vector processors. Discussion of the primitives includes consideration of the efficiency with which they may be implemented on different machines, and their possible application to portable programming, the design of intermeiate languages, and the design of future array and vector processors.     

带有非局部边界条件的反应——扩散方程组解的全局存在性

研究一类带有非局部边界条件的抛物型方程组解的全局存在性.主要通过构造迭代序列,利用比较原理得到定理的证明.     

Skew‐Hadamard matrices of orders 436, 580, and 988 exist

We construct two difference families on each of the cyclic groups of order 109, 145, and 247, and use them to construct skew‐Hadamard matrices of orders 436, 580, and 988. Such difference families and matrices are constructed here for the first time. The matrices are constructed by using the Goethals‐Seidel array. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 493–498, 2008     

Linear hash families and forbidden configurations

The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) ∈ {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.      

A new multi-criteria approach dealing with dependent and heterogeneous criteria for end-of-life product strategy

Strict regulations, technological growth and environmental impacts are influent factors in the choice of the best strategy for end-of-life (EOL) product. In fact, EOL is one stage of the life cycle having gained the attention of the market.This study proposes an integrated methodology that relies on multi-criteria analysis and takes into account both quantitative and qualitative criteria while respecting mutual interactions between them. This has been performed by introducing, on the one hand, the 2-tuple linguistic representation model dealing with non-homogeneous information data, and on the other hand, the Choquet integral interaction modeling between criteria into the PROMETHEE method. Although it has been developed for EOL selection problems, the proposed method fits to all kinds of decision-making problems with heterogeneous information. As this work demonstrates, this multi-criteria analysis approach can offer a technical-scientific decision making support tool in the EOL product sector. We also perform a sensitivity to reveal the effect of the subjective parameter variations on the originally resulted ranking.     

Lattice embeddings and array noncomputable degrees

We focus on a particular class of computably enumerable (c. e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering (??, ≤) of c. e. degrees under Turing reducibility. We demonstrate that the latticeM₅ cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M₅ can be embedded below every nonlow₂ degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow₂ degrees. We note also that there are embeddings of M₅ in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

低回收价值高环境影响EOL产品闭环供应链模型构建

以EOL产品循环利用为研究对象,定量分析低回收价值高环境影响EOL产品回收决策问题。通过构建EOL产品双闭环供应链和多闭环供应链模型,求解了各模型的EOL产品回收策略,并与传统单闭环供应链进行对比分析,证明了该闭环供应链优于传统单闭环供应链。研究发现,在政府监督和补贴强度不变、市场外部变量相同的条件下,多闭环供应链的EOL产品回收量更大,循环利用更充分,且随着多闭环供应链外循环次数的增加,EOL产品回收量、回收商利润均增加,内循环制造商利润也相应增加,销售商利润不受影响。最后,对构建的多闭环供应链进行了算例分析,验证了上述研究结论。为政府运用监督和补贴手段更好地配置市场资源提供决策参考。     

Array P systems with permitting features

The biologically inspired model, known as P system, has proved to be a general framework for investigating several problems related to computing in different fields. Two-dimensional picture array languages is one such area in which different kinds of P systems have been constructed for picture array generation. Incorporating the feature of permitting symbols in the rules, a new variety of array P system is constructed here for generating picture languages consisting of picture arrays. The advantage of this approach is that there is a reduction in the number of membranes used in the construction, in comparison to the existing array P system models.     

A novel heuristic approach to determine compromise management for end-of-life electronic products

The European Union directive of Waste Electrical and Electronic Equipment for recycling end-of-life (EOL) products has had a significant impact on global enterprises. Recent studies have shed light on optimization of the EOL process. In addition to identifying the most economical EOL process, identifying the EOL process with the smallest environmental load is equally important, and this is thus a bi-criteria optimization problem. This study attempts to optimize EOL processes for electronic products based on a three-stage heuristic approach, which simultaneously minimizes cost and environmental impact. The proposed heuristic approach then assesses the most common disassembly and recycling processes by using the characteristics of electronic product recycling. Next, the best process for this bi-criteria optimization problem is identified by using the compromise programming method. The empirical analysis is based on data for notebook, and the potential impact on best EOL processes when notebook adopt new product designs is also discussed.     

A generalization of finiteness

We explore an analogy between the family ₁, of finite/cofinite languages and the family ₁ of languages whose syntactic monoids are J-trivial. It is shown that (a) J-trivial monoids, (b)L-trivial monoids, (c) R-trivial monoids, and (d) a recently studied family, that we callK, of aperiodic monoids are natural generalization of the families of syntactic semigroups of (a) finite/cofinite languages, (b) definite languages, (c) reverse definite languages, and (d) generalized definite languages, respectively. In the case of alphabets of one and two letters, the languages corresponding to the familyK of monoids are characterized, illustrating the above-mentioned analogy explicitly.This work was done partly at the University of Paris VI and VII under the scientific exchange program between Canada and France, and partly at the Institut für Rechner- und Programmstrukturen, Gesellschaft für Mathematik und Datenverarbeitung mbH. Bonn, Germany.     

Roux-type constructions for covering arrays of strengths three and four

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. Recursive constructions for covering arrays of strengths 3 and 4 are developed, generalizing many “Roux-type” constructions. A numerical comparison with current construction techniques is given through existence tables for covering arrays.      

Generalised Cumulative Arrays in Secret Sharing

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.     

Products of mixed covering arrays of strength two

A covering array CA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006     

达到极大线性复杂度的前馈阵列

讨论了三类达到极大线性复杂度的前馈阵列的输入阵列的结构。一类是达到极大线性复杂度的乘积前馈阵列,完全确定了其输入阵列的结构;给出了两类输入阵列,证明了它们的任意前馈阵列达到极大线性复杂度。     

Riordan 矩阵的$(m,r,s)$-Halves

Riordan矩阵的垂直一半和水平一半已经被许多学者分别研究过.本文给出了Riordan矩阵的$(m,r,s)$-halves的定义.利用此定义能够统一的讨论Riordan矩阵的垂直一半和水平一半.作为应用,通过对Pascal和Delannoy矩阵的$(m,r,s)$-halves的研究,可以得到了一些与Fibonacci, Pell和Jacobsthal序列相关的等式.     

An identity of Andrews and a new method for the Riordan array proof of combinatorial identities

We consider an identity relating Fibonacci numbers to Pascal's triangle discovered by G.E. Andrews. Several authors provided proofs of this identity, most of them rather involved or else relying on sophisticated number theoretical arguments. We present a new proof, quite simple and based on a Riordan array argument. The main point of the proof is the construction of a new Riordan array from a given Riordan array, by the elimination of elements. We extend the method and as an application we obtain other identities, some of which are new. An important feature of our construction is that it establishes a nice connection between the generating function of the A-sequence of a certain class of Riordan arrays and hypergeometric functions.