COMPLEXITY AND ERROR IN SOCIAL DYNAMICS

A model of cultural dynamics based on the work of Colin Renfrew is briefly described. It is shown how the general concepts of complexity and error pertain to this kind of cultural model. In particular, it is suggested that conflict in cultural contexts arises through the generation of diverse simple models of the culture, created by different members of the culture. We indicate how general system-theoretic concepts can thus be brought to bear on problems of conflict in and between cultures.     

Reliability and performance optimization of pipelined real-time systems

We consider pipelined real-time systems that consist of a chain of tasks executing on a distributed platform. The processing of the tasks is pipelined: each processor executes only one interval of consecutive tasks. We are interested in minimizing both the input–output latency and the period of application mapping. For dependability reasons, we are also interested in maximizing the reliability of the system. We therefore assign several processors to each interval of tasks, so as to increase the reliability of the system. Both processors and communication links are unreliable and subject to transient failures. We assume that the arrival of the failures follows a constant parameter Poisson law, and that the failures are statistically independent events. We study several variants of this multiprocessor mapping problem, with several hypotheses on the target platform (homogeneous/heterogeneous speeds and/or failure rates). We provide NP-hardness complexity results, and optimal mapping algorithms for polynomial problem instances. Efficient heuristics are presented to solve the general case, and experimental results are provided.     

A Bound for the Order of Characteristic Set Elements of an Ordinary Prime Differential Ideal and some Applications

With respect to an elimination ordering, we give an upper bound for the order of characteristic set elements of an ordinary prime differential ideal. Using some results of complexity in the algebraic case, we show that computing characteristic sets of ordinary prime differential ideals, by change of ordering, is single exponential time. Received: January 8, 1997; revised version: May 6, 1999     

A multi-objective approach to RBF network learning

The problem of inductive supervised learning is discussed in this paper within the context of multi-objective (MOBJ) optimization. The smoothness-based apparent (effective) complexity measure for RBF networks is considered. For the specific case of RBF network, bounds on the complexity measure are formally described. As the synthetic and real-world data experiments show, the proposed MOBJ learning method is capable of efficient generalization control along with network size reduction.     

Pattern Matching and Membership for Hierarchical Message Sequence Charts

Several formalisms and tools for software development use hierarchy in system design, for instance statecharts and diagrams in UML. Message sequence charts (MSCs) are a standardized notation for asynchronously communicating processes. The norm Z.120 also includes hierarchical HMSCs. Algorithms on MSCs rarely take into account all possibilities covered by the norm. In particular, hierarchy is not taken into account since the models that are usually considered are (flat) MSC-graphs, that correspond to the unfolding of hierarchical HMSCs. However, complexity can increase exponentially by unfolding. The aim of this paper is to show that basic algorithms can be designed such that they avoid the costly unfolding of hierarchical MSCs and HMSCs. We show this for the membership and the pattern matching problem. We prove that the membership problem for hierarchical HMSCs is PSPACE-complete. Then we describe a polynomial time algorithm for the pattern matching problem on hierarchical MSCs. The results were obtained while B. Genest was affiliated with LIAFA, Université Paris 7.     

An overview of statistical decomposition techniques applied to complex systems

The current state of the art in applied decomposition techniques is summarized within a comparative uniform framework. These techniques are classified by the parametric or information theoretic approaches they adopt. An underlying structural model common to all parametric approaches is outlined. The nature and premises of a typical information theoretic approach are stressed. Some possible application patterns for an information theoretic approach are illustrated. Composition is distinguished from decomposition by pointing out that the former is not a simple reversal of the latter. From the standpoint of application to complex systems, a general evaluation is provided.     

Multiprocessor scheduling with communication delays

This paper adresses certain types of scheduling problems that arise when a parallel computation is to be executed on a multiprocessor. We define a model that allows for communication delays between precedence-related tasks, and propose a classification of various submodels. We also review complexity results and optimization and approximation algorithms that have been presented in the literature.     

基于路程检测的机器人运动控制研究

机器人比赛赛道日趋复杂,由以往单一的直线、转弯增加了上坡、下坡等难度,鉴于机器人比赛赛道的复杂性,提出一种基于路程检测的控制机器人运动的方法,保证机器人顺利、快速地在各种赛道上行进。采用串口位置控制和光码盘共同进行路程检测方法,通过建立直流伺服电机的数学模型,根据PID算法调整机器人运动姿态,详细计算出不同路段下的机器人速度,给机器人运动轨迹控制提供重要参数。通过实验场地测试,结果表明:采用此方法,机器人能稳定、可靠、快速地在复杂的赛道上行进。