Congruences Generated by Extended Ground Term Rewrite Systems

• Autorzy: Vagvölgyi S.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

extended ground term rewrite system; tree automaton

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 95, nr 2/3
• Strony: 381--399
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Vagvölgyi S.

• Árpád tér 2, H-6720 Szeged, Hungary,

Bibliografia

• [1] Baader, F., Nipkow, T.: Term Rewriting and All That, Cambridge University Press, United Kingdom 1998.
• [2] Bachmair, L., Ganzinger, H., Lynch, C., Snyder, W.: Basic Paramodulation, Information and Computation, 121, 1995(2), 172-192.
• [3] Brainerd,W. S.: Tree generating regular systems, Information and Control, 14, 1969(2), 217-231.
• [4] Büchi, J. R.: Regular canonical systems, Archiv für Mathematische Logik und Grundlagenforschung, 6 (1964) 91-111.
• [5] Comon, H., Dauchet,M., Gilleron, R., Jacquemard, F., Lugiez, D., Lőding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, http://www.grappa.univ-lille3.fr/tata, 2007.
• [6] Dauchet, M., Tison, S., Decidability of confluence for ground term rewriting systems, Proc. Fundamentals of Computation Theory, FCT '85, (L. Budach, Ed.), LNCS 199, Springer Verlag, Berlin, 1985, 80-89.
• [7] Dauchet,M., Heuillard, P., Lescanne, P., Tison, S: Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems, Information and Control, 88(2), 1990, 187-201.
• [8] Dauchet,M., Tison, S: The Theory of Ground Rewrite Systems is Decidable, Proceedings of the Fifth Annual Symposium on Logic in Computer Science (LICS '90), (J. Mitchell, Ed.), IEEE Computer Society Press, 1990, Philadelphia, PA, USA, 242-248.
• [9] Engelfriet, J.: Derivation Trees of Ground Term Rewriting Systems, Information and Computation, 152(1), 1999, 1-15.
• [10] Fülőp, Z., Vágvőlgyi, S.: Ground term rewriting rules for the word problem of ground term equations, Bulletin of the European Association for Theoretical Computer Science, 45, 1991, 186-201.
• [11] Fülőp, Z., Vágvőlgyi, S.: Minimal equational representations of recognizable tree languages, Acta Informatica, 34, 1997, 59-84.
• [12] Fülőp, Z., Vágvőlgyi, Restricted ground tree transducers. Theoretical Computer Science, 250(1-2), 2001, 219-233.
• [13] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiadó, Budapest, 1984.
• [14] R. Nieuwenhuis, A. Rubio: Paramodulation-Based Theorem Proving, (J. A. Robinson, A. Voronkov Eds.), Handbook of Automated Reasoning Volume 1, Elsevier and MIT Press 2001, 371-443.
• [15] Snyder, W.: A Fast Algorithm for Generating Reduced Ground Rewriting Systems from a set of Ground Equations, Journal of Symbolic Computation, 15(4), 1993, 415-450.
• [16] Vágvőlgyi, S.: Term rewriting restricted to ground terms, Theoretical Computer Science, 302(1-3), 2003, 135-165.
• [17] Vágvőlgyi, S.: Left-linear Right-ground Term Rewrite Systems and Ground Term Rewrite Systems, Bulletin of the European Association for Theoretical Computer Science, 82, 2004, 269-285.