On the bijective colouring of Cantor trees based on transducers

Given a vertex colouring of the infinite n-ary Cantor tree with m colours ($n,m\ge 2$), the natural problem arises: may this colouring induce a bijective colouring of the infinite paths starting at the root, i.e., that every infinite m-coloured string is used for some of these paths but different paths are not coloured identically? In other words, we ask if the above vertex colouring may define a bijective short map between the corresponding Cantor spaces. We show that the answer is positive if and only if $n\ge m$, and provide an effective construction of the bijective colouring in terms of Mealy automata and functions defined by such automata. We also show that a finite Mealy automaton may define such a bijective colouring only in the trivial case, i.e. $m=n$.     

The adjacency-Jacobsthal-Hurwitz sequences in groups

In [3 Deveci, O., Aküzüm, Y. (in press). The adjacency-Jacobsthal-Hurwitz type numbers. Filomat. [Google Scholar]], Deveci and Aküzüm defined the adjacency-Jacobsthal-Hurwitz sequences of the first and second kind. In this work, firstly we produce the cyclic groups from the multiplicative orders of the generating matrices of the adjacency-Jacobsthal-Hurwitz sequences of the first and second kind when read modulo λ and we study the adjacency-Jacobsthal-Hurwitz sequences of the first and second kind modulo λ. Then, we give the relationship between the orders of the cyclic groups obtained and the periods of the adjacency-Jacobsthal-Hurwitz sequences of the first and second kind modulo λ. Further, we extend the adjacency-Jacobsthal-Hurwitz sequences of the first and second kind to groups and then we examine these sequences in the quaternion group Q₈ in detail.     

Generic sequences,transducers and multiplication of normal numbers

Existence of a topological joining between two subshiftsX andX′ defines a relation between points of the two. Supposex ∈X is generic for an invariant measureμ onX; when is a relatedx′ ∈X′ also generic for some corresponding measureμ′ onX′? We prove this property holds in several situations for bounded-to-one joinings: whenμ andμ′ are the measures with maximal entropy on intrinsically ergodicX andX′, and also whenμ has a unique preimage on the joining, a property for which several sufficient conditions are given. In the latter case it is also possible to prove that the nearer a point is to genericity with respect toμ, the nearer to genericity with respect toμ′ a related point is. Bounded-to-one joinings may be defined by nonambiguous rational transductions. This provides several applications, most of them in Number Theory. It is proven that transducers performing multiplication by integers have the suitable properties: this implies multiplication by a rational preserves near normality; so does addition of a rational. An application to Markov measures, and sufficient conditions for a transducer to map normality to the basep to normality to the basep′, p′≠p, are given.     

The signs of three-term recurrence sequences

In this note, we present two sufficient conditions for determining the signs of three-term recurrence sequences. In order to determine the signs of some sequences, by our method, it suffices to compute a constant number of terms at the beginning. For example, in order to prove the positivity of the central Delannoy number D(n), by our method, it just needs to know the recurrence relation of D(n) and the values of D(k) for 0≤k≤2. As applications, we determine the signs of some famous sequences.     

模糊无限状态自动机及其收敛性

到目前为止,我们所研究的模糊或非模糊的自动机都是有限状态自动机.然而,关于无限状态自动机的定义及它的稳定性和收敛性都没有被讨论过.本文中,我们使用离散的反馈神经网络及网络输出空间划分方法,同时,在梯度更新算法中使用伪梯度方法,给出了模糊无限状态自动机收敛到模糊有限状态自动机的证明.     

On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.     

Lower bounds for optimal alignments of binary sequences

In parametric sequence alignment, optimal alignments of two sequences are computed as a function of matches, mismatches and spaces, producing many different optimal alignments. In the two-parameter case, Gusfield et al shows that the number of distinct optimal alignment summaries for a pair of sequences is O(n^2/3). Here we construct binary sequences of length n with 3/(2^7/3π^2/3)n^2/3+O(n^1/3logn) distinct optimal alignment summaries. This shows that the upper bound given by Gusfield et al. is tight over all alphabets, thereby disproving the “ conjecture”. Thus the maximum number of distinct optimal alignment summaries over all pairs of length n sequences is Θ(n^2/3).     

A note on the existence of sequences with small star discrepancy

It was shown by Heinrich et al. [The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001) 279–302] that there exist point sets for which the inverse of the star discrepancy depends linearly on the dimension. In this paper we extend those results by showing that there exist point sets extensible in the modulus and the dimension for which the star discrepancy satisfies a tractability bound for all dimensions and moduli.     

Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study

The permutation flowshop scheduling problem has been thoroughly studied in recent decades, both from single objective as well as from multi-objective perspectives. To the best of our knowledge, little has been done regarding the multi-objective flowshop with Pareto approach when sequence dependent setup times are considered. As setup times and multi-criteria problems are important in industry, we must focus on this area. We propose a simple, yet powerful algorithm for the sequence dependent setup times flowshop problem with several criteria. The presented method is referred to as Restarted Iterated Pareto Greedy or RIPG and is compared against the best performing approaches from the relevant literature. Comprehensive computational and statistical analyses are carried out in order to demonstrate that the proposed RIPG method clearly outperforms all other algorithms and, as a consequence, it is a state-of-art method for this important and practical scheduling problem.     

Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times

This paper presents an enhanced migrating bird optimization (MBO) algorithm and a new heuristic for solving a scheduling problem. The proposed approaches are applied to a permutation flowshop with sequence dependent setup times and the objective of minimizing the makespan. In order to augment the MBOs intensification capacity, an original problem specific heuristic is introduced. An adapted neighborhood, a tabu list, a restart mechanism and an original process for selecting a new leader also improved the MBO’s behavior. Using benchmarks from the literature, the resulting enhanced MBO (EMBO) gives state-of-the-art results when compared with other algorithms reference. A statistical analysis of the numerical experiments confirms the relative efficiency and effectiveness of both EMBO and the new heuristic.     

树按Balaban指标的排序(英文)

连通图G的Balaban指标(也称J指标)定义为J=J(G)=(|E(G)|)/μ+1∑_(uυ∈E(G)),其中σ_G(u)=∑(w∈V(G)d_G(u,w)此处μ是基圈数.Balaban指标常用于各种QSAR和QSPR的研究.本文根据Balaban指标的计算公式及文中提到的变换方式,我们得到了一些序关系.基于这些序关系,我们确定了n个顶点的树中具有最小Balaban指标的前21个树.     

Ordering trees by algebraic connectivity

LetG be a graph onn vertices. Denote byL(G) the difference between the diagonal matrix of vertex degrees and the adjacency matrix. It is not hard to see thatL(G) is positive semidefinite symmetric and that its second smallest eigenvalue,a(G) > 0, if and only ifG is connected. This observation led M. Fiedler to calla(G) thealgebraic connectivity ofG. Given two trees,T ₁ andT ₂, the authors explore a graph theoretic interpretation for the difference betweena(T ₁) anda(T ₂).Research supported by ONR contract 85K0335     

On self-matching within integer part sequences

With α irrational the graph of [jα] against integer j, displays interesting patterns of self-matching. This is best seen by comparing the Bernoulli (characteristic Sturmian) or difference sequence 〈β_j〉, term by term with the Bernoulli sequence displaced by k terms 〈β_j−k〉, where

β_j=[(j+1)α]−[jα].     

Ordering trees by their spectral radii

Let T be a tree with n vertices and let A（T） be the adjacency matrix of T. Spectral radius of T is the largest eigenvalue of A（T）. Wu et al. [Wu, B.F., Yuan, X.Y, and Xiao, E.L. On the spectral radii of trees, Journal of East China Normal University （Natural Science）, 3：22-28 （2004）] determined the first seven trees of order n with the smallest spectral radius. In this paper, we extend this ordering by determining the trees with the eighth to the tenth smallest spectral radius among all trees with n vertices.     

Ordering trees by the Laplacian coefficients

Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients.     

Ordering distributions by scaled order statistics

Motivated by applications in reliability theory, we define a preordering (X ₁, ...,X _n) (Y ₁ ...,Y _n) of nonnegative random vectors by requiring thek-th order statistic ofa ₁ X ₁,..., a _n X _n to be stochastically smaller than thek-th order statistic ofa ₁ Y ₁, ...,a _n Y _n for all choices ofa _i >0,i=1, 2, ...,n. We identify a class of functionsM _{k, n} such that if and only ifE(X)E(Y) for allM _k,n. Some preservation results related to the ordering are obtained. Some applications of the results in reliability theory are given.Supported by the Air Force Office of Scientific Research, U.S.A.F., under Grant AFOSR-84-0205.     

Ordering Web Pages by Cross-Link Information

We construct an ordered family of web pages that allow for the canonical structure of the link matrix. The multirelation method is applied to obtain a restriction of this family and to investigate the kind of orderings that arise. A new interpretation of the link matrix is proposed, reducing the number of equivalence classes in its canonical form. The discussion is illustrated with some prototype examples. __________ Translated from Prikladnaya Matematika i Informatika, No. 18, pp. 93–107, 2004.