Deciding the Word Problem for Ground Identities with Commutative and Extensional Symbols
- 24 June 2020
- book chapter
- Published by Springer Nature
- Vol. 12166, 163-180
Abstract
The word problem for a finite set of ground identities is known to be decidable in polynomial time, and this is also the case if some of the function symbols are assumed to be commutative. We show that decidability in P is preserved if we also assume that certain function symbols f are extensional in the sense that \(f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)\) implies \(s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n\). In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP.
Keywords
This publication has 17 references indexed in Scilit:
- Conditional Congruence Closure over Uninterpreted and Interpreted SymbolsJournal of Systems Science and Complexity, 2019
- An Introduction to Description Logic2017
- Congruence Closure Modulo Associativity and CommutativityLecture Notes in Computer Science, 2000
- Term Rewriting and All That1998
- Shostak's congruence closure as completion1997
- An algorithm for finding canonical sets of ground rewrite rules in polynomial timeJournal of the ACM, 1993
- Any ground associative-commutative theory has a finite canonical system1991
- The theorem prover of the program verifier Tatzelwurm1990
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Complexity of finitely presented algebras1977