Recognisability for algebras of infinite trees

We develop an algebraic language theory for languages of infinite trees. We define a class of algebras called ω-hyperclones and we show that a language of infinite trees is regular if, and only if, it is recognised by a finitary path-continuous ω-hyperclone.     

On the structure of graphs in the Caucal hierarchy

We investigate the structure of graphs in the Caucal hierarchy. We provide criteria concerning the degree of vertices or the length of paths which can be used to show that a given graph does not belong to a certain level of this hierarchy. Each graph in the Caucal hierarchy corresponds to the configuration graph of some higher-order pushdown automaton. The main part of the paper consists of a study of such configuration graphs. We provide tools to decompose and reassemble their runs, and we prove a pumping lemma for higher-order pushdown automata.     

Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs

Recent work in the design of efficient algorithms for optimization problems on treedecomposable graphs concentrates on developing general approaches which lead to families of related algorithms, rather than on developing isolatedad hoc algorithms. This paper develops new general approaches to obtain two new families of related polynomial-time algorithms for (1) packing, partitioning, and covering problems and (2) multiset and multiproperty problems. These problems have not been handled by previous general approaches.     

A characterization of Büchi tree automata

We show that a language of infinite binary trees is definable by a Σ₂-formula of the monadic second order logic of two successors (with no additional symbols) iff it can be accepted by a Büchi automaton. The same result has been obtained by G. Lenzi, but our proof is simpler.     

Satisfiability of ECTL⁎ with constraints

We show that satisfiability and finite satisfiability for ${\mathsf{ECTL}}^{⁎}$ with equality-, order-, and modulo-constraints over $\mathbb{Z}$ are decidable. Since ${\mathsf{ECTL}}^{⁎}$ is a proper extension of ${\mathsf{CTL}}^{⁎}$ this greatly improves the previously known decidability results for certain fragments of ${\mathsf{CTL}}^{⁎}$, e.g., the existential and positive fragments and EF. We also show that our choice of local constraints is necessary for the result in the sense that, if we add the possibility to state non-local constraints over $\mathbb{Z}$, the resulting logic becomes undecidable.     

On linear-time algorithms for five-coloring planar graphs

Certain properties of planar graphs are established in a particularly straightforward fashion. These properties assure good performance in two linear-time algorithms for five-coloring planar graphs. A new linear-time algorithm, based on a third property, is also presented.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Optimally fast shortest path algorithms for some classes of graphs

Two algorithms for shortest path problems are presented. One is to find the all-pairs shortest paths (APSP) that runs in O(n ²logn + nm) time for n-vertex m-edge directed graphs consisting of strongly connected components with O(logn) edges among them. The other is to find the single-source shortest paths (SSSP) that runs in O(n) time for graphs reducible to the trivial graph by some simple transformations. These algorithms are optimally fast for some special classes of graphs in the sense that the former achieves O(n ²) which is a lower bound of the time necessary to find APSP, and that the latter achieves O(n) which is a lower bound of the time necessary to find SSSP. The latter can be used to find APSP, also achieving the running time O(n ²).     

A tool for model-checking Markov chains

Markov chains are widely used in the context of the performance and reliability modeling of various systems. Model checking of such chains with respect to a given (branching) temporal logic formula has been proposed for both discrete [34, 10] and continuous time settings [7, 12]. In this paper, we describe a prototype model checker for discrete and continuous-time Markov chains, the Erlangen–Twente Markov Chain Checker E⊢MC², where properties are expressed in appropriate extensions of CTL. We illustrate the general benefits of this approach and discuss the structure of the tool. Furthermore, we report on successful applications of the tool to some examples, highlighting lessons learned during the development and application of E⊢MC². Published online: 19 November 2002 Correspondence to: Holger Hermanns     

Definable transductions and weighted logics for texts

A text is a word together with an additional linear order on it. We study quantitative models for texts, i.e. text series which assign to texts elements of a semiring. We introduce an algebraic notion of recognizability following Reutenauer and Bozapalidis as well as weighted automata for texts combining an automaton model of Lodaya and Weil with a model of Ésik and Németh. After that we show that both formalisms describe the text series definable in a certain fragment of weighted logics as introduced by Droste and Gastin. In order to do so, we study certain definable transductions and show that they are compatible with weighted logics.     

Existential MSO over two successors is strictly weaker than over linear orders

As is well known, a language of finite words, considered as labeled linear orders, is definable in monadic second-order logic (MSO) iff it is definable in the existential fragment of MSO, that is the quantifier alternation hierarchy collapses. Even more, it does not make a difference if we consider existential MSO over a linear order or a successor relation only. In this note we show that somewhat surprisingly the latter does not hold if we just add a second linear order and consider finite relational structures with two linear orders, so-called texts.     

基于U-net的海马体分割算法应用

为促进阿尔兹海默症的诊断及治疗,实现对海马体的精确分割,针对海马体MRI图像,提出一种基于U-net模型改进的分割算法。使用CLAHE等对原始图像进行预处理,经处理后的图像有效提高了分割效果;将残差模块加入实现分割算法的卷积网络,增强网络性能,避免网络性能退化。对原始数据集进行扩充,将扩充后的样本数据用以训练网络,解决数据量的问题。实验结果表明,该算法在脑部MRI图像中对海马体实现了良好的分割效果,能较好辅助医生诊断。     

基于改进遗传算法的飞机定检人员均衡配置

将遗传算法应用于解决飞机定检人员均衡配置问题中.根据均方差指标建立了人员均衡配王模型;采用候选集合策略处理约束条件,保证每个个体都对应有可行解;采用最优保存策略和基于预选择的小生境实现方法对基本遗传算法进行改进,并使用其求解模型.仿真实例结果表明,改进遗传算法克服了基本遗传算法客易“早熟”的不足,均衡配置后人员工作时间均方差减少65.90％.     

Practical algorithms for selection on coarse-grained parallelcomputers

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. The results clearly demonstrate the role of randomization in reducing communication overhead     

Parallel algorithms for parameter-free structural diversity search on graphs

Structural diversity of a user in a social network is the number of social contexts in his/her contact neighborhood. The problem of structural diversity search is to find the top-k vertices with the largest structural diversity in a graph. However, when identifying distinct social contexts, existing structural diversity models (e.g., t-sized component, t-core, and t-brace) are sensitive to an input parameter of t. To address this drawback, we propose a parameter-free structural diversity model. Specifically, we propose a novel notation of discriminative core, which automatically models various kinds of social contexts without parameter t. Leveraging on discriminative cores and h-index, the structural diversity score for a vertex is calculated. We study the problem of parameter-free structural diversity search in this paper. An efficient top-k search algorithm with a well-designed upper bound for pruning is proposed. To further speed up the computation, we design a novel parallel algorithm for efficient top-k search over large graphs. The parallel algorithm computes diversity scores for a batch of vertices simultaneously using multi-threads. Extensive experiment results demonstrate the parameter sensitivity of existing t-core based model and verify the superiority of our methods.

     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。