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.