SOME UNDECIDABILITY RESULTS CONCERNING THE PROPERTY OF PRESERVING REGULARITY

A finite string-rewriting system R preserves regularity if and only if it preserves C-regularity, where Sigma is the alphabet containing exa ctly those letters that have occurrences in the rules of R. This prove s a conjecture of Gyenizse and Vagvolgyi (1997). In addition, some und ecidability results are presented that generalize results of Gilleron and Tison (1995) from term-rewriting systems to string-rewriting syste ms. It follows that the property of being regularity preserving is und ecidable for term-rewriting systems, thus answering another question o f Gyenizse and Vagvolgyi (1997). Finally, it is shown that it is undec idable in general whether a finite, length-reducing, and confluent str ing-rewriting system yields a regular set of normal forms for each reg ular language. (C) 1998-Elsevier Science B.V. All rights reserved.