(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