文章基本信息

标题：A LOWER BOUND OF THE NUMBER OF REWRITE RULES OBTAINED BY HOMOLOGICAL METHODS
本地全文：下载
作者：Mirai Ikebuchi.
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2022
卷号：18
期号：3
页码：1-25
DOI：10.46298/lmcs-18(3:36)2022
语种：English
出版社：Technical University of Braunschweig
摘要：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, and experimented with 64 complete TRSs.
关键词：Term rewriting systems;Equational logic;Homological algebra. The author thanks Keisuke Nakano for comments that greatly improved the manuscript and Aart Middeldorp for his suggestion about prime critical pairs.