Problem #7 (Solved !)
Originator: Hubert Comon, Max Dauchet
Date: April 1991
Summary:
Is it possible to decide whether the set of ground normal forms
with respect to a given (finite) term-rewriting system
is a regular tree language?
Is it possible to decide whether the set of ground normal forms
with respect to a given (finite) term-rewriting system
is a regular tree language?
See [Gil91][Kuc91].
Remark
This has been answered in the affirmative
[VG92, KT93, KT95, HH93].
References
-
[Gil91]
-
R. Gilleron.
Decision problems for term rewriting systems and recognizable tree
languages.
In Christian Choffrut and Matthias Jantzen, editors, Eighth
Symposium on Theoretical Aspects of Computer Science, volume 480 of Lecture Notes in Computer
Science, Hamburg, Germany, February 1991.
Springer-Verlag.
- [HH93]
-
D. Hofbauer and M. Huber.
Computing linearizations using test sets.
In Michaël Rusinowitch and Rémy [MRR93], pages 287–301.
- [KT93]
-
Gregory Kucherov and Mohamed Tajine.
Decidability of regularity and related properties of ground normal
form languages.
In Michaël Rusinowitch and Rémy [MRR93], pages 272–286.
- [KT95]
-
Gregory Kucherov and Mohamed Tajine.
Decidability of regularity and related properties of ground normal
form languages.
Information
and Computation, 118(1):91–100, 1995.
- [Kuc91]
-
G. Kucherov.
On relationship between term rewriting systems and regular tree
languages.
In Ronald. V. Book, editor, 4th International Conference on
Rewriting Techniques and Applications, volume 488 of Lecture Notes in Computer
Science, Como, Italy, April 1991.
Springer-Verlag.
- [MRR93]
-
M. Michaël Rusinowitch and J. L. Rémy, editors.
Proceedings of the Third International Workshop on Conditional
Rewriting Systems, volume 656 of Lecture Notes in Computer
Science, Pont-à-Mousson, France, January 1993.
Springer-Verlag.
- [VG92]
-
S. Vágvölgyi and R. Gilleron.
For a rewrite system it is decidable whether the set of irreducible,
ground terms is decidable.
Bulletin of the European Association for Theoretical Computer
Science, 48:197–209, October 1992.