一种检测TAL-freeness的代数方法

时间动作锁(Ti me-Action-Lock,TAL)指的是实时系统处于一种时间无法继续同时又没有任何动作能够发生的状态.Behzad和Kozo在时间自动机的几何学基础上提出了一种针对TAL-freeness的检测方法.但该方法要求必须将需要检测的模型转化为一种逻辑语言Rational Presburger Sentences后才能进行检测,因此使得验证过程比较繁琐.文中提出了一种检测TAL-freeness的代数方法,能够直接对系统模型进行直接验证,并且能够定位死锁原因.针对该方法,文中还给出了相应算法并提供了正确性证明与性能分析.     

A Software-Reuse Approach to Build Monitor Programs for Soft Real-Time Applications

Thispaper describes the implementation of an integration frameworkto build real-time monitor programs based on software reuse.A custom-made real-time monitor program can be built very quicklyby integrating existing monitor programs on commercial operatingsystems, where limited real-time system support is provided.We address issues related to software control, output re-processing,data age, and interactivities of program executions. The feasibilityof this framework is demonstrated by the construction of an integrationenvironment and a monitor program built by the environment forsoft real-time applications in the Microsoft Windows operatingsystems. We also measure the incurred system overheads of thisapproach.     

一种用于指针程序的形状分析方法

指针程序的分析一直是研究热点。本文提出一种基于形状图逻辑的形状分析方法,其中形状分析采用形状图来表达程序中指针的指向和相等关系,并用形状图逻辑来进行推理。形状图逻辑是一种把形状图看成有关指针的断言,并在此基础上对Hoare逻辑进行扩展而得到的程序逻辑。首先介绍所提出的形状图和形状图逻辑;然后在此基础之上,设计一种基于形状图逻辑的形状分析方法。     

An Algebraic Approach to Shadowed Sets

After the introduction of shadowed sets and the investigation of their relation with fuzzy sets, we present BZMV^dM algebras as an abstract environment for both shadowed and fuzzy sets. Then, we introduce the weaker notion of pre-BZMV^dM algebra. This structure enables us to algebraically define a mapping from fuzzy sets to shadowed sets.     

An Algebraic Approach to Camera Self-Calibration

This paper describes a new self-calibration method for a single camera undergoing general motions. It has the following main contributions. First, we establish new constraints which relate the intrinsic parameters of the camera to the rotational part of the motions. This derivation is purely algebraic. We propose an algorithm which simultaneously solves for camera calibration and the rotational part of motions. Second, we provide a comparison between the developed method and a Kruppa equation-based method. Extensive experiments on both synthetic and real image data show the reliability and outperformance of the proposed method. The practical contribution of the method is its interesting convergence property compared with that of the Kruppa equations method.     

A Process Algebraic Approach to the Schedulability Analysis of Real-Time Systems

To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of ACSR with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can use VERSA, a toolkit we have developed for ACSR, to perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

A Parallelization Approach for Hard Real-Time Systems and Its Application on Two Industrial Programs

Applications in industry often have grown and improved over many years. Since their performance demands increase, they also need to benefit from the availability of multi-core processors. However, a reimplementation from scratch and even a restructuring of these industrial applications is very expensive, often due to high certification efforts. Therefore, a strategy for a systematic parallelization of legacy code is needed. We present a parallelization approach for hard real-time systems, which ensures a high reusage of legacy code and preserves timing analysability. To show its applicability, we apply it on the core algorithm of an avionics application as well as on the control program of a large construction machine. We create models of the legacy programs showing the potential of parallelism, optimize them and change the source codes accordingly. The parallelized applications are placed on a predictable multi-core processor with up to 18 cores. For evaluation, we compare the worst case execution times and their speedups. Furthermore, we analyse limitations coming up at the parallelization process.     

Real-Time Behavior of Programs

Verification and compile-time checking of the behavior of programs in real time is an important issue in many applications, e.g., process control, lab automation, and monitoring of missiles and vehicles. Present day programming languages and compilers lack the facilities of calculating execution times of programs.     

An Algebraic Detection Approach for Control Systems under Multiple Stochastic Cyber-attacks

In order to compromise a target control system successfully, hackers possibly attempt to launch multiple cyberattacks aiming at multiple communication channels of the control system. However, the problem of detecting multiple cyber-attacks has been hardly investigated so far. Therefore, this paper deals with the detection of multiple stochastic cyber-attacks aiming at multiple communication channels of a control system. Our goal is to design a detector for the control system under multiple cyberattacks. Based on frequency-domain transformation technique and auxiliary detection tools, an algebraic detection approach is proposed. By applying the presented approach, residual information caused by different attacks is obtained respectively and anomalies in the control system are detected. Sufficient and necessary conditions guaranteeing the detectability of the multiple stochastic cyber-attacks are obtained. The presented detection approach is simple and straightforward. Finally, two simulation examples are provided, and the simulation results show that the detection approach is effective and feasible.      

一种面向实时交互的变形手势跟踪方法

变形手势跟踪是基于视觉的人机交互研究中的一项重要内容.单摄像头条件下,提出一种新颖的变形手势实时跟踪方法.利用一组2D手势模型替代高维度的3D手模型.首先利用贝叶斯分类器对静态手势进行识别,然后对图像进行手指和指尖定位,通过将图像特征与识别结果进行匹配,实现了跟踪过程的自动初始化.提出将K-means聚类算法与粒子滤波相结合,用于解决多手指跟踪问题中手指互相干扰的问题.跟踪过程中进行跟踪状态检测,实现了自动恢复跟踪及手势模型更新.实验结果表明,该方法可以实现对变形手势快速、准确的连续跟踪,能够满足基于视觉的实时人机交互的要求.     

Algebraic Correctness Proofs for Compiling Recursive Function Definitions with Strictness Information

Adding appropriate strictness information to recursive function definitions we achieve a uniform treatment of lazy and eager evaluation strategies. By restriction to first-order functions over basic types we develop a pure stack implementation that avoids a heap even for lazy arguments. We present algebraic definitions of denotational, operational, and stack-machine semantics and prove their equivalence by means of structural induction.     

An Algebraic Approach to Lens Distortion by Line Rectification

A very important property of the usual pinhole model for camera projection is that 3D lines in the scene are projected in 2D lines. Unfortunately, wide-angle lenses (specially low-cost lenses) may introduce a strong barrel distortion which makes the usual pinhole model fail. Lens distortion models try to correct such distortion. In this paper, we propose an algebraic approach to the estimation of the lens distortion parameters based on the rectification of lines in the image. Using the proposed method, the lens distortion parameters are obtained by minimizing a 4 total-degree polynomial in several variables. We perform numerical experiments using calibration patterns and real scenes to show the performance of the proposed method.

Normative Systems and their Revision: An Algebraic Approach

The paper discusses normative systems and their revision within an algebraic framework. If a system is logically well-formed, certain norms, called connecting norms, determine the system as a whole. It is maintained that, if the system is well-formed, a relation “at least as low as” determines a lattice or quasi-lattice of its connecting norms. The ideas are presented mainly in the form of comments on a legal example concerning acquisition of movable property by extinction of another person's previous rights.     

Efficient Index Generation for Compiling Two-Level Mappings in Data-Parallel Programs

This paper presents compilation techniques used to compress holes, which are caused by the nonunit alignment stride in a two-level data-processor mapping. Holes are the memory locations mapped by useless template cells. To fully utilize the memory space, memory holes should be removed. In a two-level data-processor mapping, there is a repetitive pattern for array elements mapped onto processors. We classify blocks into classes and use a class table to record the distribution of each class in the first repetitive data distribution pattern. Similarly, data distribution on a processor also has a repetitive pattern. We use a compression table to record the distribution of each block in the first repetitive data distribution pattern on a processor. By using a class table and a compression table, hole compression can be easily and efficiently achieved. Compressing holes can save memory usage, improve spatial locality and further improve system performance. The proposed method is efficient, stable, and easy to implement. The experimental results do confirm the advantages of our proposed method over existing methods.     

An Algebraic Computational Approach to the Identifiability of Fourier Models

Computer algebra and in particular Gröbner bases are powerful tools in experimental design (Pistone and Wynn, 1996,Biometrika83, 653–666). This paper applies this algebraic methodology to the identifiability of Fourier models. The choice of the class of trigonometric models forces one to deal with complex entities and algebraic irrational numbers. By means of standard techniques we have implemented a version of the Buchberger algorithm that computes Gröbner bases over the complex rational numbers and other simple algebraic extensions of the rational numbers. Some examples are fully carried out.