License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2019.24
URN: urn:nbn:de:0030-drops-105312
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10531/
Go to the corresponding LIPIcs Volume Portal

Ikebuchi, Mirai

A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods

pdf-format:
LIPIcs-FSCD-2019-24.pdf (0.6 MB)

Abstract

It is well-known that some equational theories such as groups or boolean algebras can be defined by fewer equational axioms than the original axioms. However, it is not easy to determine if a given set of axioms is the smallest or not. Malbos and Mimram investigated a general method to find a lower bound of the cardinality of the set of equational axioms (or rewrite rules) that is equivalent to a given equational theory (or term rewriting systems), using homological algebra. Their method is an analog of Squier's homology theory on string rewriting systems. In this paper, we develop the homology theory for term rewriting systems more and provide a better lower bound under a stronger notion of equivalence than their equivalence. The author also implemented a program to compute the lower bounds.

BibTeX - Entry

@InProceedings{ikebuchi:LIPIcs:2019:10531,
  author =	{Mirai Ikebuchi},
  title =	{{A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Herman Geuvers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10531},
  URN =		{urn:nbn:de:0030-drops-105312},
  doi =		{10.4230/LIPIcs.FSCD.2019.24},
  annote =	{Keywords: Term rewriting systems, Equational logic, Homological algebra}
}

Keywords: Term rewriting systems, Equational logic, Homological algebra
Collection: 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)
Issue Date: 2019
Date of publication: 18.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI