DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2015.423

Confluence of Layered Rewrite Systems

Authors: Jiaxiang Liu, Jean-Pierre Jouannaud, and Mizuhito Ogawa

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract

We investigate a new, Turing-complete class of layered systems, whose linearized lefthand sides of rules can only be overlapped at the root position. Layered systems define a natural notion of rank for terms: the maximal number of redexes along a path from the root to a leaf. Overlappings are allowed in finite or infinite trees. Rules may be non-terminating, non-left-linear, or non-right- linear. Using a novel unification technique, cyclic unification, we show that rank non-increasing layered systems are confluent provided their cyclic critical pairs have cyclic-joinable decreasing diagrams.

Cite as

Jiaxiang Liu, Jean-Pierre Jouannaud, and Mizuhito Ogawa. Confluence of Layered Rewrite Systems. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 423-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.CSL.2015.423,
  author =	{Liu, Jiaxiang and Jouannaud, Jean-Pierre and Ogawa, Mizuhito},
  title =	{{Confluence of Layered Rewrite Systems}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{423--440},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.423},
  URN =		{urn:nbn:de:0030-drops-54293},
  doi =		{10.4230/LIPIcs.CSL.2015.423},
  annote =	{Keywords: Layers, confluence, decreasing diagrams, critical pairs, cyclic unification}
}

Search Results

Documents authored by Ogawa, Mizuhito

Confluence of Layered Rewrite Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message