Congruences Generated by Extended Ground Term Rewrite Systems

被引：1
作者：
Vagvolgyi, Sandor [1 ]
机构：
[1] Univ Szeged, Dept Fdn Comp Sci, Szeged, Hungary
来源：
FUNDAMENTA INFORMATICAE | 2009年 / 95卷 / 2-3期
关键词：
extended ground term rewrite system; tree automaton; DECIDABILITY; CONFLUENCE;
D O I：
10.3233/FI-2009-155
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：381 / 399
页数：19
相关论文
共 17 条
[1]  
[Anonymous], 1998, Term rewriting and all thatM
[2]   BASIC PARAMODULATION [J].
BACHMAIR, L ;
GANZINGER, H ;
LYNCH, C ;
SNYDER, W .
INFORMATION AND COMPUTATION, 1995, 121 (02) :172-192
[3]   TREE GENERATING REGULAR SYSTEMS [J].
BRAINERD, WS .
INFORMATION AND CONTROL, 1969, 14 (02) :217-&
[4]  
Buchi J. R., 1964, Archiv fur mathematische Logik und Grundlagenforschung, V6, P91, DOI DOI 10.1007/BF01969548
[5]  
Comon H., 2008, Tree Automata Techniques and Applications
[6]   DECIDABILITY OF THE CONFLUENCE OF FINITE GROUND TERM REWRITE SYSTEMS AND OF OTHER RELATED TERM REWRITE SYSTEMS [J].
DAUCHET, M ;
HEUILLARD, T ;
LESCANNE, P ;
TISON, S .
INFORMATION AND COMPUTATION, 1990, 88 (02) :187-201
[7]  
Dauchet M., 1990, Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science (90CH2897-7), P242, DOI 10.1109/LICS.1990.113750
[8]  
DAUCHET M, 1985, LECT NOTES COMPUT SC, V199, P80
[9]   Derivation trees of ground term rewriting systems [J].
Engelfriet, J .
INFORMATION AND COMPUTATION, 1999, 152 (01) :1-15
[10]   Restricted ground tree transducers [J].
Fülöp, Z ;
Vágvölgyi, S .
THEORETICAL COMPUTER SCIENCE, 2001, 250 (1-2) :219-233
12