Talk:Rewriting

Broken sentence(s)

The following sentence from chapter 2.2, second paragraph, is completely illegible to me, but my knowledge is not sufficient to correct it:

Various properties, simpler than Church-Rosser, are equivalent to it; here we These
existence of these equivalent properties allows one to prove that a system is
Church-Rosser with less work.

Someone more knowledgable should correct it.
H.Marxen (talk) 14:47, 10 September 2009 (UTC)

I'm not entirely sure what the original intention was, but I've fixed it to something I understand. Is it better now? --Stephan Schulz (talk) 15:22, 10 September 2009 (UTC)

Thanks for the correction. I produced the gibberish when I summarized the longer Abstract rewriting system here by pruning some details. Pcap ping 16:31, 10 September 2009 (UTC)

More tutorial for the lay reader?

It looks like this article has a pretty steep curve: it has a very broad intro, then one example without much discussion, and then jumps into a very detailed abstract treatment. A bit more help could be offered for the uninitiated.

For example, the lead could offer some more background on what they're used for, and we could offer a few more examples. No concrete examples of string rewriting systems are given, yet these might be good intuitive starting points for some students.

I may take a crack at giving an informal description of SRSes to complement the formal one, and perhaps add an example or two. Anyone else want to chip in? Ezrakilty (talk) 04:03, 16 March 2011 (UTC)

Yes, yes! Please work on this article. For one thing, it needs more history. There may be some review articles that could be used to create an overview. At present it seems to have little content, but offers a series of formalizations of rewriting that have been created for different purposes. There is not much explanation of what those purposes might be. An improved article should have at least of bit of logic, algebra and computer science. It probably can't be very detailed but it should at least give the reader a feeling for the subject. EdJohnston (talk) 04:25, 16 March 2011 (UTC)

The book by Baader and Nipkow "Term Rewriting and All That", sounds like it would have material in support of a better introduction. EdJohnston (talk) 15:58, 20 April 2019 (UTC)

Applications

Anything on term rewriting's fields of application would be of interest. --78.49.180.20 (talk) 19:14, 31 March 2011 (UTC)

Citations

The citation of Davis et.al. in the Notes section has no counterpart in the Further Reading section, I think that maybe this is what's been originally intended (and that's why I didn't just added the citation under the FR section), so then the article needs another section, a References or Bibliography section or just add the full citation. Anyway here is the full document citation of Davis et.al.:

Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition, Academic Press, ISBN 0-12-206382-1. Anrusso (talk) 04:48, 23 July 2012 (UTC)

I continue with my two cents regarding the citations, maybe it would be better to rename the Further Reading section to References as suggested in the Wikipedia Manual of Style. Then add the citations of Davis and Church-Rosser. And modify the footer of Church-Rosser.anrc (talk) 15:31, 24 July 2012 (UTC)

As I see it, the Further Reading section, as it is (with comments about the documents), intends to be an annotated bibliography, so that's what I think it should be named.anrc (talk) 15:58, 24 July 2012 (UTC)

Non-deterministic

The introductory section states rewriting "can be non-deterministic". I think what it means is that, given only the original formula, rewriting is non-deterministic because their can be more than one ways of rewriting it.

But that doesn't mean an algorithm should be "non-deterministic" (there really isn't much point to make the result dependent on trivial factors such as time), just as stated in the paragraph: "Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications." This really is different from "non-deterministic algorithm".

However, the link to "deterministic computation" at the beginning of the first paragraph ("In mathematics, computer science, and logic, rewriting covers a wide range of (potentially non-deterministic) methods ...") and the one to "non-deterministic algorithm" at the beginning of the second ("Rewriting can be non-deterministic") might suggest (perhaps for some people, but that still makes it potentially confusing) that the algorithms for rewriting are "potentially non-deterministic".

The "non-deterministic" stuff and links to "non-deterministic algorithm" only appears in the introduction, not elaborated anywhere in the rest of the article. I think that can be a bit confusing for some... I'm seriously thinking about removing said links. Another thing is that cites no references at all. --Thomas J. S. Greenfield (talk) 12:30, 14 February 2014 (UTC) corrected line breaks 12:33, 14 February 2014 (UTC)

broken internal reference

Section "Termination" has a cross-reference to a page section "Termination and convergence" which no longer exists. It was broken in this edit by User:Mathnerd314159 -- 2A00:23C7:E482:AB01:3D2F:C6F6:E910:A9A2 (talk) 14:14, 17 December 2021 (UTC)

 Done The general ARS stuff was omitted, since it is found in Abstract rewriting system; I changed the sentence accordingly. Thanks for noticing, and looking up the relevant edit! - Jochen Burghardt (talk) 14:41, 17 December 2021 (UTC)