Projekt A1 - Eingeschränkte Konfluenz und spezielle Vervollständigung

(bis 12/93)

Endliche Ersetzungssysteme können oft nicht vervollständigt werden. Daher sind Systeme von Interesse, die nur auf einigen speziellen Kongruenzklassen konfluent sind. Dabei sind folgende Fragestellungen von Bedeutung:

Veröffentlichungen:

Otto, F. :
A survey on specialized completion procedures for constructing e-confluent string-rewriting systems.
In Ito, M. and Jürgensen, H., editors, Words, Languages and Combinatorics II, Proc., pages 301-316, Singapure. World Scientific 1994.
Madlener, K., Narendran, P., Otto, F., and Zhang, L. :
On weakly confluent monadic string-rewriting systems.
Theoretical Computer Science, 1993, 113:119-165.
Otto, F. :
The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems.
Mathematical Systems Theory, 1992, 25:241-251.
Otto, F. :
Completing a finite special string-rewriting system on the congruence class of the empty word.
Applicable Algebra in Engineering, Communication and Computing, 1992, 2:257-274.
Otto, F. :
Some recent results on string-rewriting systems that are confluent on some congruence class - a survey.
In Ito, M., editor, Words, Languages and Combinatorics, Proc., pages 385-409, Singapure. World Scientific 1992.
Otto, F. and Zhang, L. :
Decision problems for finite special string-rewriting systems that are confluent on some congruence class.
Acta Informatica, 1991, 28:477-510.
Otto, F. :
Some undecidability results for weakly confluent monadic string-rewriting systems.
In Mattson, H., Mora, T., and Rao, T., editors, Proceedings AAECC-9, Lecture Notes in Computer Science 539, pages 292-303. Springer-Verlag 1991, Berlin.
Madlener, K., Narendran, P., and Otto, F. :
A specialized completion procedure for monadic string-rewriting systems presenting groups.
In Albert, J., Monien, B., and Artalejo, M., editors, Proceedings 18th ICALP, Lecture Notes in Computer Science 510, pages 279-290. Springer-Verlag 1991, Berlin.
Otto, F. :
On deciding the confluence of a finite string-rewriting system on a given congruence class.
Journal Computer System Sciences, 1987, 35:285-310.
Otto, F. :
Some results about confluence on a given congruence class.
In Lescanne, P., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 256, pages 145-155. Springer-Verlag 1987, Berlin.