Phase Transition in Vertex-Reinforced Random Walks on {\mathbb{Z}} with Non-linear Reinforcement

Vertex-reinforced random walk is a random process which visits a site with probability proportional to the weight w _k of the number k of previous visits. We show that if w _k ∼ k ^α, then there is a large time T ₀ such that after T ₀ the walk visits 2, 5, or ∞ sites when α < 1, = 1, or > 1, respectively. More general results are also proven.      

关于PFI-代数与剩余格

本文提出了一种强FI代数-PFI代数,并且深入研究了它的性质,借此进一步揭示了FI-代数和剩余格之间更加密切的联系,进而以FI-代数为基本框架建立了R0-代数、正则剩余格等逻辑系统的结构特征(包括对隅结构)及其相互关系．这种以FI-代数为基础来统一处理剩余格和R0-代数的方法,同样适合于格蕴涵代数和MV代数等代数结构,而且从中更能清楚地看出它们之间的密切联系,也将有助于对相应形式逻辑系统与模糊推理的研究．     

On-line arbitrarily vertex decomposable trees

A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ. An on-line version of the problem of characterizing arbitrarily vertex decomposable trees is completely solved here.     

Semiconvergence in distribution of random closed sets with application to random optimization problems

The paper considers upper semicontinuous behavior in distribution of sequences of random closed sets. Semiconvergence in distribution will be described via convergence in distribution of random variables with values in a suitable topological space. Convergence statements for suitable functions of random sets are proved and the results are employed to derive stability statements for random optimization problems where the objective function and the constraint set are approximated simultaneously. The author is grateful to two anonymous referees for helpful suggestions.     

随机环境中多物种分枝随机游动

引进了随机环境中多物种分枝随机游动的一般模型.在分枝过程非灭绝的情况下,讨论了系统的状态分类,得到了系统暂留及强常返的充要条件是存在k个定义在整数集上的函数分别满足某种性质.最后给出了系统强暂留的充分条件.     

Magnetic behavior of the bond random mixed compound FE(BR x I1−x )2(x = 0.9) with Mössbauer spectroscopy

The bond random mixed compound Fe(Br_0.9I_0.1)₂ has been studied by magnetization and Mössbauer measurements. Although the zero-field cooled and field-cooled magnetization variations are not like a typical spin glass one, the Mössbauer spectrum below Néel temperature shows a hyperfine field distribution. It implies that the 10% FeI₂ mixed in FeBr₂ can be induced by the bond random effect which causes the sample to exhibit a spin glass-like behavior.     

A note on balance vertices in trees

The notion of balanced bipartitions of the vertices in a tree T was introduced and studied by Reid (Networks 34 (1999) 264). Reid proved that the set of balance vertices of a tree T consists of a single vertex or two adjacent vertices. In this note, we give a simple proof of that result.     

Measurements of edge-uncolorability

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let c_k be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r₃=|E|−c₃ and . We show that on one side r₃ and r₂ bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r₃ and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr₃. For k=2,3, let ζ_k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.     

Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.