The unifiability problem in ground AC theories
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 364-370
- https://doi.org/10.1109/lics.1993.287572
Abstract
It is shown that unifiability is decidable in theories presented by a set of ground equations with several associative-communicative symbols (ground AC theories). This result applies, for instance, to finitely presented commutative semigroups, and it extends the authors' previous work (P. Narendran and M. Rusinwithch, 1991) where they gave an algorithm for solving the uniform word problem in ground AC theories.Keywords
This publication has 7 references indexed in Scilit:
- Finding canonical rewriting systems equivalent to a finite set of ground equations in polynomial timePublished by Springer Nature ,2005
- Unification theoryJournal of Symbolic Computation, 1989
- Matching, unification and complexityACM SIGSAM Bulletin, 1987
- A Unification Algorithm for Associative-Commutative FunctionsJournal of the ACM, 1981
- Complete Sets of Reductions for Some Equational TheoriesJournal of the ACM, 1981
- An algorithm for the general Petri net reachability problemPublished by Association for Computing Machinery (ACM) ,1981
- Canonical forms and unificationPublished by Springer Nature ,1980