Algorithms and Reductions for Rewriting Problems (1997)  (Make Corrections)  (6 citations)
Rakesh M. Verma, Michael Rusinowitch, Denis Lugiez
Lecture Notes in Computer Science

  Home/Search   Context   Related

Links:   ACM   DBLP

 
View or download:
inria.fr/INRIA/publicat...RR3258.ps.gz
Cached:  PS.gz  PS  PDF  Image  Update  Help

From:  indiana.edu/pub/ucstri/index (more)
(Enter author homepages)

Rate this article: (best)
  Comment on this article  
(Enter summary)

Abstract: : In this paper we initiate a systematic study of polynomial-time reductions for some basic decision problems of rewrite systems. We then give a polynomial-time algorithm for Unique-normal-form property of ground systems for the first time. Next we prove undecidability of these problems for string rewriting using our reductions. Finally, we prove partial decidability results for Confluence of commutative semi-thue systems. The Confluence and Unique-normal-form property are also shown... (Update)

Context of citations to this paper:   More

.... are only decidable for trace rewriting systems 1 over free commutative monoids, i.e. vector replacement sytems, see [HL78] BO84] [VRL98] 1 . For the con uence problem this situation changes if only terminating systems are considered. It is a classical result that for the...

.... Preprint submitted to Elsevier Science 13 March 2003 Reachability, joinability and con uence are undecidable for linear (non shallow) TRS [7], but it was not known whether we can relax the linearity assumptions on variables of the systems of [5,6] keeping these properties...

Cited by:   More
On the Confluence of Linear Shallow - Term Rewrite Systems (2003)   (Correct)
Con uence Problems for Trace Rewriting Systems - Markus Lohrey Universit (2001)   (Correct)
Relative Undecidability in Term Rewriting Part 2: The.. - Geser, Middeldorp   (Correct)

Similar documents (at the sentence level):
48.1%:   Algorithms and Reductions for Rewriting Problems - Verma, Rusinowitch, Lugiez (1998)   (Correct)
32.1%:   Fundamenta Informaticae XX (2001) 1--20 1 IOS Press - Algorithms And Reductions   (Correct)

Active bibliography (related documents):   More   All
0.5:   Decidability Issues for Petri Nets - Esparza, Nielsen (1994)   (Correct)
0.1:   Departamento De Sistemas Inform - Aticos Computaci On (2004)   (Correct)
0.1:   Reachability and Confluence Are Undecidable for Flat Term.. - Jacquemard (2003)   (Correct)

Similar documents based on text:   More   All
0.2:   Model Checking Using Tabled Rewriting - For Ijcar Doctoral   (Correct)
0.2:   On the Reachability Problem in Cryptographic Protocols - Amadio, Lugiez (2000)   (Correct)
0.2:   The Regular Viewpoint on PA-Processes - Lugiez, Schnoebelen (1998)   (Correct)

Related documents from co-citation:   More   All
3:   algorithm for testing the Church-Rosser property of Thue systems (context) - Kapur, Krishnamoorthy et al. - 1985
3:   Finite complete rewriting systems and the complexity of the word problem (context) - Bauer, Otto - 1984
3:   Number 454 in Lecture Notes in Computer Science (context) - Diekert, Traces - 1990

BibTeX entry:   (Update)

R. M. Verma, M. Rusinowitch, and D. Lugiez. Algorithms and reductions for rewriting problems. In Proceedings of the 9th Conference on Rewriting Techniques and Applications (RTA-98), Tsukuba (Japan), number 1379 in Lecture Notes in Computer Science, pages 166-180. Springer, 1998. http://citeseer.ist.psu.edu/article/verma97algorithms.html   More

@article{ verma98algorithms,
    author = "Rakesh M. Verma and Michael Rusinowitch and Denis Lugiez",
    title = "Algorithms and Reductions for Rewriting Problems",
    journal = "Lecture Notes in Computer Science",
    volume = "1379",
    pages = "166--??",
    year = "1998",
    url = "citeseer.ist.psu.edu/article/verma97algorithms.html" }
Citations (may not include all citations):
759   Rewrite systems - Dershowitz, Jouannaud - 1990  ACM   DBLP
76   Variations on the common subexpression problem (context) - Downey, Sethi et al. - 1980  ACM   DBLP
76   The complexity of the word problem for commutative semigroup.. (context) - Mayr, Meyer - 1982
65   Complexity of finitely presented algebras (context) - Kozen - 1977  ACM   DBLP
22   the reachability problem for 5-dimensional vector addition s.. (context) - Hopcroft, Pansiot - 1979
19   Decidability of the confluence of finite ground term rewrite.. (context) - Dauchet, Heuillard et al. - 1990
19   The Church-Rosser property for ground term rewriting systems.. (context) - Oyamaguchi - 1987
15   Finite complete rewriting systems and the complexity of the .. (context) - Bauer, Otto - 1984  DBLP
7   The reachability and joinability problems for right-ground t.. (context) - Oyamaguchi - 1990
6   The reachability problem for ground TRS and some extensions (context) - Deruyver, Gilleron - 1989  ACM   DBLP
3   String Rewriting Systems Springer-Verlag (context) - Book, Otto - 1992
3   Rewrite systems (context) - Klop - 1992  ACM   DBLP
2   Laboratoire de Recherche en Informatique (context) - Escrig, Johnen et al. - 1989

Documents on the same site (http://www.cs.indiana.edu/pub/ucstri/index):   More
Environment Modelling for Mobile Robots: Neural Learning for.. - van Dam (1998)   (Correct)
Broadcasting in Butterfly and DeBruijn Networks - Klasing, Monien, Peine, Stöhr (1992)   (Correct)
ILFA - A Project in Experimental Logic Computation - Dunker, Flögel, Büning..   (Correct)

Online articles have much greater impact   More about CiteSeer.IST   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST - Copyright Penn State and NEC