-
Characterisation of Lawvere-Tierney Topologies on Simplicial Sets, Bicolored Graphs, and Fuzzy Sets
Authors:
Aloïs Rosset,
Helle Hvid Hansen,
Jörg Endrullis
Abstract:
Simplicial sets generalize many categories of graphs. In this paper, we give a complete characterization of the Lawvere-Tierney topologies on (semi-)simplicial sets, on bicolored graphs, and on fuzzy sets. We apply our results to establish that 'partially simple' simplicial sets and 'partially simple' graphs form quasitoposes.
Simplicial sets generalize many categories of graphs. In this paper, we give a complete characterization of the Lawvere-Tierney topologies on (semi-)simplicial sets, on bicolored graphs, and on fuzzy sets. We apply our results to establish that 'partially simple' simplicial sets and 'partially simple' graphs form quasitoposes.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Correspondence between Composite Theories and Distributive Laws
Authors:
Aloïs Rosset,
Maaike Zwart,
Helle Hvid Hansen,
Jörg Endrullis
Abstract:
Composite theories are the algebraic equivalent of distributive laws. In this paper, we delve into the details of this correspondence and concretely show how to construct a composite theory from a distributive law and vice versa. Using term rewriting methods, we also describe when a minimal set of equations axiomatises the composite theory.
Composite theories are the algebraic equivalent of distributive laws. In this paper, we delve into the details of this correspondence and concretely show how to construct a composite theory from a distributive law and vice versa. Using term rewriting methods, we also describe when a minimal set of equations axiomatises the composite theory.
△ Less
Submitted 31 March, 2024;
originally announced April 2024.
-
Generalized Weighted Type Graphs for Termination of Graph Transformation Systems
Authors:
Jörg Endrullis,
Roy Overbeek
Abstract:
We refine the weighted type graph technique for proving termination of double pushout (DPO) graph transformation systems. We increase the power of the approach for graphs, we generalize the technique to other categories, and we allow for variations of DPO that occur in the literature.
We refine the weighted type graph technique for proving termination of double pushout (DPO) graph transformation systems. We increase the power of the approach for graphs, we generalize the technique to other categories, and we allow for variations of DPO that occur in the literature.
△ Less
Submitted 7 May, 2024; v1 submitted 14 July, 2023;
originally announced July 2023.
-
Termination of Graph Transformation Systems Using Weighted Subgraph Counting
Authors:
Roy Overbeek,
Jörg Endrullis
Abstract:
We introduce a termination method for the algebraic graph transformation framework PBPO+, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including S…
▽ More
We introduce a termination method for the algebraic graph transformation framework PBPO+, in which we weigh objects by summing a class of weighted morphisms targeting them. The method is well-defined in rm-adhesive quasitoposes (which include toposes and therefore many graph categories of interest), and is applicable to non-linear rules. The method is also defined for other frameworks, including SqPO and left-linear DPO, because we have previously shown that they are naturally encodable into PBPO+ in the quasitopos setting. We have implemented our method, and the implementation includes a REPL that can be used for guiding relative termination proofs.
△ Less
Submitted 14 December, 2023; v1 submitted 14 March, 2023;
originally announced March 2023.
-
Fuzzy Presheaves are Quasitoposes
Authors:
Aloïs Rosset,
Roy Overbeek,
Jörg Endrullis
Abstract:
Quasitoposes encompass a wide range of structures, including various categories of graphs. They have proven to be a natural setting for reasoning about the metatheory of algebraic graph rewriting. In this paper we propose and motivate the notion of fuzzy presheaves, which generalises fuzzy sets and fuzzy graphs. We prove that fuzzy presheaves are rm-adhesive quasitoposes, proving our recent conjec…
▽ More
Quasitoposes encompass a wide range of structures, including various categories of graphs. They have proven to be a natural setting for reasoning about the metatheory of algebraic graph rewriting. In this paper we propose and motivate the notion of fuzzy presheaves, which generalises fuzzy sets and fuzzy graphs. We prove that fuzzy presheaves are rm-adhesive quasitoposes, proving our recent conjecture for fuzzy graphs. Furthermore, we show that simple fuzzy graphs categories are quasitoposes.
△ Less
Submitted 20 March, 2023; v1 submitted 30 January, 2023;
originally announced January 2023.
-
A PBPO+ Graph Rewriting Tutorial
Authors:
Roy Overbeek,
Jörg Endrullis
Abstract:
We provide a tutorial introduction to the algebraic graph rewriting formalism PBPO+. We show how PBPO+ can be obtained by composing a few simple building blocks, and model the reduction rules for binary decision diagrams as an example. Along the way, we comment on how alternative design decisions lead to related formalisms in the literature, such as DPO. We close with a detailed comparison with Ba…
▽ More
We provide a tutorial introduction to the algebraic graph rewriting formalism PBPO+. We show how PBPO+ can be obtained by composing a few simple building blocks, and model the reduction rules for binary decision diagrams as an example. Along the way, we comment on how alternative design decisions lead to related formalisms in the literature, such as DPO. We close with a detailed comparison with Bauderon's double pullback approach.
△ Less
Submitted 28 March, 2023; v1 submitted 30 January, 2023;
originally announced January 2023.
-
Algebraic Presentation of Semifree Monads
Authors:
Aloïs Rosset,
Helle Hvid Hansen,
Jörg Endrullis
Abstract:
Monads and their composition via distributive laws have many applications in program semantics and functional programming. For many interesting monads, distributive laws fail to exist, and this has motivated investigations into weaker notions. In this line of research, Petrişan and Sarkis recently introduced a construction called the semifree monad in order to study semialgebras for a monad and we…
▽ More
Monads and their composition via distributive laws have many applications in program semantics and functional programming. For many interesting monads, distributive laws fail to exist, and this has motivated investigations into weaker notions. In this line of research, Petrişan and Sarkis recently introduced a construction called the semifree monad in order to study semialgebras for a monad and weak distributive laws. In this paper, we prove that an algebraic presentation of the semifree monad M^s on a monad M can be obtained uniformly from an algebraic presentation of M. This result was conjectured by Petrişan and Sarkis. We also show that semifree monads are ideal monads, that the semifree construction is not a monad transformer, and that the semifree construction is a comonad on the category of monads.
△ Less
Submitted 11 May, 2022;
originally announced May 2022.
-
Graph Rewriting and Relabeling with PBPO+: A Unifying Theory for Quasitoposes
Authors:
Roy Overbeek,
Jörg Endrullis,
Aloïs Rosset
Abstract:
We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO+, allows more control over the embedding of the pattern in the host graph, which is important for a large class of rewrite systems. We argue that PBPO+ can be considered a unifying theory in the general setting of quasitoposes, by demonstrating that PBPO+ can define a strict…
▽ More
We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO+, allows more control over the embedding of the pattern in the host graph, which is important for a large class of rewrite systems. We argue that PBPO+ can be considered a unifying theory in the general setting of quasitoposes, by demonstrating that PBPO+ can define a strict superset of the rewrite relations definable by PBPO, AGREE and DPO. Additionally, we show that PBPO+ is well suited for rewriting labeled graphs and some classes of attributed graphs, by introducing a lattice structure on the label set and requiring graph morphisms to be order-preserving.
△ Less
Submitted 25 May, 2023; v1 submitted 2 March, 2022;
originally announced March 2022.
-
From Linear Term Rewriting to Graph Rewriting with Preservation of Termination
Authors:
Roy Overbeek,
Jörg Endrullis
Abstract:
Encodings of term rewriting systems (TRSs) into graph rewriting systems usually lose global termination, meaning the encodings do not terminate on all graphs. A typical encoding of the terminating TRS rule a(b(x)) -> b(a(x)), for example, may be indefinitely applicable along a cycle of a's and b's. Recently, we introduced PBPO+, a graph rewriting formalism in which rules employ a type graph to spe…
▽ More
Encodings of term rewriting systems (TRSs) into graph rewriting systems usually lose global termination, meaning the encodings do not terminate on all graphs. A typical encoding of the terminating TRS rule a(b(x)) -> b(a(x)), for example, may be indefinitely applicable along a cycle of a's and b's. Recently, we introduced PBPO+, a graph rewriting formalism in which rules employ a type graph to specify transformations and control rule applicability. In the present paper, we show that PBPO+ allows for a natural encoding of linear TRS rules that preserves termination globally. This result is a step towards modeling other rewriting formalisms, such as lambda calculus and higher order rewriting, using graph rewriting in a way that preserves properties like termination and confluence. We moreover expect that the encoding can serve as a guide for lifting TRS termination methods to PBPO+ rewriting.
△ Less
Submitted 21 December, 2021; v1 submitted 25 June, 2021;
originally announced June 2021.
-
Graph Rewriting and Relabeling with PBPO+
Authors:
Roy Overbeek,
Jörg Endrullis,
Aloïs Rosset
Abstract:
We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called \pbpostrong, exerts more control over the embedding of the pattern in the host graph, which is important for a large class of graph rewrite systems. In addition, we show that \pbpostrong is well-suited for rewriting labeled graphs and certain classes of attributed graphs. For this…
▽ More
We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called \pbpostrong, exerts more control over the embedding of the pattern in the host graph, which is important for a large class of graph rewrite systems. In addition, we show that \pbpostrong is well-suited for rewriting labeled graphs and certain classes of attributed graphs. For this purpose, we employ a lattice structure on the label set and use order-preserving graph morphisms. We argue that our approach is simpler and more general than related relabeling approaches in the literature.
△ Less
Submitted 25 June, 2021; v1 submitted 16 October, 2020;
originally announced October 2020.
-
Patch Graph Rewriting (Extended Version)
Authors:
Roy Overbeek,
Jörg Endrullis
Abstract:
The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it.
We introduce the patch graph rewriting framework, a visual graph rewriting language with precise formal semantics. The language h…
▽ More
The basic principle of graph rewriting is the stepwise replacement of subgraphs inside a host graph. A challenge in such replacement steps is the treatment of the patch graph, consisting of those edges of the host graph that touch the subgraph, but are not part of it.
We introduce the patch graph rewriting framework, a visual graph rewriting language with precise formal semantics. The language has rich expressive power in two ways. Firstly, rules can flexibly constrain the permitted shapes of patches touching matching subgraphs. Secondly, rules can freely transform patches. While the framework is designed to be easy to understand, it subsumes many approaches to graph rewriting.
△ Less
Submitted 19 August, 2020; v1 submitted 13 March, 2020;
originally announced March 2020.
-
Star Games and Hydras
Authors:
Jörg Endrullis,
Jan Willem Klop,
Roy Overbeek
Abstract:
The recursive path ordering is an established and crucial tool in term rewriting to prove termination. We revisit its presentation by means of some simple rules on trees (or corresponding terms) equipped with a 'star' as control symbol, signifying a command to make that tree (or term) smaller in the order being defined. This leads to star games that are very convenient for proving termination of m…
▽ More
The recursive path ordering is an established and crucial tool in term rewriting to prove termination. We revisit its presentation by means of some simple rules on trees (or corresponding terms) equipped with a 'star' as control symbol, signifying a command to make that tree (or term) smaller in the order being defined. This leads to star games that are very convenient for proving termination of many rewriting tasks. For instance, using already the simplest star game on finite unlabeled trees, we obtain a very direct proof of termination of the famous Hydra battle, direct in the sense that there is not the usual mention of ordinals. We also include an alternative road to setting up the star games, using a proof method of Buchholz, adapted by van Oostrom, resulting in a quantitative version of the star as control symbol. We conclude with a number of questions and future research directions.
△ Less
Submitted 26 May, 2021; v1 submitted 23 January, 2020;
originally announced January 2020.
-
Decreasing Diagrams for Confluence and Commutation
Authors:
Jörg Endrullis,
Jan Willem Klop,
Roy Overbeek
Abstract:
Like termination, confluence is a central property of rewrite systems. Unlike for termination, however, there exists no known complexity hierarchy for confluence. In this paper we investigate whether the decreasing diagrams technique can be used to obtain such a hierarchy. The decreasing diagrams technique is one of the strongest and most versatile methods for proving confluence of abstract rewrit…
▽ More
Like termination, confluence is a central property of rewrite systems. Unlike for termination, however, there exists no known complexity hierarchy for confluence. In this paper we investigate whether the decreasing diagrams technique can be used to obtain such a hierarchy. The decreasing diagrams technique is one of the strongest and most versatile methods for proving confluence of abstract rewrite systems. It is complete for countable systems, and it has many well-known confluence criteria as corollaries.
So what makes decreasing diagrams so powerful? In contrast to other confluence techniques, decreasing diagrams employ a labelling of the steps with labels from a well-founded order in order to conclude confluence of the underlying unlabelled relation. Hence it is natural to ask how the size of the label set influences the strength of the technique. In particular, what class of abstract rewrite systems can be proven confluent using decreasing diagrams restricted to 1 label, 2 labels, 3 labels, and so on? Surprisingly, we find that two labels suffice for proving confluence for every abstract rewrite system having the cofinality property, thus in particular for every confluent, countable system.
Secondly, we show that this result stands in sharp contrast to the situation for commutation of rewrite relations, where the hierarchy does not collapse.
Thirdly, investigating the possibility of a confluence hierarchy, we determine the first-order (non-)definability of the notion of confluence and related properties, using techniques from finite model theory. We find that in particular Hanf's theorem is fruitful for elegant proofs of undefinability of properties of abstract rewrite systems.
△ Less
Submitted 19 February, 2020; v1 submitted 30 January, 2019;
originally announced January 2019.
-
Degrees of Infinite Words, Polynomials, and Atoms (Extended Version)
Authors:
Jörg Endrullis,
Juhani Karhumäki Jan Willem Klop,
Aleksi Saarela
Abstract:
We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words.
The word tr…
▽ More
We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words.
The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality.
We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.
△ Less
Submitted 8 March, 2018;
originally announced March 2018.
-
Coinductive Foundations of Infinitary Rewriting and Infinitary Equational Logic
Authors:
Jörg Endrullis,
Helle Hvid Hansen,
Dimitri Hendriks,
Andrew Polonsky,
Alexandra Silva
Abstract:
We present a coinductive framework for defining and reasoning about the infinitary analogues of equational logic and term rewriting in a uniform, coinductive way. The setup captures rewrite sequences of arbitrary ordinal length, but it has neither the need for ordinals nor for metric convergence. This makes the framework especially suitable for formalizations in theorem provers.
We present a coinductive framework for defining and reasoning about the infinitary analogues of equational logic and term rewriting in a uniform, coinductive way. The setup captures rewrite sequences of arbitrary ordinal length, but it has neither the need for ordinals nor for metric convergence. This makes the framework especially suitable for formalizations in theorem provers.
△ Less
Submitted 9 January, 2018; v1 submitted 31 May, 2017;
originally announced June 2017.
-
Undecidability and Finite Automata
Authors:
Jörg Endrullis,
Jeffrey Shallit,
Tim Smith
Abstract:
Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.
Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.
△ Less
Submitted 27 February, 2017; v1 submitted 5 February, 2017;
originally announced February 2017.
-
The Degree of Squares is an Atom (Extended Version)
Authors:
Jörg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks,
Hans Zantema
Abstract:
We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of degrees was carried out in (Endrullis, Hendriks, Klop, 2011), but many basic questions remain unanswered. One of the central questions concerns the existence of atom degrees, other than the degree of the `identity sequence'…
▽ More
We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of degrees was carried out in (Endrullis, Hendriks, Klop, 2011), but many basic questions remain unanswered. One of the central questions concerns the existence of atom degrees, other than the degree of the `identity sequence' 1 0^0 1 0^1 1 0^2 1 0^3 .... A degree is called an `atom' if below it there is only the bottom degree 0, which consists of the ultimately periodic sequences. We show that also the degree of the `squares sequence' 1 0^0 1 0^1 1 0^4 1 0^9 1 0^{16} ... is an atom. As the main tool for this result we characterise the transducts of `spiralling' sequences and their degrees. We use this to show that every transduct of a `polynomial sequence' either is in 0 or can be transduced back to a polynomial sequence for a polynomial of the same order.
△ Less
Submitted 2 June, 2015;
originally announced June 2015.
-
A Coinductive Framework for Infinitary Rewriting and Equational Reasoning (Extended Version)
Authors:
Jörg Endrullis,
Helle Hvid Hansen,
Dimitri Hendriks,
Andrew Polonsky,
Alexandra Silva
Abstract:
We present a coinductive framework for defining infinitary analogues of equational reasoning and rewriting in a uniform way. We define the relation =^infty, notion of infinitary equational reasoning, and ->^infty, the standard notion of infinitary rewriting as follows:
=^infty := nu R. ( <-_root + ->_root + lift(R) )^*
->^infty := mu R. nu S. ( ->_root + lift(R) )^* ; lift(S)
where
lift(R)…
▽ More
We present a coinductive framework for defining infinitary analogues of equational reasoning and rewriting in a uniform way. We define the relation =^infty, notion of infinitary equational reasoning, and ->^infty, the standard notion of infinitary rewriting as follows:
=^infty := nu R. ( <-_root + ->_root + lift(R) )^*
->^infty := mu R. nu S. ( ->_root + lift(R) )^* ; lift(S)
where
lift(R) := { (f(s_1,...,s_n), f(t_1,...,t_n)) | s_1 R t_1,...,s_n R t_n } + id ,
and where mu is the least fixed point operator and nu is the greatest fixed point operator.
The setup captures rewrite sequences of arbitrary ordinal length, but it has neither the need for ordinals nor for metric convergence. This makes the framework especially suitable for formalizations in theorem provers.
△ Less
Submitted 5 May, 2015;
originally announced May 2015.
-
Proving Looping and Non-Looping Non-Termination by Finite Automata
Authors:
Jörg Endrullis,
Hans Zantema
Abstract:
A new technique is presented to prove non-termination of term rewriting. The basic idea is to find a non-empty regular language of terms that is closed under rewriting and does not contain normal forms. It is automated by representing the language by a tree automaton with a fixed number of states, and expressing the mentioned requirements in a SAT formula. Satisfiability of this formula implies no…
▽ More
A new technique is presented to prove non-termination of term rewriting. The basic idea is to find a non-empty regular language of terms that is closed under rewriting and does not contain normal forms. It is automated by representing the language by a tree automaton with a fixed number of states, and expressing the mentioned requirements in a SAT formula. Satisfiability of this formula implies non-termination. Our approach succeeds for many examples where all earlier techniques fail, for instance for the S-rule from combinatory logic.
△ Less
Submitted 3 May, 2015;
originally announced May 2015.
-
Regularity Preserving but not Reflecting Encodings
Authors:
Jörg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks
Abstract:
Encodings, that is, injective functions from words to words, have been studied extensively in several settings. In computability theory the notion of encoding is crucial for defining computability on arbitrary domains, as well as for comparing the power of models of computation. In language theory much attention has been devoted to regularity preserving functions.
A natural question arising in t…
▽ More
Encodings, that is, injective functions from words to words, have been studied extensively in several settings. In computability theory the notion of encoding is crucial for defining computability on arbitrary domains, as well as for comparing the power of models of computation. In language theory much attention has been devoted to regularity preserving functions.
A natural question arising in these contexts is: Is there a bijective encoding such that its image function preserves regularity of languages, but its pre-image function does not? Our main result answers this question in the affirmative: For every countable class C of languages there exists a bijective encoding f such that for every language L in C its image f[L] is regular.
Our construction of such encodings has several noteworthy consequences. Firstly, anomalies arise when models of computation are compared with respect to a known concept of implementation that is based on encodings which are not required to be computable: Every countable decision model can be implemented, in this sense, by finite-state automata, even via bijective encodings. Hence deterministic finite-state automata would be equally powerful as Turing machine deciders.
A second consequence concerns the recognizability of sets of natural numbers via number representations and finite automata. A set of numbers is said to be recognizable with respect to a representation if an automaton accepts the language of representations. Our result entails that there is one number representation with respect to which every recursive set is recognizable.
△ Less
Submitted 20 January, 2015;
originally announced January 2015.
-
Eigenvalues and Transduction of Morphic Sequences: Extended Version
Authors:
David Sprunger,
William Tune,
Jörg Endrullis,
Lawrence S. Moss
Abstract:
We study finite state transduction of automatic and morphic sequences. Dekking proved that morphic sequences are closed under transduction and in particular morphic images. We present a simple proof of this fact, and use the construction in the proof to show that non-erasing transductions preserve a condition called alpha-substitutivity. Roughly, a sequence is alpha-substitutive if the sequence ca…
▽ More
We study finite state transduction of automatic and morphic sequences. Dekking proved that morphic sequences are closed under transduction and in particular morphic images. We present a simple proof of this fact, and use the construction in the proof to show that non-erasing transductions preserve a condition called alpha-substitutivity. Roughly, a sequence is alpha-substitutive if the sequence can be obtained as the limit of iterating a substitution with dominant eigenvalue alpha. Our results culminate in the following fact: for multiplicatively independent real numbers alpha and beta, if v is an alpha-substitutive sequence and w is a beta-substitutive sequence, then v and w have no common non-erasing transducts except for the ultimately periodic sequences. We rely on Cobham's theorem for substitutions, a recent result of Durand.
△ Less
Submitted 5 June, 2014;
originally announced June 2014.
-
An Introduction to the Clocked Lambda Calculus
Authors:
Jörg Endrullis,
Dimitri Hendriks,
Jan Willem Klop,
Andrew Polonsky
Abstract:
We give a brief introduction to the clocked lambda calculus, an extension of the classical lambda calculus with a unary symbol tau used to witness the beta-steps. In contrast to the classical lambda calculus, this extension is infinitary strongly normalising and infinitary confluent. The infinitary normal forms are enriched Boehm Trees, which we call clocked Boehm Trees.
We give a brief introduction to the clocked lambda calculus, an extension of the classical lambda calculus with a unary symbol tau used to witness the beta-steps. In contrast to the classical lambda calculus, this extension is infinitary strongly normalising and infinitary confluent. The infinitary normal forms are enriched Boehm Trees, which we call clocked Boehm Trees.
△ Less
Submitted 29 May, 2014;
originally announced May 2014.
-
Non-termination using Regular Languages
Authors:
Jörg Endrullis,
Hans Zantema
Abstract:
We describe a method for proving non-looping non-termination, that is, of term rewriting systems that do not admit looping reductions. As certificates of non-termination, we employ regular (tree) automata.
We describe a method for proving non-looping non-termination, that is, of term rewriting systems that do not admit looping reductions. As certificates of non-termination, we employ regular (tree) automata.
△ Less
Submitted 22 May, 2014;
originally announced May 2014.
-
Infinitary Term Rewriting for Weakly Orthogonal Systems: Properties and Counterexamples
Authors:
Joerg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks,
Jan Willem Klop,
Vincent van Oostrom
Abstract:
We present some contributions to the theory of infinitary rewriting for weakly orthogonal term rewrite systems, in which critical pairs may occur provided they are trivial. We show that the infinitary unique normal form property fails by an example of a weakly orthogonal TRS with two collapsing rules. By translating this example, we show that this property also fails for the infinitary lambda-bet…
▽ More
We present some contributions to the theory of infinitary rewriting for weakly orthogonal term rewrite systems, in which critical pairs may occur provided they are trivial. We show that the infinitary unique normal form property fails by an example of a weakly orthogonal TRS with two collapsing rules. By translating this example, we show that this property also fails for the infinitary lambda-beta-eta-calculus. As positive results we obtain the following: Infinitary confluence, and hence the infinitary unique normal forms property, holds for weakly orthogonal TRSs that do not contain collapsing rules. To this end we refine the compression lemma. Furthermore, we establish the triangle and diamond properties for infinitary multi-steps (complete developments) in weakly orthogonal TRSs, by refining an earlier cluster-analysis for the finite case.
△ Less
Submitted 5 June, 2014; v1 submitted 24 March, 2014;
originally announced March 2014.
-
A Coinductive Treatment of Infinitary Rewriting
Authors:
Joerg Endrullis,
Helle Hvid Hansen,
Dimitri Hendriks,
Andrew Polonsky,
Alexandra Silva
Abstract:
We introduce a coinductive definition of infinitary term rewriting. The setup is surprisingly simple, and has in contrast to the usual definitions of infinitary rewriting, neither need for ordinals nor for metric convergence. While the idea of a coinductive treatment of infinitary rewriting is not new, all previous approaches were limited to reductions of length at most omega. The approach present…
▽ More
We introduce a coinductive definition of infinitary term rewriting. The setup is surprisingly simple, and has in contrast to the usual definitions of infinitary rewriting, neither need for ordinals nor for metric convergence. While the idea of a coinductive treatment of infinitary rewriting is not new, all previous approaches were limited to reductions of length at most omega. The approach presented in this paper is the first to capture the full infinitary term rewriting with reductions of arbitrary ordinal length. Apart from an elegant reformulation of known concepts, our approach gives rise, in a very natural way, to a novel notion of infinitary equational reasoning.
△ Less
Submitted 10 April, 2014; v1 submitted 26 June, 2013;
originally announced June 2013.
-
Discriminating Lambda-Terms Using Clocked Boehm Trees
Authors:
Joerg Endrullis,
Dimitri Hendriks,
Jan Willem Klop,
Andrew Polonsky
Abstract:
As observed by Intrigila, there are hardly techniques available in the lambda-calculus to prove that two lambda-terms are not beta-convertible. Techniques employing the usual Boehm Trees are inadequate when we deal with terms having the same Boehm Tree (BT). This is the case in particular for fixed point combinators, as they all have the same BT. Another interesting equation, whose consideration…
▽ More
As observed by Intrigila, there are hardly techniques available in the lambda-calculus to prove that two lambda-terms are not beta-convertible. Techniques employing the usual Boehm Trees are inadequate when we deal with terms having the same Boehm Tree (BT). This is the case in particular for fixed point combinators, as they all have the same BT. Another interesting equation, whose consideration was suggested by Scott, is BY = BYS, an equation valid in the classical model P-omega of lambda-calculus, and hence valid with respect to BT-equality but nevertheless the terms are beta-inconvertible. To prove such beta-inconvertibilities, we employ `clocked' BT's, with annotations that convey information of the tempo in which the data in the BT are produced. Boehm Trees are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for lambda-terms. The corresponding equality is strictly intermediate between beta-convertibility and Boehm Tree equality, the equality in the model P-omega. An analogous approach pertains to Levy-Longo and Berarducci Trees. Our refined Boehm Trees find in particular an application in beta-discriminating fixed point combinators (fpc's). It turns out that Scott's equation BY = BYS is the key to unlocking a plethora of fpc's, generated by a variety of production schemes of which the simplest was found by Boehm, stating that new fpc's are obtained by postfixing the term SI, also known as Smullyan's Owl. We prove that all these newly generated fpc's are indeed new, by considering their clocked BT's. Even so, not all pairs of new fpc's can be discriminated this way. For that purpose we increase the discrimination power by a precision of the clock notion that we call `atomic clock'.
△ Less
Submitted 22 May, 2014; v1 submitted 3 December, 2012;
originally announced December 2012.
-
On Periodically Iterated Morphisms
Authors:
Joerg Endrullis,
Dimitri Hendriks
Abstract:
We investigate the computational power of periodically iterated morphisms, also known as D0L systems with periodic control, PD0L systems for short. These systems give rise to a class of one-sided infinite sequences, called PD0L words.
We construct a PD0L word with exponential subword complexity, thereby answering a question raised by Lepisto (1993) on the existence of such words. We solve anothe…
▽ More
We investigate the computational power of periodically iterated morphisms, also known as D0L systems with periodic control, PD0L systems for short. These systems give rise to a class of one-sided infinite sequences, called PD0L words.
We construct a PD0L word with exponential subword complexity, thereby answering a question raised by Lepisto (1993) on the existence of such words. We solve another open problem concerning the decidability of the first-order theories of PD0L words; we show it is already undecidable whether a certain letter occurs in a PD0L word. This stands in sharp contrast to the situation for D0L words (purely morphic words), which are known to have at most quadratic subword complexity, and for which the monadic theory is decidable.
The main result of our paper, leading to these answers, is that every computable word w over an alphabet Sigma can be embedded in a PD0L word u over an extended alphabet Gamma in the following two ways: (i) such that every finite prefix of w is a subword of u, and (ii) such that w is obtained from u by erasing all letters from Gamma not in Sigma. The PD0L system generating such a word u is constructed by encoding a Fractran program that computes the word w; Fractran is a programming language as powerful as Turing Machines.
As a consequence of (ii), if we allow the application of finite state transducers to PD0L words, we obtain the set of all computable words. Thus the set of PD0L words is not closed under finite state transduction, whereas the set of D0L words is. It moreover follows that equality of PD0L words (given by their PD0L system) is undecidable. Finally, we show that if erasing morphisms are admitted, then the question of productivity becomes undecidable, that is, the question whether a given PD0L system defines an infinite word.
△ Less
Submitted 10 July, 2012;
originally announced July 2012.
-
On the Complexity of Equivalence of Specifications of Infinite Objects
Authors:
Joerg Endrullis,
Dimitri Hendriks,
Rena Bakhshi
Abstract:
We study the complexity of deciding the equality of infinite objects specified by systems of equations, and of infinite objects specified by lambda-terms. For equational specifications there are several natural notions of equality: equality in all models, equality of the sets of solutions, and equality of normal forms for productive specifications. For lambda-terms we investigate Boehm-tree equali…
▽ More
We study the complexity of deciding the equality of infinite objects specified by systems of equations, and of infinite objects specified by lambda-terms. For equational specifications there are several natural notions of equality: equality in all models, equality of the sets of solutions, and equality of normal forms for productive specifications. For lambda-terms we investigate Boehm-tree equality and various notions of observational equality. We pinpoint the complexity of each of these notions in the arithmetical or analytical hierarchy. We show that the complexity of deciding equality in all models subsumes the entire analytical hierarchy. This holds already for the most simple infinite objects, viz. streams over {0,1}, and stands in sharp contrast to the low arithmetical Pi^0_2-completeness of equality of equationally specified streams derived in [Rosu 2006] employing a different notion of equality.
△ Less
Submitted 30 June, 2012;
originally announced July 2012.
-
Arithmetic Self-Similarity of Infinite Sequences
Authors:
Dimitri Hendriks,
Frits G. W. Dannenberg,
Joerg Endrullis,
Mark Dow,
Jan Willem Klop
Abstract:
We define the arithmetic self-similarity (AS) of a one-sided infinite sequence sigma to be the set of arithmetic progressions through sigma which are a vertical shift of sigma. We study the AS of several famlies of sequences, viz. completely additive sequences, Toeplitz words and Keane's generalized Morse sequences. We give a complete characterization of the AS of completely additive sequences, an…
▽ More
We define the arithmetic self-similarity (AS) of a one-sided infinite sequence sigma to be the set of arithmetic progressions through sigma which are a vertical shift of sigma. We study the AS of several famlies of sequences, viz. completely additive sequences, Toeplitz words and Keane's generalized Morse sequences. We give a complete characterization of the AS of completely additive sequences, and classify the set of single-gap Toeplitz patterns that yield completely additive Toeplitz words. We show that every arithmetic subsequence of a Toeplitz word generated by a one-gap pattern is again a Toeplitz word. Finally, we establish that generalized Morse sequences are specific sum-of-digits sequences, and show that their first difference is a Toeplitz word.
△ Less
Submitted 21 May, 2012; v1 submitted 18 January, 2012;
originally announced January 2012.
-
Automatic Sequences and Zip-Specifications
Authors:
Clemens Grabmayer,
Joerg Endrullis,
Dimitri Hendriks,
Jan Willem Klop,
Lawrence S. Moss
Abstract:
We consider infinite sequences of symbols, also known as streams, and the decidability question for equality of streams defined in a restricted format. This restricted format consists of prefixing a symbol at the head of a stream, of the stream function `zip', and recursion variables. Here `zip' interleaves the elements of two streams in alternating order, starting with the first stream. For examp…
▽ More
We consider infinite sequences of symbols, also known as streams, and the decidability question for equality of streams defined in a restricted format. This restricted format consists of prefixing a symbol at the head of a stream, of the stream function `zip', and recursion variables. Here `zip' interleaves the elements of two streams in alternating order, starting with the first stream. For example, the Thue-Morse sequence is obtained by the `zip-specification' {M = 0 : X, X = 1 : zip(X,Y), Y = 0 : zip(Y,X)}. Our analysis of such systems employs both term rewriting and coalgebraic techniques. We establish decidability for these zip-specifications, employing bisimilarity of observation graphs based on a suitably chosen cobasis. The importance of zip-specifications resides in their intimate connection with automatic sequences. We establish a new and simple characterization of automatic sequences. Thus we obtain for the binary zip that a stream is 2-automatic iff its observation graph using the cobasis (hd,even,odd) is finite. The generalization to zip-k specifications and their relation to k-automaticity is straightforward. In fact, zip-specifications can be perceived as a term rewriting syntax for automatic sequences. Our study of zip-specifications is placed in an even wider perspective by employing the observation graphs in a dynamic logic setting, leading to an alternative characterization of automatic sequences. We further obtain a natural extension of the class of automatic sequences, obtained by `zip-mix' specifications that use zips of different arities in one specification. We also show that equivalence is undecidable for a simple extension of the zip-mix format with projections like even and odd. However, it remains open whether zip-mix specifications have a decidable equivalence problem.
△ Less
Submitted 16 April, 2012; v1 submitted 16 January, 2012;
originally announced January 2012.
-
Local Termination: theory and practice
Authors:
Joerg Endrullis,
Roel de Vrijer,
Johannes Waldmann
Abstract:
The characterisation of termination using well-founded monotone algebras has been a milestone on the way to automated termination techniques, of which we have seen an extensive development over the past years. Both the semantic characterisation and most known termination methods are concerned with global termination, uniformly of all the terms of a term rewriting system (TRS). In this paper we co…
▽ More
The characterisation of termination using well-founded monotone algebras has been a milestone on the way to automated termination techniques, of which we have seen an extensive development over the past years. Both the semantic characterisation and most known termination methods are concerned with global termination, uniformly of all the terms of a term rewriting system (TRS). In this paper we consider local termination, of specific sets of terms within a given TRS. The principal goal of this paper is generalising the semantic characterisation of global termination to local termination. This is made possible by admitting the well-founded monotone algebras to be partial. We also extend our approach to local relative termination. The interest in local termination naturally arises in program verification, where one is probably interested only in sensible inputs, or just wants to characterise the set of inputs for which a program terminates. Local termination will be also be of interest when dealing with a specific class of terms within a TRS that is known to be non-terminating, such as combinatory logic (CL) or a TRS encoding recursive program schemes or Turing machines. We show how some of the well-known techniques for proving global termination, such as stepwise removal of rewrite rules and semantic labelling, can be adapted to the local case. We also describe transformations reducing local to global termination problems. The resulting techniques for proving local termination have in some cases already been automated. One of our applications concerns the characterisation of the terminating S-terms in CL as regular language. Previously this language had already been found via a tedious analysis of the reduction behaviour of S-terms. These findings have now been vindicated by a fully automated and verified proof.
△ Less
Submitted 7 September, 2010; v1 submitted 25 June, 2010;
originally announced June 2010.
-
Transforming Outermost into Context-Sensitive Rewriting
Authors:
Joerg Endrullis,
Dimitri Hendriks
Abstract:
We define two transformations from term rewriting systems (TRSs) to context-sensitive TRSs in such a way that termination of the target system implies outermost termination of the original system. In the transformation based on 'context extension', each outermost rewrite step is modeled by exactly one step in the transformed system. This transformation turns out to be complete for the class of le…
▽ More
We define two transformations from term rewriting systems (TRSs) to context-sensitive TRSs in such a way that termination of the target system implies outermost termination of the original system. In the transformation based on 'context extension', each outermost rewrite step is modeled by exactly one step in the transformed system. This transformation turns out to be complete for the class of left-linear TRSs. The second transformation is called `dynamic labeling' and results in smaller sized context-sensitive TRSs. Here each modeled step is adjoined with a small number of auxiliary steps. As a result state-of-the-art termination methods for context-sensitive rewriting become available for proving termination of outermost rewriting. Both transformations have been implemented in Jambox, making it the most successful tool in the category of outermost rewriting of the last edition of the annual termination competition.
△ Less
Submitted 29 June, 2010; v1 submitted 31 May, 2010;
originally announced May 2010.
-
Asynchronous Bounded Expected Delay Networks
Authors:
Rena Bakhshi,
Jörg Endrullis,
Wan Fokkink,
Jun Pang
Abstract:
The commonly used asynchronous bounded delay (ABD) network models assume a fixed bound on message delay. We propose a probabilistic network model, called asynchronous bounded expected delay (ABE) model. Instead of a strict bound, the ABE model requires only a bound on the expected message delay. While the conditions of ABD networks restrict the set of possible executions, in ABE networks all async…
▽ More
The commonly used asynchronous bounded delay (ABD) network models assume a fixed bound on message delay. We propose a probabilistic network model, called asynchronous bounded expected delay (ABE) model. Instead of a strict bound, the ABE model requires only a bound on the expected message delay. While the conditions of ABD networks restrict the set of possible executions, in ABE networks all asynchronous executions are possible, but executions with extremely long delays are less probable. In contrast to ABD networks, ABE networks cannot be synchronised efficiently. At the example of an election algorithm, we show that the minimal assumptions of ABE networks are sufficient for the development of efficient algorithms. For anonymous, unidirectional ABE rings of known size N we devise a probabilistic leader election algorithm having average message and time complexity O(N).
△ Less
Submitted 7 June, 2011; v1 submitted 10 March, 2010;
originally announced March 2010.
-
Levels of Undecidability in Infinitary Rewriting: Normalization and Reachability
Authors:
Joerg Endrullis
Abstract:
In [EGZ09] it has been shown that infinitary strong normalization (SNi) is Pi-1-1-complete. Suprisingly, it turns out that infinitary weak normalization (WNi) is a harder problem, being Pi-1-2-complete, and thereby strictly higher in the analytical hierarchy.
In [EGZ09] it has been shown that infinitary strong normalization (SNi) is Pi-1-1-complete. Suprisingly, it turns out that infinitary weak normalization (WNi) is a harder problem, being Pi-1-2-complete, and thereby strictly higher in the analytical hierarchy.
△ Less
Submitted 4 March, 2010;
originally announced March 2010.
-
Modular Construction of Fixed Point Combinators and Clocked Boehm Trees
Authors:
Joerg Endrullis,
Dimitri Hendriks,
Jan Willem Klop
Abstract:
Fixed point combinators (and their generalization: looping combinators) are classic notions belonging to the heart of lambda-calculus and logic. We start with an exploration of the structure of fixed point combinators (fpc's), vastly generalizing the well-known fact that if Y is an fpc, Y(SI) is again an fpc, generating the Boehm sequence of fpc's. Using the infinitary lambda-calculus we devise…
▽ More
Fixed point combinators (and their generalization: looping combinators) are classic notions belonging to the heart of lambda-calculus and logic. We start with an exploration of the structure of fixed point combinators (fpc's), vastly generalizing the well-known fact that if Y is an fpc, Y(SI) is again an fpc, generating the Boehm sequence of fpc's. Using the infinitary lambda-calculus we devise infinitely many other generation schemes for fpc's. In this way we find schemes and building blocks to construct new fpc's in a modular way.
Having created a plethora of new fixed point combinators, the task is to prove that they are indeed new. That is, we have to prove their beta-inconvertibility. Known techniques via Boehm Trees do not apply, because all fpc's have the same Boehm Tree (BT). Therefore, we employ `clocked BT's', with annotations that convey information of the tempo in which the data in the BT are produced. BT's are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for lambda-terms. The corresponding equality is strictly intermediate between beta-convertibility and BT-equality, the equality in the classical models of lambda-calculus. An analogous approach pertains to Levy-Longo Berarducci trees. Finally, we increase the discrimination power by a precision of the clock notion that we call `atomic clock'.
△ Less
Submitted 12 February, 2010;
originally announced February 2010.
-
Unique Normal Forms in Infinitary Weakly Orthogonal Term Rewriting
Authors:
Joerg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks,
Jan Willem Klop
Abstract:
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 contributions to the latter case of weak orthogonality, where critial pairs are admitted provided they are trivial.
We start with a refinement of the by now classical Compression Lemma, as a tool f…
▽ More
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 contributions to the latter case of weak orthogonality, where critial pairs are admitted provided they are trivial.
We start with a refinement of the by now classical Compression Lemma, as a tool for establishing infinitary confluence, and hence the property of unique infinitary normal forms, for the case of weakly orthogonal TRSs that do not contain collapsing rewrite rules.
That this restriction of collapse-freeness is crucial, is shown in a elaboration of a simple TRS which is weakly orthogonal, but has two collapsing rules. It turns out that all the usual theory breaks down dramatically.
We conclude with establishing a positive fact: the diamond property for infinitary developments for weakly orthogonal TRSs, by means of a detailed analysis initiated by van Oostrom for the finite case.
△ Less
Submitted 5 November, 2009;
originally announced November 2009.
-
Let's Make a Difference!
Authors:
Joerg Endrullis,
Dimitri Hendriks,
Jan Willem Klop
Abstract:
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 differences sigma, delta(sigma), delta(delta(sigma)), ..., the `delta-orbit' of sigma as we call it, is eventually periodic. Moreover, we generalise this result to operations delta_d that sum modulo 2 the ele…
▽ More
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 differences sigma, delta(sigma), delta(delta(sigma)), ..., the `delta-orbit' of sigma as we call it, is eventually periodic. Moreover, we generalise this result to operations delta_d that sum modulo 2 the elements of each consecutive block of length d+1 in a given 01-stream. Some experimentation with delta-orbits of well-known streams reveals a surprising connexion between the Sierpinski stream and the Mephisto Waltz.
△ Less
Submitted 5 November, 2009;
originally announced November 2009.
-
Complexity of Fractran and Productivity
Authors:
Joerg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks
Abstract:
In functional programming languages the use of infinite structures is common practice. For total correctness of programs dealing with infinite structures one must guarantee that every finite part of the result can be evaluated in finitely many steps. This is known as productivity. For programming with infinite structures, productivity is what termination in well-defined results is for programmin…
▽ More
In functional programming languages the use of infinite structures is common practice. For total correctness of programs dealing with infinite structures one must guarantee that every finite part of the result can be evaluated in finitely many steps. This is known as productivity. For programming with infinite structures, productivity is what termination in well-defined results is for programming with finite structures.
Fractran is a simple Turing-complete programming language invented by Conway. We prove that the question whether a Fractran program halts on all positive integers is Pi^0_2-complete. In functional programming, productivity typically is a property of individual terms with respect to the inbuilt evaluation strategy. By encoding Fractran programs as specifications of infinite lists, we establish that this notion of productivity is Pi^0_2-complete even for the most simple specifications. Therefore it is harder than termination of individual terms. In addition, we explore possible generalisations of the notion of productivity in the framework of term rewriting, and prove that their computational complexity is Pi^1_1-complete, thus exceeding the expressive power of first-order logic.
△ Less
Submitted 31 July, 2009; v1 submitted 25 March, 2009;
originally announced March 2009.
-
Degrees of Undecidability in Rewriting
Authors:
Joerg Endrullis,
Herman Geuvers,
Hans Zantema
Abstract:
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This gives rise to a hierarchy of distinct levels of undecidability, starting from the arithmetical hierarchy classifying properties using first order arithmetical formulas and continuing into the analytic hierarchy, whe…
▽ More
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This gives rise to a hierarchy of distinct levels of undecidability, starting from the arithmetical hierarchy classifying properties using first order arithmetical formulas and continuing into the analytic hierarchy, where also quantification over function variables is allowed.
In this paper we consider properties of first order term rewriting systems and classify them in this hierarchy. Weak and strong normalization for single terms turn out to be Sigma-0-1-complete, while their uniform versions as well as dependency pair problems with minimality flag are Pi-0-2-complete. We find that confluence is Pi-0-2-complete both for single terms and uniform. Unexpectedly weak confluence for ground terms turns out to be harder than weak confluence for open terms. The former property is Pi-0-2-complete while the latter is Sigma-0-1-complete (and thereby recursively enumerable).
The most surprising result is on dependency pair problems without minimality flag: we prove this to be Pi-1-1-complete, which means that this property exceeds the arithmetical hierarchy and is essentially analytic.
△ Less
Submitted 26 February, 2009;
originally announced February 2009.
-
Data-Oblivious Stream Productivity
Authors:
Joerg Endrullis,
Clemens Grabmayer,
Dimitri Hendriks
Abstract:
We are concerned with demonstrating productivity of specifications of infinite streams of data, based on orthogonal rewrite rules. In general, this property is undecidable, but for restricted formats computable sufficient conditions can be obtained. The usual analysis disregards the identity of data, thus leading to approaches that we call data-oblivious. We present a method that is provably opt…
▽ More
We are concerned with demonstrating productivity of specifications of infinite streams of data, based on orthogonal rewrite rules. In general, this property is undecidable, but for restricted formats computable sufficient conditions can be obtained. The usual analysis disregards the identity of data, thus leading to approaches that we call data-oblivious. We present a method that is provably optimal among all such data-oblivious approaches. This means that in order to improve on the algorithm in this paper one has to proceed in a data-aware fashion.
△ Less
Submitted 19 July, 2008; v1 submitted 16 June, 2008;
originally announced June 2008.
