重写系统的模块分解

Ｍｉｄｄｅｌｄｏｒｐ和Ｔｏｙａｍａ证明，强加构造原则到项重写系统可获得完备概念的模块性，并且系统分解成的各部分间可共亨函数符号和重量写规则。本文推广他们的结论，当构造性的项重写系统引用定义在其它系统中的函数符号时，完备概念的模块性仍保持。该结论对代数规范和基于项重写的编程语言等方面是很有意义的。     

基于重写方法的程序开发系统的设计和实现

本文介绍了一个基于重写方法的程序开发系统的设计和实现。该系统使用代数规范说明语言和扩展的函数式语言合成而形成的混合语言进行程序设计。系统将代数规范转换为合流的重写系统，并以平行最外方法辅以必要归约进行计算。该文详细介绍了系统的原理和实现技术，并以一些实例说明了系统的特点。     

Sufficient-completeness,ground-reducibility and their complexity

Summary The sufficient-completeness property of equational algebraic specifications has been found useful in providing guidelines for designing abstract data type specifications as well as in proving inductive properties using the induction-less-induction method. The sufficient-completeness property is known to be undecidable in general. In an earlier paper, it was shown to be decidable for constructor-preserving, complete (canonical) term rewriting systems, even when there are relations among constructor symbols. In this paper, the complexity of the sufficient-completeness property is analyzed for different classes of term rewriting systems. A number of results about the complexity of the sufficient-completeness property for complete (canonical) term rewriting systems are proved: (i) The problem is co-NP-complete for term rewriting systems with free constructors (i.e., no relations among constructors are allowed), (ii) the problem remains co-NP-complete for term rewriting systems with unary and nullary constructors, even when there are relations among constructors, (iii) the problem is provably in almost exponential time for left-linear term rewriting systems with relations among constructors, and (iv) for left-linear complete constructor-preserving rewriting systems, the problem can be decided in steps exponential innlogn wheren is the size of the rewriting system. No better lower-bound for the complexity of the sufficient-completeness property for complete (canonical) term rewriting system with nonlinear left-hand sides is known. An algorithm for left-linear complete constructor-preserving rewriting systems is also discussed. Finally, the sufficient-completeness property is shown to be undecidable for non-linear complete term rewriting systems with associative functions. These complexity results also apply to the ground-reducibility property (also called inductive-reducibility) which is known to be directly related to the sufficient-completeness property.Some of the results in this paper were reported in a paper titled Complexity of Sufficient-Completeness presented at theSixth Conf. on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, Dec. 1986. The term quasi-reducibility is replaced in this paper by ground-reducibility as the latter seems to convey a lot more about the concept than the former.Partially supported by the National Science Foundation Grant nos. CCR-8408461 and CCR-8906678Partially supported by the National Science Foundation Grant nos. CCR-8408461 and CCR-9009414Partially supported by the National Science Foundation Grant no. DCR-8603184     

Rewriting systems with limited distance forbidding context

A random context production has a permitting and forbidding context. A symbol can be rewritten using such a production if all the permitting context symbols and no forbidding context symbol appear in the sentential string. In this paper we limit the effect of forbidding context symbols to be within a certain distance from the symbol to be rewritten. Outside this distance the forbidding context symbols do not influence the rewriting of a symbol. This restriction strictly increases the generating power of the rewriting system.

A further result of this paper is a “negative parallel” version of Penttonen's normal form.     

一种基于模重写系统的攻击者推理方法

为了解决安全协议验证中攻击者模等式理论推理的可操作性问题,提出并设计了一种基于模重写系统的攻击者推理方法。该方法建立在一个反映两种密码原语代数特性的联合理论实例之上,由一组定向的重写规则和非定向的等式构成,前者进一步转化为项重写系统TRS(Term Rewriting System),而后者则转化为有限等价类理论,通过定义项间的模重写关系,使二者构成一个可以反映攻击者针对联合理论代数项操作能力的模重写系统。实例分析表明,该模型为攻击者模等式推理规则赋予了明确的操作语义,可以使攻击者达到对安全协议代数项规约、推理的目的。     

A Rewriting Machine and Optimization of Strategies of Term Rewriting

An algebraic specification of a new rewriting machine for fast rewriting of terms is considered. Theorems on the correctness of this specification are proved. A method for optimization of a strategy of iterative rewriting is proposed.     

Comparing Curried and Uncurried Rewriting

Currying is a transformation of term rewrite systems which may contain symbols of arbitrary arity into systems which contain only nullary symbols, together with a single binary symbol called application. We show that for all term rewrite systems (whether orthogonal or not) the following properties are preserved by this transformation: strong normalization, weak normalization, weak Church-Rosser, completeness, semi-completeness, and the non-convertibility of distinct normal forms. Under the condition of left-linearity we show preservation of the properties NF (if a term is reducible to a normal form,then its reducts are all reducible to the same normal form) and UN→ (a term is reducible to at most one normal form).We exhibit counterexamples to the preservation of NF and UN→ for non-left-linear systems.The results extend to partial currying(where some subset of the symbols are curried),and imply some modularity properties for unions of applicative systems.     

Rewriting systems with limited distance permitting context

By restricting the permitting context symbols in a rewriting system to be within a specified distance from the symbol to be replaced, we strictly increase the generative power above that of rewriting systems where the context symbols can appear within arbitrary distances from the symbol to be replaced.     

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.     

Methodical specification of abstract data types via rewriting systems

A data type is often given by an informal model. Its formal specification is an important task, but also difficult and error-prone. Here a methodology for this task is presented. Its steps are, first, the election of a canonical form defining a canonical term algebra; second, a system of sound rewriting rules powerful enough to achieve the syntactical transformations of the canonical term algebra. The final translation of rewriting rules into equations is immediate. The methodology is illustrated by the detailed presentation of a simple example.Research partly sponsored by FINEP, CNPq and the French Ministry for Foreign Affairs.     

Some algebraic laws for spans (and their connections with multirelations)

This paper investigates some key algebraic properties of the categories of spans and cospans (up to isomorphic supports) over the category Set of (small) sets and functions, analyzing the monoidal structures induced over both spans and cospans by cartesian product and disjoint union of sets. Our results find analogous counterparts in (and are partly inspired by) the theory of relational algebras, thus our paper also sheds some light on the relationship between (co)spans and the categories of (multi)relations and of equivalence relations. And, since (co)spans yield an intuitive presentation of dynamical systems with input and output interfaces, our results introduce an expressive, two-fold algebra that can serve as a specification formalism for rewriting systems and for composing software modules.     

Inequational Deduction as Term Graph Rewriting

Multi-algebras allow to model nondeterminism in an algebraic framework by interpreting operators as functions from individual arguments to sets of possible results.We propose a simple inequational deduction system, based on term graphs, for inferring inclusions of derived relations in a multi-algebra, and we show that term graph rewriting provides a sound and complete implementation of it.     

An algebraic model for programming languages

The language of universal algebras is used as a model for programming language specification. BNF rules are employed for specifying the signature of the language algebra instead of the context free syntax. The algorithm for program evaluation is inductively defined by the following universal algebraic construction:

Any function defined on the generators of a free algebra taking values in the carrier of another similar algebra can be uniquely extended to a homomorphism between the two algebras.

Any conventional programming language can be specified by a finite set of BNF rules and its algebra of symbols is generated by a finite set of generator classes. Thus any function defined on the finite set of generators offers an algebraic mechanism for a universal algorithm for source language program evaluation.     

Exhaustive test sets for algebraic specifications

In the context of testing from algebraic specifications, test cases are ground formulas chosen amongst the ground semantic consequences of the specification, according to some possible additional observability conditions. A test set is said to be exhaustive if every programme P passing all the tests is correct and if for every incorrect programme P, there exists a test case on which P fails. Because correctness can be proved by testing on such a test set, it is an appropriate basis for the selection of a test set of practical size. The largest candidate test set is the set of observable consequences of the specification. However, depending on the nature of specifications and programmes, this set is not necessarily exhaustive. In this paper, we study conditions to ensure the exhaustiveness property of this set for several algebraic formalisms (equational, conditional positive, quantifier free and with quantifiers) and several test hypotheses. Copyright © 2016 John Wiley & Sons, Ltd.     

Counterexamples to termination for the direct sum of term rewriting systems

The direct sum of two term rewriting systems is the union of systems having disjoint sets of function symbols. It is shown that the direct sum of two term rewriting systems is not terminating, even if these systems are both terminating.     

Ensuring termination by typability

A term terminates if all its reduction sequences are of finite length. We show four type systems that ensure termination of well-typed π-calculus processes. The systems are obtained by successive refinements of the types of the simply typed π-calculus. For all (but one of) the type systems we also present upper bounds to the number of steps well-typed processes take to terminate. The termination proofs use techniques from term rewriting systems. We show the usefulness of the type systems on some non-trivial examples: the encodings of primitive recursive functions, the protocol for encoding separate choice in terms of parallel composition, a symbol table implemented as a dynamic chain of cells.     

非线性代数规范的直接实现技术

代数规范是支持软件规格说明和设计的一种有效的方法，代数规范的直接实现技术是该研究领域的一个主要分支，目前这方面的研究基本上局限于线性代数规范，本文介绍一个实现非线性代数规范的转换过程，从该过程可自然是导出针对不同程序设计语言的转换系统，我们已实现了一个基于Ｐａｓｃａｌ语言的转换系统。     

An encoding of partial algebras as total algebras

We introduce a semantic encoding of partial algebras as total algebras through a Horn axiomatization of the existence equality relation interpreted as an algebraic operation. We show that this novel encoding enjoys several important properties that make it a good tool for the execution of partial algebraic specifications through means specific to ordinary algebraic reasoning, such as term rewriting.     

Coinduction for preordered algebra

We develop a combination, called hidden preordered algebra, between preordered algebra, which is an algebraic framework supporting specification and reasoning about transitions, and hidden algebra, which is the algebraic framework for behavioural specification. This combination arises naturally within the heterogeneous framework of the modern formal specification language CafeOBJ. The novel specification concept arising from this combination, and which constitutes its single unique feature, is that of behavioural transition. We extend the coinduction proof method for behavioural equivalence to coinduction for proving behavioural transitions.     

Lazy productivity via termination

We present a procedure for transforming strongly sequential constructor-based term rewriting systems (TRSs) into context-sensitive TRSs in such a way that productivity of the input system is equivalent to termination of the output system. Thereby automated termination provers become available for proving productivity. A TRS is called productive if all its finite ground terms are constructor normalizing, and all ‘inductive constructor paths’ through the resulting (possibly non-wellfounded) constructor normal form are finite. To our knowledge, this is the first complete transformation from productivity to termination.The transformation proceeds in two steps: (i) The strongly sequential TRS is converted into a shallow TRS, where patterns do not have nested constructors. (ii) The shallow TRS is transformed into a context-sensitive TRS, where rewriting below constructors and in arguments not ‘consumed from’ is disallowed.Furthermore, we show how lazy evaluation can be encoded by strong sequentiality, thus extending our transformation to, e.g., Haskell programs.Finally, we present a simple, but fruitful extension of matrix interpretations to make them applicable for proving termination of context-sensitive TRSs.