Congruences Generated by Extended Ground Term Rewrite Systems

Article type: Research Article

Authors: Vágvölgyi, Sándor

Affiliations: Department of Foundations of Computer Science, University of Szeged, Hungary. E-mail: vagvolgy@inf.u-szeged.hu

Abstract: We show that it is decidable for any extended ground term rewrite system R whether there is a ground term rewrite system S such that the congrunce ↔^*_R generated by R is equal to the congruence ↔^*_S generated by S. If the answer is yes, then we can effectively construct such a ground term rewrite system S. We characterize congruences generated by extended ground term rewrite systems.

Keywords: Extended ground term rewrite system, tree automaton

DOI: 10.3233/FI-2009-155

Journal: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 381-399, 2009