2018

  1. Decreasing Diagrams with Two Labels Are Complete for Confluence of Countable Systems
    Jörg Endrullis, Jan Willem Klop, and Roy Overbeek
    In: Proc. Conf. on Formal Structures for Computation and Deduction (FSCD 2018), pp. 14:1–14:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
    paper

    Summary

    The decreasing diagrams technique is one of the strongest and most versatile methods for proving confluence of abstract reduction systems. So what makes decreasing diagrams so powerful? In contrast to other confluence techniques, decreasing diagrams employ a labelling of the steps.

    In this paper we investigate how the size of the label set influences the strength of the technique. Surprisingly, we find that two labels suffice for proving confluence of every confluent, countable system. In contrast, for proving commutation of rewrite relations, it turns out that the strength of the technique increases with more labels.

    While decreasing diagrams is complete for proving confluence of countable systems, the technique is not complete for commutation. In our paper De Bruijn's Weak Diamond Property Revisited we give a counterexample to the completeness of decreasing diagrams for commutation.

    See research for an overview of my research on confluence.

    Bibtex

    @inproceedings{confluence:decreasing:diagrams:2018,
  author = {Endrullis, J{\"{o}}rg and Klop, Jan Willem and Overbeek, Roy},
  title = {{Decreasing Diagrams with Two Labels Are Complete for Confluence of Countable Systems}},
  booktitle = {Proc.\ Conf.\ on Formal Structures for Computation and Deduction (FSCD~2018)},
  volume = {108},
  pages = {14:1--14:15},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  series = {LIPIcs},
  year = {2018},
  doi = {10.4230/LIPIcs.FSCD.2018.14},
  keywords = {rewriting, confluence},
  type = {conference}
}

    Digital Object Identifier

    10.4230/LIPIcs.FSCD.2018.14
  2. Degrees of Infinite Words, Polynomials and Atoms
    Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi Saarela
    International Journal of Foundations of Computer Science , 29 (5) , pp. 825–843 (2018)
    paper

    Summary

    A finite state transducer is a finite automaton that transforms input words into output words. The transducer reads the input letter by letter, in each step producing an output word and changing its state.

    While finite state transducers are very simple and elegant devices, their power in transforming infinite words is hardly understood.

    In this paper we show that techniques from continuous mathematics can be used to reason about finite state transducers. To be precise, we use the following methods from linear algebra and analysis:

    • continuity,
    • Vandermonde matrices,
    • invertibility of matrices, and
    • the generalised mean inequality.
    We employ these techniques to obtain both positive and negative results on transducibility.

    The main result in this paper is the existance of an infinite number of atoms in the hierarchy of streams arising from finite state transduction.

    This paper is an extended version of Degrees of Infinite Words, Polynomials and Atoms presented at the Conference on Developments in Language Theory (DLT), 2016.

    See research for an introduction to finite state transducers, an overview of my research and many open questions.

    Bibtex

    @article{streams:degrees:polynomials:2018,
  author = {Endrullis, J\"{o}rg and Karhum{\"{a}}ki, Juhani and Klop, Jan Willem and Saarela, Aleksi},
  title = {{Degrees of Infinite Words, Polynomials and Atoms}},
  journal = {International Journal of Foundations of Computer Science},
  volume = {29},
  number = {5},
  pages = {825--843},
  year = {2018},
  doi = {10.1142/S0129054118420066},
  keywords = {streams, degrees, automata},
  type = {journal}
}

    Digital Object Identifier

    10.1142/S0129054118420066
  3. Coinductive Foundations of Infinitary Rewriting and Infinitary Equational Logic
    Jörg Endrullis, Helle Hvid Hansen, Dimitri Hendriks, Andrew Polonsky, and Alexandra Silva
    Logical Methods in Computer Science , 14 (1) (2018)
    paper

    Summary

    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 framework lends itself to an elegant and concise definition of the infinitary rewrite relation \( \to^\infty \) in terms of the single step relation \( \to \): \[ {\to^\infty} \,=\, \mu R. \nu S. ( \to \cup \mathrel{\overline{R}} )^* \mathrel{;} \overline{S} \] Here \( \mu \) and \( \nu \) are the least and greatest fixed-point operators, respectively, and \[ \overline{R} \,=\, \{\, (\, f(s_1,\ldots,s_n),\, \,f(t_1,\ldots,t_n) \,) \mid f \in \Sigma,\, s_1\! \mathrel{R} t_1,\ldots,s_n\! \mathrel{R} t_n \,\} \cup \text{Id} \] 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 suitable for formalizations in theorem provers. To wit, we provide the first formalization of the compression lemma in Coq.

    This paper is an extended version of A Coinductive Framework for Infinitary Rewriting and Equational Reasoning (RTA 2015). We build on ideas in Infinitary Rewriting Coinductively (TYPES 2012) giving a coinductive perspective on infinitary lambda calculus. We extend these ideas to rewrite sequences beyond length omega by mixing induction and coinduction (least and greatest fixed-points).

    Bibtex

    @article{infintary:rewriting:coinductive:2018,
  author = {Endrullis, J\"{o}rg and Hansen, Helle Hvid and Hendriks, Dimitri and Polonsky, Andrew and Silva, Alexandra},
  title = {{Coinductive Foundations of Infinitary Rewriting and Infinitary Equational Logic}},
  journal = {Logical Methods in Computer Science},
  volume = {14},
  number = {1},
  year = {2018},
  doi = {10.23638/LMCS-14(1:3)2018},
  keywords = {rewriting, infinitary rewriting, coinduction},
  type = {journal}
}

    Digital Object Identifier

    10.23638/LMCS-14(1:3)2018