Diffusion dynamics of open source software: An agent-based computational economics (ACE) approach

The rising popularity of open source software (OSS) calls for a better understanding of the drivers of its adoption and diffusion. In this research, we propose an integrated framework that simultaneously investigates a broad range of social and economic factors on the diffusion dynamics of OSS using an Agent Based Computational Economics (ACE) approach. We find that interoperability costs, variability of OSS support costs, and duration of PS upgrade cycle are major determinants of OSS diffusion. Furthermore, there are interaction effects between network topology, network density and interoperability costs, which strongly influence the diffusion dynamics of OSS. The proposed model can be used as a building block to further investigate complex competitive dynamics in software markets.     

Realizability models and implicit complexity

New, simple, proofs of soundness (every representable function lies in a given complexity class) for Elementary Affine Logic, LFPL and Soft Affine Logic are presented. The proofs are obtained by instantiating a semantic framework previously introduced by the authors and based on an innovative modification of realizability. The proof is a notable simplification on the original already semantic proof of soundness for the above mentioned logical systems and programming languages. A new result made possible by the semantic framework is the addition of polymorphism and a modality to LFPL, thus allowing for an internal definition of inductive datatypes. The methodology presented proceeds by assigning both abstract resource bounds in the form of elements from a resource monoid and resource-bounded computations to proofs (respectively, programs).     

An optimal online algorithm for halfplane intersection

The intersection of N halfplanes is a basic problem in computational geometry and computer graphics,The optimal offline algorithm for this problem runs in time O(N log N).In this paper,an optimal online algorithm which runs also in time O(N log N) for this problem is presented.The main idea of the algorithm is to give a new definition for the left side of a given line,to assign the order for the opoints of a convex polygon.and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.     

Parametric Sequence Alignment with Constraints

Approximate matching techniques based on string alignment are important tools for investigating similarities between strings, such as those representing DNA and protein sequences. We propose a constraint based approach for parametric sequence alignment which allows for more general string alignment queries where the alignment cost can itself be parameterized as a query with some initial constraints. Thus, the costs need not be fixed in a parametric alignment query unlike the case in normal alignment. The basic dynamic programming string edit distance algorithm is generalized to a naive algorithm which uses inequalities to represent the alignment score. The naive algorithm is rather costly and the remainder of the paper develops an improvement which prunes alternatives where it can and approximates the alternatives otherwise. This reduces the number of inequalities significantly and strengthens the constraint representation with equalities. We present some preliminary results using parametric alignment on some general alignment queries.     

用VIS验证微处理器PIC

近年来,二叉判定图ＢＤＤ和符号模型检验在形式验证数字电路设计中取得了突破性进展,文中介绍了符号模型检验的基本原理和方法,重点介绍了如何用ＶＩＳ系统验证微处理器ＰＩＣ设计的正确性。利用ＶＩＳ证明了ＰＩＣ设计部分电路的等价性。发现了一个设计错误并证明了ＰＩＣ中一些重要模块的特性。     

On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata.(i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight.(ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams.(iii) For the size (i.e., the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language L is at least the square root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.     

Formulating and Solving Nonlinear Integrated Ecological-Economic Models Using GAMS

In order to analyze, understand and prescribe natural resourcemanagement strategies, the decision making framework should ideallycapture the dynamics of inter-dependency between the economic andecological systems in an integrated manner. However, by including twocomplex systems within a single integrated framework makes many of thepresent analytical tools redundant. Computational models on the otherhand are ideally suited to meet this challenge. The size and complexityof models solved through numerical techniques have increasedexponentially over the last decade. This is especially true fornon-linear optimization models. However, although the science of solvingnon-linear models has improved significantly, the solving of thesemodels is still an art. In this paper, we look at the criticalparameters that a modeler needs to be aware of when developingintegrated economic-ecology models and some `tricks' to solve them withthe minimum of effort through the use of the optimization software GAMS(General Algebraic Modeling System).     

Learning to Be Thoughtless: Social Norms and Individual Computation

This paper extends the literature on the evolution of norms with anagent-based modelcapturing a phenomenon that has been essentially ignored, namely thatindividual thought – orcomputing – is often inversely related to the strength of a social norm.Once a norm isentrenched, we conform thoughtlessly. In this model, agents learn how tobehave (what normto adopt), but – under a strategy I term Best Reply to Adaptive SampleEvidence – they also learnhow much to think about how to behave. How much they are thinking affects howthey behave,which – given how others behave – affects how much they think. Inshort, there is feedbackbetween the social (inter-agent) and internal (intra-agent) dynamics. Inaddition, we generate thestylized facts regarding the spatio-temporal evolution of norms: localconformity, global diversity,and punctuated equilibria.     

关于TSP问题的一种求解方法:CED聚合法

本文提出了 CED聚合法——几何算法和生态算法 ,并把 TSP转化为判定问题来处理 .给出了重要的定理 ,提出了数学聚合法原理 .最后 ,计算实例的结果表明 ,这种方法具有可行性和有效性