Incompleteness of states w.r.t. traces in model checking

Cousot and Cousot introduced and studied a general past/future-time specification language, called

-calculus, featuring a natural time-symmetric trace-based semantics. The standard state-based semantics of the

-calculus is an abstract interpretation of its trace-based semantics, which turns out to be incomplete, that is trace-incomplete, even for finite systems. As a consequence, standard state-based model checking of the

-calculus is incomplete w.r.t. trace-based model checking. This paper shows that any refinement or abstraction of the domain of sets of states induces a corresponding semantics which is still trace-incomplete for any propositional fragment of the

-calculus. This derives from a number of results, one for each incomplete logical/temporal connective of the

-calculus, that characterize the structure of models, i.e., transition systems, whose corresponding state-based semantics of the

-calculus is trace-complete.     

Solving the Word Problem for Two Classes of Non-associative Rings by Rewriting

Using the notion of modified completion given in Widiger, A. (1998, Deciding degree-four-identities for alternative rings by rewriting. In Bronstein, M., Grabmeier, J., Weispfenning, V. eds, Symbolic Rewriting Techniques, PCS 15, pp. 277–288. Birkhäuser-Verlag), it is shown that the word problem for the varieties of non-associative rings defined by (xy)z = y(zx) and (xy)z = y(xz) respectively can be decided by rewriting.     

Space Functions and Space Complexity of the Word Problem in Semigroups

We introduce the space function s(n) of a finitely presented semigroup ${S =\langle A \mid R \rangle}$ . To define s(n) we consider pairs of words w,w′ over A of length at most n equal in S and use relations from R for the derivations ${w = w_0 \rightsquigarrow \dots \rightsquigarrow w_t = w'; s(n)}$ bounds from above the lengths of the words w _i at intermediate steps, i.e., the space sufficient to implement all such transitions ${w \rightsquigarrow \dots \rightsquigarrow w'}$ . One of the results obtained is the following criterion: A finitely generated semigroup S has decidable word problem of polynomial space complexity if and only if S is a subsemigroup of a finitely presented semigroup H with polynomial space function.     

A branch, bound, and remember algorithm for the 1|r i |∑t i scheduling problem

This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r _i |∑t _i scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1|r _i |∑t _i scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.     

局部引理及其在（r，s）-SAT问题中的应用

一般说来,寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径：证明满足一定结构性质的对象的概率大于零。在概率方法中,局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法,并将其应用到估计（r,s）-SAT问题中临界函数的下界。     

Order Invariants and the "Environment" Problem for Games with Ordered Outcomes

A property of a game with ordered outcomes is called an order invariant if it does not depend on the addition of unrealizable outcomes. In this paper, some important order invariants are obtained for antagonistic games with ordered outcomes. It is shown that these invariants are connected with equilibrium points in the sense of Nash. For a given game, its so-called majorant extension is constructed so that certain noninvariant properties of the game become its invariants.     

Generalization and specialization strategies for learning r.e. languages

Overgeneralization is a major issue in the identification of grammars for formal languages from positive data. Different formulations of generalization and specialization strategies have been proposed to address this problem, and recently there has been a flurry of activity investigating such strategies in the context of indexed families of recursive languages. The present paper studies the power of these strategies to learn recursively enumerable languages from positive data. In particular, the power of strong-monotonic, monotonic, and weak-monotonic (together with their dual notions modeling specialization) strategies are investigated for identification of r.e. languages. These investigations turn out to be different from the previous investigations on learning indexed families of recursive languages and at times require new proof techniques. A complete picture is provided for the relative power of each of the strategies considered. An interesting consequence is that the power of weak-monotonic strategies is equivalent to that of conservative strategies. This result parallels the scenario for indexed classes of recursive languages. It is also shown that any identifiable collection of r.e. languages can also be identified by a strategy that exhibits the dual of weak-monotonic property. An immediate consequence of the proof of this result is that if attention is restricted to infinite r.e. languages, then conservative strategies can identify every identifiable collection. This revised version was published online in June 2006 with corrections to the Cover Date.     

Accelerating the Arnoldi-Type Algorithm for the PageRank Problem and the ProteinRank Problem

PageRank is an algorithm for computing a ranking for every Web page based on the graph of the Web. It plays an important role in Google’s search engine. The core of the PageRank algorithm involves computing the principal eigenvector of the Google matrix. Currently, we need to solve PageRank problems with high damping factors, which cost considerable time. A possible approach for accelerating the computation is the Arnoldi-type algorithm. However, this algorithm may not be satisfactory when the damping factor is high and the dimension of the Krylov subspace is low. Even worse, it may stagnate in practice. In this paper, we propose two strategies to improve the efficiency of the Arnoldi-type algorithm. Theoretical analysis shows that the new algorithms can accelerate the original Arnoldi-type algorithm considerably, and circumvent the drawback of stagnation. Numerical experiments illustrate that the accelerated Arnoldi-type algorithms usually outperform many state-of-the-art accelerating algorithms for PageRank. Applications of the new algorithms to function predicting of proteins are also discussed.     

A branch‐and‐cut algorithm for the Team Orienteering Problem

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two‐index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch‐and‐cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.     

孤立词语音识别算法性能研究与改进

文章针对特定人中小字表孤立词语音识别,以提高实用性为目的,对两种常用识别方法(VQ、DTW)的效果及其性能(识别速度和识别率)改善进行分析与探索,并通过对实验数据的讨论,提出了一些有效的改进方法。     

Word reordering on multiple pivots for the Japanese and Indonesian language pair

Machine Translation - We investigated multiple pivot approaches for the Japanese and Indonesian (Ja–Id) language pair in phrase-based statistical machine translation (SMT). We used four...     

Participatory journalism – the (r)evolution that wasn't. Content and user behavior in Sweden 2007–2013

A contemporary debate in media studies concerns participation and empowerment, and to what extent digital media shift power to the citizens. This study assesses the long‐term viability of participatory journalism using Swedish content and user data. Inclusion of comments and blog‐links on news sites increased from 2007 to 2010, and decreased rather dramatically from 2011 onward. Posting user comments or writing blogs have never been activities that have appealed to a majority of the Swedes. Participatory journalism seems to have decreasing value to producers and little appeal to users. A shift in how power is distributed in the public sphere is absent. This is not primarily a problem of reluctant producers but, more importantly, a lack of interest from users.     

Mission Energy Prediction for Unmanned Ground Vehicles Using Real‐time Measurements and Prior Knowledge

A typical unmanned ground vehicle (UGV) mission can be composed of various tasks and several alternative paths. Small UGVs are typically teleoperated and rely on electric rechargeable batteries for their operations. Since each battery has limited energy storage capacity, it is essential to predict the expected mission energy requirement during the mission execution and update this prediction adaptively via real‐time performance measurements (e.g., vehicle power consumption and velocity). We propose and compare two methods in this paper. One is based on recursive least‐squares estimation built upon a UGV longitudinal dynamics model. The other is based on Bayesian estimation when prior knowledge (e.g., road average grade and operator driving style) is available. The proposed Bayesian prediction can effectively combine prior knowledge with real‐time performance measurements for adaptively updating the prediction of the mission energy requirement. Our experimental and simulation studies show that the Bayesian approach can yield more accurate predictions even with moderately imprecise prior knowledge. © 2013 Wiley Periodicals, Inc.     

A Strongly Conservative Hybrid DG/Mixed FEM for the Coupling of Stokes and Darcy Flow

We consider the coupling of free and porous media flow governed by Stokes and Darcy equations with the Beavers–Joseph–Saffman interface condition. This model is discretized using a divergence-conforming finite element for the velocities in the whole domain. Hybrid discontinuous Galerkin techniques and mixed methods are used in the Stokes and Darcy subdomains, respectively. The discretization achieves mass conservation in the sense of \(H(\mathrm {div},\Omega )\), and we obtain optimal velocity convergence. Numerical results are presented to validate the theoretical findings.     

改进NSGA Ⅱ算法在车辆路径多目标优化问题中的应用

本文选用NSGA Ⅱ作为求解VRP多目标优化问题的算法基础,分析概括出VRP的三个主要目标函数和三个约束条件,实现了VRP多目标优化问题的数学建模。选择MATLAB作为软件工具进行代码编写,选取Benchmark Problems中C101里的数据作为实验数据进行软件仿真;并且针对NSGA Ⅱ在设计方面的不足之处,对NSGA Ⅱ的初始群体确定和交叉算子两个环节进行改进;然后通过对两种算法仿真结果的比较分析,证实了改进算法在克服早熟现象、提高算法效率以及算法稳定性方面的有效性。     

Term Rewriting for the Conjugacy Problem and the Braid Groups

We show how term rewriting can be applied to the conjugacy problem for finitely presented groups. The conjugacy problem is paricularly important for the braid groups. We illustrate the term rewriting approach by applying it to the braid group B₃.