Guillem Godoy, Ashish Tiwari, Rakesh Verma  @ NUS Home/Search
Context Related
| sri.com/~tiwari/stacs2003.ps Cached: PS.gz PS PDF Image Update Help From: sri.com/users/tiwari/stacs2003 (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We show that the confluence of shallow linear term rewrite systems is decidable. The decision procedure is a nontrivial generalization of the polynomial time algorithms for deciding confluence of ground and restricted non-ground term rewrite systems presented in [13, 2]. Our algorithm has a polynomial time complexity if the maximum arity of a function symbol in the signature is considered a constant. We also give EXPTIME-hardness proofs for reachability and confluence of shallow term... (Update)
Cited by: More
Deciding Fundamental Properties of Right-(Ground or - Variable Rewrite Systems (Correct)
Active bibliography (related documents): More All
1.3: Deciding Confluence of Certain Term Rewriting Systems in.. - Tiwari (2002) (Correct)
0.4: Rewrite Closure for Ground and Cancellative AC Theories - Tiwari (2001) (Correct)
0.3: Rewrite Closures for Ground and Cancellative AC Theories - Tiwari (2001) (Correct)
Similar documents based on text: More All
0.6: Classes of Term Rewrite Systems with Polynomial.. - Godoy, Nieuwenhuis.. (2002) (Correct)
0.3: The Confluence of Ground Term Rewrite Systems is Decidable in.. - Comon, Godoy (2001) (Correct)
0.3: Cv - Tiwari (Correct)
Related documents from co-citation: More All
2: Characterizing confluence by rewrite closure and right ground term rewrite syste.. (context) - Godoy, Tiwari et al. - 2004
BibTeX entry: (Update)
G. Godoy, A. Tiwari, and R. Verma. On the confluence of linear shallow term rewrite systems. In H. Alt, editor, 20th Intl. Symposium on Theoretical Aspects of Computer Science STACS 2003, volume 2607 of LNCS, pages 85--96. Springer, February 2003. http://citeseer.comp.nus.edu.sg/696872.html More
@misc{ godoy03confluence,
author = "G. Godoy and A. Tiwari and R. Verma",
title = "the confluence of linear shallow term rewrite systems",
text = "G. Godoy, A. Tiwari, and R. Verma. On the confluence of linear shallow
term rewrite systems. In H. Alt, editor, 20th Intl. Symposium on Theoretical
Aspects of Computer Science STACS 2003, volume 2607 of LNCS, pages 85--96.
Springer, February 2003.",
year = "2003",
url = "citeseer.comp.nus.edu.sg/696872.html" }
Citations (may not include all citations):384 Simple word problems in universal algebras (context) - Knuth, Bendix - 1970
89 Termination of term rewriting: interpretation and type elimi.. - Zantema - 1994
58 Canonical Equational Proofs (context) - Bachmair - 1991
28 Information and Computation (context) - Comon, Haberstrau et al. - 1994
26 Basic paramodulation and decidable theories (context) - Nieuwenhuis - 1996
20 The Church-Rosser property for ground term-rewriting systems.. (context) - Oyamaguchi - 1987
19 Decidability of the confluence of finite ground term rewrite.. (context) - Dauchet, Heuillard et al. - 1990
6 Algorithms and reductions for rewriting problems - Verma, Rusinowitch et al. - 1998
5 Rewrite closure for ground and cancellative AC theories - Tiwari - 2001
4 a term rewriting technique for monotone order relations (context) - Levy, Agusti - 1993
3 the combination of equational and rewrite theories induced b.. (context) - Tiwari - 2002
3 The confluence of ground term rewrite systems is decidable i.. - Comon, Godoy et al. - 2001
3 the complexity of confluence for ground rewrite systems (context) - Hayrapetyan, Verma - 2001
1 Classes of Term Rewrite Systems with Polynomial Confluence P.. - Godoy, Nieuwenhuis et al. - 2002
1 Deciding confluence of certain term rewriting systems in pol.. - Tiwari - 2002
1 Rigid reachability: The non-symmetric form of rigid E-unific.. - Ganzinger, Jacquemard et al. - 2000
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.