文章基本信息

标题：A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods
本地全文：下载
作者：Mirai Ikebuchi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：131
页码：1-18
DOI：10.4230/LIPIcs.FSCD.2019.24
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Term rewriting systems; Equational logic; Homological algebra