Prefix languages of Church-Rosser languages

Jens R. Woinowski

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


Abstract: Church-Rosser languages are mainly based on confluent length reducing string rewriting systems. In general, the prefix language of a Church-Rosser language may not be describable by such a system, too. In this paper it is shown that under certain conditions it is possible to give a construction for a system defining the prefix language and to prove its correctness. This construction also gives a completion of prefixes to full words in the original language, which is an interesting property for practical applications.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems