Let's Make a Difference! (2009)
Endrullis, Joerg, Hendriks, Dimitri, Klop, Jan Willem
We study the behaviour of iterations of the difference operator delta on streams over {0,1}. In particular, we show that a stream sigma is eventually periodic if and only if the sequence of...
Unique Normal Forms in Infinitary Weakly Orthogonal Term Rewriting (2009)
Endrullis, Joerg, Grabmayer, Clemens, Hendriks, Dimitri, Klop, Jan Willem
The theory of finite and infinitary term rewriting is extensively developed for orthogonal rewrite systems, but to a lesser degree for weakly orthogonal rewrite systems. In this note we present some...
Abstract Vicious Circles in Rewriting Systems (2009)
Jeroen Ketema, Jan Willem Klop, Vincent Van Oostrom, Van Oostrom
We continue our study of the difference between Weak Normalisation (WN) and Strong Normalisation (SN). We extend our earlier result that orthogonal TRSs with the property WN do not admit cyclic...
Abstract Vicious Circles in Rewriting Systems (2008)
Jeroen Ketema, Jan Willem Klop, Vincent Van Oostrom, Van Oostrom
We continue our study of the difference between Weak Normalisation (WN) and Strong Normalisation (SN). We extend our earlier result that orthogonal TRSs with the property WN do not admit cyclic...
Lambda Calculus with Patterns (2008)
Jan Willem Klop, Vincent Van Oostrom, Roel De Vrijer
Abstract. In this paper we revisit the λ-calculus with patterns, originating from the practice of functional programming language design. We treat this feature in a framework ranging from pure...
Abstract WRS 2004 Preliminary Version Vicious Circles in Orthogonal Term Rewriting Systems (2008)
Jeroen Ketema, Jan Willem Klop, Vincent Van Oostrom, Van Oostrom
In this paper we first study the difference between Weak Normalization (WN) and Strong Normalization (SN), in the framework of first order orthogonal rewriting systems. With the help of the Erasure...
Iterative Path Orders 1 Iterative Path Orders Extended abstract (2008)
Jan Willem Klop, Vincent Van Oostrom, Roel De Vrijer
In the first half of this paper we give an alternative version of the recursive path order (RPO) for first-order term rewriting, which is ‘iterative ’ rather than recursive. Hence the name...
Iterative Lexicographic Path Orders (2008)
Jan Willem Klop, Vincent Van Oostrom, Roel De Vrijer
Abstract. We relate Kamin and Lévy’s original presentation of lexicographic path orders (LPO), using an inductive definition, to a presentation, which we will refer to as iterative lexicographic...
Some Remarks on Definability of Process Graphs (2008)
Clemens Grabmayer, Jan Willem Klop, Bas Luttik, Cwi Amsterdam
Abstract. We propose the notions of “density ” and “connectivity ” of infinite process graphs and investigate them in the context of the wellknown process algebras BPA and BPP. For a process...
Zena M. Ariola, Jan Willem Klop
E-mail:det informatik.uni-bremen.de We present a survey of confluence properties of (acyclic) term graph rewriting. Results and counterexamples are given for different kinds of term graph rewriting;...
Bisimilarity in term graphs rewriting (2007)
Zena M. Ariola, Jan Willem Klop, Detlef Plump
We present a survey of con uence properties of (acyclic) term graph rewriting. Results and counterexamples are given for dierent kinds of term graph rewriting: besides plain applications of rewrite...
Descendants and Origins in Term Rewriting (2007)
Inge Bethke Jan, Jan Willem Klop, Roel De Vrijer
In this paper we treat various aspects of a notion that is central in term rewriting, namely that of descendants or residuals. We address both first order term rewriting and -calculus, their finitary...
A Geometric Proof of Confluence by Decreasing Diagrams (2007)
Jan Willem Klop, Vincent Van Oostrom, Roel De Vrijer
Recently a new confluence criterion for confluence was found using decreasing diagrams, as a generalization of several wellknown confluence criteria in abstract rewriting such as the strong...
Jan Willem Klop, Catuscia Palamidessi
) Frank S. de Boer , Jan Willem Klop yz , Catuscia Palamidessi yx Abstract We study the paradigm of asynchronous process communication, as contrasted with the synchronous communication mechanism...
Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica (2007)
Mieke Brune, Jan Willem Klop, Jan Rutten (eds.), Van De Redactie, Samenstelling Bestuur, ...
s van voordrachten On Notions of bisimulation and associated logics Prof.dr. M. Nielsen BRICS, Computer Science Department, University of Aarhus Recently, there have been several attempts of abstract...
Richard Kennaway, Jan Willem Klop
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...
Bisimilarity in term graphs rewriting (2007)
Z. M. Ariola, J. W. Klop, D. Plump, Issn -x, Mathematisch Centrum (smc, The Dutch Foundation, ...
and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
Computing with Actions and Communications (2007)
Fokkink, Wan, Klop, Jan Willem
The paradigm of computer science is nowadays shifting from computation to communication. In this paper we aim to give an impression of the algebra of actions and communications as it has been...
The conjecture that the above statement can be answered in the positive is known as the Barendregt-Geuvers-Klop conjecture. It was presented to the originator by Henk Barendregt some time in 1994. Is...
6.0. General introduction. In this proposal we focus on infinite objects such as streams, infinite terms, both first order and higher order (with binders as in lambda calculus), infinite trees,...
Software ENgineering Infinitary normalization (2005)
J. W. Klop, Jan Willem Klop, Roel De Vrijer
CWI is a founding member of ERCIM, the European Research Consortium for Informatics and Mathematics. CWI's research has a theme-oriented structure and is grouped into four clusters. Listed below...
Infinitary Normalization (2005)
Jan Willem Klop, Roel De Vrijer
abstract. In infinitary orthogonal first-order term rewriting the properties confluence (CR), Uniqueness of Normal forms (UN), Parallel Moves Lemma (PML) have been generalized to their infinitary...
. DRAFT Iterative path orders (2004)
Jan Willem Klop, Vincent Van Oostrom, Roel De Vrijer
In Dershowitz’s original presentation recursive path orders (RPO) are defined by means of recursion. In Bergstra and Klop’s presentation RPOs are operationally defined by means of a set of term...
A geometric proof of confluence by decreasing diagrams (2000)
J. W. Klop, V. Van Oostrom, R. De Vrijer, Mathematisch Centrum (smc, The Dutch Foundation, Jan Willem Klop, ...
and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
Descendants and Origins in Term Rewriting (1999)
I. Bethke, Jan W. Klop, R. De Vrijer, Inge Bethke, Jan Willem Klop, Roel De Vrijer
In this paper we treat various aspects of a notion that is central in term rewriting, namely that of descendants or residuals. We address both first order term rewriting and -calculus, their finitary...
Comparing Curried and Uncurried Rewriting (1998)
Richard Kennaway, Jan Willem Klop, Ronan Sleep
this paper we show that strong normalization (SN), weak normalization (WN), the weak Church-Rosser property (WCR), the unique normal form property (UN), completeness, and semi-completeness are...
Bisimilarity in Term Graph Rewriting (1998)
Zena M. Ariola, Jan Willem Klop, D. Plump
We present a survey of confluence properties of (acyclic) term graph rewriting. Results and counterexamples are given for different kinds of term graph rewriting: besides plain applications of...
ABSTRACT Bisimilarity in Term Graph Rewriting (1998)
Z. M. Ariola, J. W. Klop, D. Plump, Issn -x, Copyright Stichting, Mathematisch Centrum, ...
and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
Infinitary Lambda Calculus (1997)
Richard Kennaway, Jan Willem Klop
In a previous paper we have established the theory of transfinite reduction for orthogonal term rewriting systems. In this paper we perform the same task for the lambda calculus. From the viewpoint...
Z. M. Ariola, J. W. Klop, Issn -x, Zena M. Ariola, Jan Willem Klop
We present an equational framework for term graph rewriting with cycles. The usual notion of homomorphism is phrased in terms of the notion of bisimulation, which is well-known in process algebra and...
Diagram Techniques for Confluence (1996)
Marc Bezem, Jan Willem Klop, Vincent Van Oostrom
We develop diagram techniques for proving confluence in abstract reductions systems. The underlying theory gives a systematic and uniform framework in which a number of known results, widely...
Problems in rewriting III (1995)
Nachum Dershowitz, Jean-pierre Jouannaud, Jan Willem Klop
We presented lists of open problems in the theory of rewriting in the proceedings of the previous two conferences [36; 37]. We continue with that tradition this year. We give references to solutions...
Completing Partial Combinatory Algebras with Unique Head-Normal Forms (1995)
I. Bethke, J. W. Klop, R. De Vrijer, Issn -x, Inge Bethke, Jan Willem Klop, ...
In this note, we prove that having unique head-normal forms is a sufficient condition on partial combinatory algebras to be completable. As application, we show that the pca of strongly normalizing...
Transfinite Reductions in Orthogonal Term Rewriting Systems (1995)
Richard Kennaway Jan, Jan Willem Klop
We define the notion of transfinite term rewriting: rewriting in which terms may be infinitely large and rewrite sequences may be of any ordinal length. For orthogonal rewrite systems, some...
Transfinite Reductions in Orthogonal Term Rewriting Systems (1995)
Richard Kennaway, Jan Willem Klop, Ronan Sleep
We define the notion of transfinite term rewriting: rewriting in which terms may be infinitely large and rewrite sequences may be of any ordinal length. For orthogonal rewrite systems, some...
Problems in Rewriting III (1995)
Nachum Dershowitz, Jean-pierre Jouannaud, Jan Willem Klop
Introduction We presented lists of open problems in the theory of rewriting in the proceedings of the previous two conferences [ 36; 37 ] . We continue with that tradition this year. We give...
Problems in Rewriting III (1995)
Nachum Dershowitz, Jan Willem Klop
Introduction We presented lists of open problems in the theory of rewriting in the proceedings of the previous two conferences [ 36; 37 ] . We continue with that tradition this year. We give...
Syntactic definitions of undefined: on defining the undefined (Extended Abstract) (1994)
Zena Ariola, Richard Kennaway, Jan Willem Klop
Zena Ariola 1 , Richard Kennaway 2 , Jan Willem Klop 3 , Ronan Sleep 4 and Fer-Jan de Vries 5 1 Computer and Information Science Department, University of Oregon, Eugene, Oregon 2;4 School of...
Cyclic Lambda Graph Rewriting (1994)
Zena M. Ariola, Jan Willem Klop
This paper is concerned with the study of cyclic - graphs. The starting point is to treat a -graph as a system of recursion equations involving -terms, and to manipulate such systems in an...
Modularity of confluence: A simplified proof (1994)
Jan Willem Klop, Aart Middeldorp, Yoshihito Toyama, Roel De Vrijer
In this note we present a simple proof of a result of Toyama which states that the disjoint union of confluent term rewriting systems is confluent.
Combinatory reduction systems: Introduction and survey (1993)
Jan Willem Klop, Vincent Van Oostrom, Femke Van Raamsdonk
Combinatory Reduction Systems, or CRSs for short, were designed to combine the usual first-order format of term rewriting with the presence of bound variables as in pure-calculus and various...
More problems in rewriting (1993)
Nachum Dershowitz, Jean-pierre Jouannaud, Jan Willem Klop
Two years ago, in the proceedings of the previous conference, we presented a list of open problems in the theory of rewriting [Dershowitz et al., 1991a]. This time, we report on progress made during...
Equational Term Graph Rewriting (1993)
Zena M. Ariola, Jan Willem Klop, De Boelelaan A, Hv Amsterdam
We present an equational framework for term graph rewriting with cycles. The usual notion of homomorphism is phrased in terms of the notion of bisimulation, which is well-known in process algebra and...
More Problems in Rewriting (1993)
Nachum Dershowitz, Jean-Pierre Jouannaud, Jan Willem Klop
Introduction Two years ago, in the proceedings of the previous conference, we presented a list of open problems in the theory of rewriting [ Dershowitz et al., 1991a ] . This time, we report on...
Open Problems in Rewriting (1991)
Nachum Dershowitz, Jean-pierre Jouannaud, Jan Willem Klop
Introduction Interest in the theory and applications of rewriting has been growing rapidly, as evidenced in part by four conference proceedings (including this one) [15, 26, 41, 66]; three workshop...