Projekt A9 - Die Sprache der grundreduzierbaren Terme (The language of ground reducible terms)

(until December 2003)

This project is an extension of Project A6. There we especially obtained interesting results for the language of ground reducible terms in case only linear terms are considered and the left hand sides of the underlying term rewriting system are linear as well (a term is called linear if no variable occurs twice in it):

Now our focus is on arbitrary (non-linear) term rewriting systems and we investigate the following questions:

Here we have to deal with more complex language classes: Whereas for left-linear term rewriting systems the language of reducible ground terms constitutes a regular tree language, for arbitrary term rewriting systems a language accepted by a constrained automaton is obtained, since we have to keep track of equalities between subterms. Consequently appropriate test sets also become rather complex, as already pointed out in our article on linearisation of term rewriting systems.

Members:

Dieter Hofbauer

Maria Huber

Technical Reports:

Hofbauer, D. and Huber, M.:
Test Sets for the Universal and Existential Closure of Regular Tree Languages.
Mathematische Schriften Kassel 7/99, Universität-GH Kassel (42 pages), October 1999. (To appear in Information and Computation.)

Publications:

Hofbauer, D. and Huber, M.:
Test Sets for the Universal and Existential Closure of Regular Tree Languages.
Proc. of the 10th International Conference on Rewriting Techniques and Applications, RTA 99, Trento (Italy), Lecture Notes in Computer Science 1631, pages 205-219, 1999.
Hofbauer, D. and Huber, M.:
Linearizing Term Rewriting Systems using Test Sets.
Journal of Symbolic Computation 17, pp. 91-129, 1994.