The undecidability of self-embedding for term rewriting systems

The self-embedding property of term rewriting systems is closely related to the uniform termination property, since a nonself-embedding term rewriting system is uniform terminating. The self-embedding property is shown to be undecidable and partially decidable. It follows that the nonself-embedding property is not partially decidable. This is true even for globally finite term rewriting systems. The same construction gives an easy alternate proof that uniform termination is undecidable in general and also for globally finite term rewriting systems. Also, the looping property is shown to be undecidable in the same way.     

Domain-specific program profiling and its application to attribute grammars and term rewriting

We present a method for profiling programs that are written using domain-specific languages. Instead of reporting execution in terms of implementation details as in most existing profilers, our method operates at the level of the problem domain. Program execution generates a stream of events that summarises the execution in terms of domain concepts and operations. The events enable us to construct a hierarchical model of the execution. A flexible reporting system summarises the execution along developer-chosen model dimensions. The result is a flexible way for a developer to explore the execution of their program without requiring any knowledge of the domain-specific language implementation.These ideas are embodied in a new profiling library called dsprofile that is independent of the problem domain so it has no specific knowledge of the data and operations that are being profiled. We illustrate the utility of dsprofile by using it to profile programs that are written using our Kiama language processing library. Specifically, we instrument Kiama's attribute grammar and term rewriting domain-specific languages to use dsprofile to generate events that report on attribute evaluation and rewrite rule application. Examples of typical language processing tasks show how domain-specific profiling can help to diagnose problems in Kiama-based programs without the developer needing to know anything about how Kiama is implemented.     

Reachability and confluence are undecidable for flat term rewriting systems

Ground reachability, ground joinability and confluence are shown undecidable for flat term rewriting systems, i.e., systems in which all left and right members of rule have depth at most one.     

A class of confluent term rewriting systems and unification

The narrowing mechanism and term rewriting systems are powerful tools for constructing complete and efficient unification algorithms for useful classes of equational theories. This has been shown for the case where term rewriting systems are confluent and noetherian (i.e., terminating). In this paper we show that the narrowing mechanism, combined with ordinary unification, yields a complete unification algorithm for equational theories that can be described by a closed linear term rewriting system with the non-repetition property; this class allows non-terminating rewrite systems. For some special forms of input terms, narrowing generates complete sets of E-unifiers without resorting to the non-repetition property. The key observation underlying the proof is that a reduction sequence in this class of term rewriting system can be transformed into one which possesses properties that enable a completeness proof.     

Term rewriting and its application to recognizing handwritten Hindu numerals

In this paper the theoretical basis is presented and the implementation of a term rewriting system based on algebraic specifications is described. The input to this system is represented by an algebraic specification language, which forms not only the set of axioms but also the sorts, variables, operators and terms of a specific simulated theory or application. Rewriting and matching mechanisms provide the formal methodology for evaluating terms and proving assertions in an algebraic theory. Specifications are evaluated by interpreting terms by means of rewrite rules. The rules are described by the axioms of the specifications where the finite termination and congruence properties are assumed. A term rewriting system to recognize handwritten Hindu numerals is introduced as a case study. Besides rewriting, a robust algorithm is proposed to segment the numeral's image into strokes based on feature points and to identify cavity features. A syntactic representation (term) of the input image is matched and rewritten against a set of rules. Experimental results proved that the proposed system is tolerant to recognize a variety of numeral shapes with 96% successful recognition rate.     

Conversion to tail recursion in term rewriting

Tail recursive functions are a special kind of recursive functions where the last action in their body is the recursive call. Tail recursion is important for a number of reasons (e.g., they are usually more efficient). In this article, we introduce an automatic transformation of first-order functions into tail recursive form. Functions are defined using a (first-order) term rewrite system. We prove the correctness of the transformation for constructor-based reduction over constructor systems (i.e., typical first-order functional programs).     

Using induction and rewriting to verify and complete parameterized specifications

In software engineering there is a growing demand for formal methods for the specification and validation of software systems. The formal development of a system might give rise to many proof obligations. We must prove the completeness of the specification and the validity of some inductive properties. In this framework, many provers have been developed. However they require much user interaction even for simple proof tasks. In this paper, we present new procedures to test sufficient completeness and to prove or disprove inductive properties automatically in para-meterized conditional specifications. The method has been implemented in the prover SPIKE. Computer experiments illustrate the improvements in length and structure of proofs, due to parameterization. Moreover, SPIKE offers facilities to check and complete specifications.     

An initial algebra approach to term rewriting systems with variable binders

We present an extension of first-order term rewriting systems. It involves variable binding in the term language. We develop systems called binding term rewriting systems (BTRSs) in a stepwise manner. First we present the term language, then formulate equational logic. Finally, we define rewriting systems. This development is novel because we follow the initial algebra approach in an extended notion of Σ-algebras in various functor categories. These are based on Fiore-Plotkin-Turi’s presheaf semantics of variable binding and Lüth-Ghani’s monadic semantics of term rewriting systems. We characterise the terms, equational logic and rewrite systems for BTRSs as initial algebras in suitable categories. Then, we show an important rewriting property of BTRSs: orthogonal BTRSs are confluent. Moreover, by using the initial algebra semantics, we give a complete characterisation of termination of BTRSs. Finally, we discuss our design choice of BTRSs from a semantic perspective. An erlier version appeared in Proc. Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP2003).     

Operational semantics of rewriting with priorities

We study the semantics of term rewriting systems with rule priorities (PRS), as introduced in Baeten et al. (1989). Three open problems posed in that paper are solved, by giving counter examples. Moreover, a class of executable PRSs is identified. A translation of PRSs into transition system specifications (TSS) is given. This translation introduces negative premises. We prove that the translation preserves the operational semantics.     

A behavioral type system and its application in Ptolemy II

Interface automata [deH01] have been introduced as an interface theory [deH01a] capable of functioning as a behavioral type system. Behavioral type systems describe dynamic properties of components and their compositions. Like traditional (data) type systems, behavioral type systems can be used to check compatibility of components. In this paper, we use interface automata to devise a behavioral type system for Ptolemy II, leveraging the contravariant and optimistic properties of interface automata to achieve behavioral subtyping and polymorphism. Ptolemy II is a software framework supporting concurrent component composition according to diverse models of computation. In this paper, we focus on representing the communication protocols used in component communication within the behavioral type system. In building this type system, we identify two key limitations in interface automata formalisms; we overcome these limitations with two extensions, transient states and projection automata. In addition to static type checking, we also propose to extend the use of interface automata to the on-line reflection of component states and to run-time type checking, which enable dynamic component creation, morphing application structure, and admission control. We discuss the trade-offs in the design of behavioral type systems.Received September 2002Accepted in revised form November 2003 by M. Broy, G. Lüttgen and M. Mendler     

A Toolkit for Generating and Displaying Proof Scores in the OTS/CafeOBJ Method

The OTS/CafeOBJ method can be used to model, specify and verify distributed systems. Specifications are written in equations, which are regarded as rewrite rules and used to verify specifications. The usefulness of the method is demonstrated by applying the method to nontrivial problems such as electronic commerce protocols and railroad signaling systems. In this paper we describe a toolkit called Buffet, which assists verification in the method. Given predicates used to split cases and lemmas, Buffet automatically generates proofs (called proof scores) and checks the proof scores using the CafeOBJ system. Buffet also has facilities to display proof scores generated and verification results on a web browser.     

PSPICE的行为模型及其在控制系统仿真中的应用

通过用电子电路仿真软件PSpice的行为模型仿真功能的分析,提出了将PSpice应用于控制系统仿真的具体方案。仿真实例充分表明PSpice是进行控制系统仿真的一个有效工具,在科研和教学中具有广泛的应用、推广价值。     

EDA技术在现代电路与系统设计中的应用

本文介绍了ISP硬件电路设计技术，借助模拟信号检测仪的研制过程，说明用ISP技术设计现代电路与系统的方法及具有的优点。     

Number of mutual connections in neighborhoods and its application to self-diagnosable systems

This paper gives a set of discriminators (sufficient conditions) to identify the possibility of embedding optimal, highly structured systems on regular graphs for the purpose of self-diagnosis. The discrimination process is only a set of straightforward matrix computations; however, the discriminator is powerful and leads to the result that most of the typical graphs representing interconnection networks such as Cayley graphs can be embedded by the highly structured systems. The highly structured system has an O(|E|) fault-identification algorithm that can diagnose each of the units independently, locally and in any order, where |E| means the cardinality of the set of edges.     

Effects of interface style on user perceptions and behavioral intention to use computer systems

This study examines the influence of two interface styles (menu- and command-based) on the perceived ease of use, perceived usefulness, and behavioral intention of the user to use the system. We have treated the system interface style as an external factor in the technology acceptance model (TAM) to examine its direct and indirect effects on behavioral intention to accept and use a system. The results showed that the interface style had direct effects on perceived ease of use and perceived usefulness which, in turn, demonstrated significant effects on behavioral intention to use the system. Further, the results showed that perceptions of the menu-based interface were more favorable than perceptions of the command-based interface. These results provide several theoretical and practical implications for designing an effective system.     

粗糙集理论及其在智能系统中的应用

粗糙集理论是一种新型的处理含糊和不确定知识的数学工具，在智能系统中得到了广泛的应用，介绍了经典粗糙集理论的基本思想，上下近似集、属性约简和核等基本概念以及粗糙集的研究现状．介绍了粗糙集理论在智能系统中的应用，主要包括基于粗糙集理论的属性约简作为数据预处理的手段，基于粗糙集理论的相关性分析和基于粗糙集理论的系统建模和控制．指出了粗糙集理论在应用中遇到的问题和可能的研究方向。     

New coprimeness over multivariable polynomial matrices and its application to control delay systems

This paper presents a new notion of coprimeness over multivariable polynomial matrices, where a single variable is given priority over the remaining variables. From a characterization through a set of common zeros of the minors, it is clarified that the presented coprimeness is equivalent to weakly zero coprimeness in the particular variable. An application of the presented coprimeness to control systems with non-commensurate delays and finite spectrum assignment is also presented. Because the presented coprimeness is stronger than minor coprimeness, non-commensurate delays are difficult to deal with in algebraic control theory. The “rational ratio condition” between delays, which can reduce non-commensurate delays to commensurate delays, proves to be both powerful and practical concept in algebraic control theory for delay systems.     

Dissipativity reinforcement in feedback systems and its application to expanding power systems

This paper focuses on the performance analysis and improvement of interconnected passive systems. We assume that each subsystem has a special passivity property that is characterized by 2 parameters. The parameters are also utilized for evaluating the dissipation performance as the L₂‐gain. Then, the feedback system composed of passive subsystems inherits the parameter‐dependent passivity, and the parameter transition is given. In addition, it is shown that the dissipation performance of the feedback system is strictly improved as compared with that of the subsystems, which is called dissipativity reinforcement in this paper. Furthermore, we expand the feedback system to a larger‐scale system via the iterative feedback connection of the passive subsystems. Then, the performance of the entire system is gradually reinforced with the increase in the number of subsystems. Subsequently, we extend the class of parameter‐dependent passivity to a frequency‐dependent one. Finally, dissipativity reinforcement via an iterative feedback connection is applied to a power system that involves a large number of renewable energy generators. In particular, we propose a strategy for designing the power system, such that the dissipation performance of the entire system is gradually reinforced via scale expansion, ie, with the increase in the amount of energy generators installed.     

State-based versus event-based specifications for information systems: a comparison of B and eb 3

This paper compares two formal methods, B and eb³, for specifying information systems. These two methods are chosen as examples of the state-based paradigm and the event-based paradigm, respectively. The paper considers four viewpoints: functional behavior expression, validation, verification, and evolution. Issues in expressing event ordering constraints, data integrity constraints, and modularity are thereby considered. A simple case study is used to illustrate the comparison, namely, a library management system. Two equivalent specifications are presented using each method. The paper concludes that B and eb³ are complementary. The former is better at expressing complex ordering and static data integrity constraints, whereas the latter provides a simpler, modular, explicit representation of dynamic constraints that are closer to the user’s point of view, while providing loosely coupled definitions of data attributes. The generality of these results from the state-based paradigm and the event-based paradigm perspective are discussed.