Confluence of Conditional Rewriting Modulo

被引:1
作者
Lucas, Salvador [1 ,2 ]
机构
[1] Univ Politecn Valencia, DSIC, Valencia, Spain
[2] Univ Politecn Valencia, VRAIN, Valencia, Spain
来源
32ND EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC, CSL 2024 | 2024年 / 288卷
关键词
Conditional rewriting; Confluence; Program analysis; REDUCTIONS;
D O I
10.4230/LIPIcs.CSL.2024.37
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We investigate confluence of rewriting with Equational Generalized Term Rewriting Systems R, consisting of Horn clauses, some of them defining conditional equations s = t double left arrow c and rewriting rules l -> r double left arrow c. In both cases, c is a sequence of atoms, possibly defined by using additional Horn clauses. Such systems include Equational Term Rewriting Systems and (join, oriented, and semi-equational) Conditional Term Rewriting Systems. A set of equations E defines an equivalence = E and quotient set T (F, X)/= E of terms, where reductions s ->(R/E) t using rules in R occur. For such systems, we obtain a finite set of conditional pairs pi, which can be viewed as logical sentences, to prove and disprove confluence of ->(R/E) by (dis)proving joinability of such conditional pairs pi.
引用
收藏
页数:21
相关论文
共 23 条
  • [1] Baader F., 2001, HDB AUTOMATED REASON, V8, P445, DOI DOI 10.1016/B978-044450813-3/50010-2
  • [2] Baader Franz, 1998, Term rewriting and all that, pI, DOI [DOI 10.1017/CBO9781139172752, 10.1017/CBO9781139172752]
  • [3] Dowek G, 2023, Arxiv, DOI [arXiv:2306.00498, 10.48550/ARXIV.2306.00498, DOI 10.48550/ARXIV.2306.00498]
  • [4] On the Church-Rosser and coherence properties of conditional order-sorted rewrite theories
    Duran, Francisco
    Meseguer, Jose
    [J]. JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING, 2012, 81 (7-8): : 816 - 850
  • [5] Fitting M., 1996, First-Order Logic and Automated Theorem Proving, V2nd
  • [6] Confluence Framework: Proving Confluence with CONFident
    Gutierrez, Raul
    Vitores, Miguel
    Lucas, Salvador
    [J]. LOGIC-BASED PROGRAM SYNTHESIS AND TRANSFORMATION (LOPSTR 2022), 2022, 13474 : 24 - 43
  • [7] Automatically Proving and Disproving Feasibility Conditions
    Gutierrez, Raul
    Lucas, Salvador
    [J]. AUTOMATED REASONING, PT II, 2020, 12167 : 416 - 435
  • [8] Automatic Generation of Logical Models with AGES
    Gutierrez, Raul
    Lucas, Salvador
    [J]. AUTOMATED DEDUCTION, CADE 27, 2019, 11716 : 287 - 299
  • [10] JOUANNAUD JP, 1983, LECT NOTES COMPUT SC, V159, P269