Equational theorem proving for clauses over strings
Author:
Open Access
- 18 April 2024
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 34 (10) , 1055-1078
Abstract
Although reasoning about equations over strings has been extensively studied for several decades, little research has been done for equational reasoning on general clauses over strings. This paper introduces a new superposition calculus with strings and present an equational theorem proving framework for clauses over strings. It provides a saturation procedure for clauses over strings and show that the proposed superposition calculus with contraction rules is refutationally complete. In particular, this paper presents a new decision procedure for solving word problems over strings and provides a new method of solving unification problems over strings w.r.t. a set of conditional equations R over strings if R can be finitely saturated under the proposed inference system with contraction rules.Keywords
This publication has 29 references indexed in Scilit:
- Equational Theorem Proving Modulo2021
- Theorem Proving with Sequence Variables and Flexible Arity SymbolsLecture Notes in Computer Science, 2002
- Cross-sections for finitely presented monoids with decidable word problemsLecture Notes in Computer Science, 1997
- Unification and matching modulo nilpotenceLecture Notes in Computer Science, 1996
- Theorem proving modulo associativity1996
- Associative-commutative superpositionLecture Notes in Computer Science, 1995
- String-Rewriting Systems1993
- Conditional semi-Thue systems for presenting monoids1992
- A specialized completion procedure for monadic string-rewriting systems presenting groups1991
- Canonical sets of horn clauses1991