Projekt A12 - Konvergente Darstellungen algebraischer Strukturen

(bis 12/2002)

Hat eine algebraische Stuktur eine endliche konvergente Darstellung, dann läßt sich das Wortproblem mittels des sogenannten "Normalformenalgorithmus" lösen. Also ist die Lösbarkeit des Wortproblems eine notwendige Voraussetzung dafür, daß überhaupt eine endliche konvergente Darstellung existieren kann. Es war lange Zeit offen, ob diese Bedingung auch bereits hinreichend ist. Inzwischen ist erkannt worden, daß dies nicht der Fall ist, und es sind weitere notwendige Bedingungen entdeckt worden, so die homologische Endlichkeitsbedingung FP3 und die kombinatorische Bedingung des "endlichen Ableitungstyps". Sind diese Bedingungen nun hinreichend für die Existenz endlicher konvergenter Darstellungen, und in welcher Beziehung stehen diese verschiedenen notwendigen Bedingungen zueinander?

Desweiteren interessiert man sich dafür, welche im allgemeinen unentscheidbaren Probleme lösbar werden, wenn man sie auf gewisse Klassen von konvergenten Darstellungen einschränkt.

Mitarbeiter:

Robert Cremanns
(jetzt: SAP, Deutschland)

Masashi Katsura
(Department of Mathematics, Kyoto-Sangyo University, Kyoto, Japan)

Yuji Kobayashi
(Department of Information Science, Toho University, Funabashi, Japan)

Klaus Madlener
(Fachbereich Informatik, Universität Kaiserslautern)

Paliath Narendran
(Department of Computer Science, State University of New York, Albany, NY, USA)

Andrea Sattler-Klein
(Fachbereich Informatik, Universität Kaiserslautern)

Interne Berichte:

Otto, F.:
Some results on Green's relations for monoids presented by monadic string-rewriting systems.
Mathematische Schriften Kassel 9/01, Universität-GH Kassel, Juli 2001.
Katsura, M., Kobayashi, Y., Otto, F.:
Undecidable properties of monoids with word problem solvable in linear time - II. Cross-sections and homological and homotopical finiteness conditions.
Mathematische Schriften Kassel 2/01, Universität-GH Kassel, Januar 2001.
Otto, F.:
On the connections between rewriting and formal language theory.
Mathematische Schriften Kassel 5/99, Universität-GH Kassel, März 1999.
Invited talk presented at
RTA'99.
Otto, F. :
A survey on the computational power of some classes of finite monoid-presentations.
Mathematische Schriften Kassel 12/98, Universität-GH Kassel, September 1998.
Cremanns, R. and Otto, F. :
FP_\infty is undecidable for finitely presented monoids with word problems decidable in polynomial time.
Mathematische Schriften Kassel 11/98, Universität-GH Kassel, September 1998.
Otto, F. :
Uniform decision problems for certain restricted classes of finite monoid-presentations - A survey on recent undecidability results.
Mathematische Schriften Kassel 11/97, Universität-GH Kassel, October 1997.
published in Semigroups and Applications in revised form.
Otto, F. :
On properties of monoids that are modular for free products and for certain free products with amalgamated submonoids.
Mathematische Schriften Kassel 6/97, Universität-GH Kassel, June 1997.
published in revised form.
Otto, F. :
Preserving regularity and related properties of string-rewriting systems.
Mathematische Schriften Kassel 6/96, Universität-GH Kassel.
published in Theoretical Computer Science in revised form.
Katsura, M., Kobayashi, Y., and Otto, F. :
Infinite convergent string-rewriting systems and cross-sections for monoids
Mathematische Schriften Kassel 3/96, Universität-GH Kassel.
published in Journal of Symbolic Computation in revised form.

Veröffentlichungen:

Otto, F.:
Some results on Green's relations for monoids presented by monadic string-rewriting systems
Semigroup Forum, 2002, 65:374-385.
Cremanns, R., Otto, F.:
A completion procedure for finitely presented groups that is based on word cycles
Journal of Automated Reasoning, 2002, 28:235-256.
Katsura, M., Kobayashi, Y., Otto, F.:
Undecidability results for monoids with linear-time decidable word problem.
In Lee, D.T. and Teng, Sh., editors, Algorithms and Computation, Proceedings ISAAC 2000, pages 278-289, Lecture Notes in Computer Science 1969, Springer-Verlag, Berlin, 2000.
Otto, F. :
A survey on the computational power of some classes of finite monoid presentations.
In Birget, J.C. and Margolis, S. and Meakin, J. and Sapir, M., editors, Algorithmic Problems in Groups and Semigroups, pages 171-194, Trends in Mathematics, Birkhäuser, Boston, 2000.
Otto, F.:
Modular properties of monoids and string-rewriting systems.
In Nehaniv, Ch. and Ito, M., editors, Algebraic Engineering, Proceedings, pages 538-554. World Scientific, Singapure, 1999.
Otto, F.:
On the connections between rewriting and formal language theory.
In Narendran, P. and Rusinowitch, M., editors, Rewriting Techniques and Applications, Proceedings RTA'99, pages 332-355, Lecture Notes in Computer Science 1631, Springer-Verlag, Berlin, 1999.
Otto, F.:
Uniform decision problems for certain restricted classes of finite monoid presentations - a survey on recent undecidability results.
In Howie, J.M. and Ruskuc, N., editors, Semigroups and Applications, Proceedings, pages 152-170. World Scientific, Singapure, 1998.
Otto, F.:
Some undecidability results concerning the property of preserving regularity
Theoretical Computer Science, 1998, 207:43--72.
Otto, F. and Sattler-Klein, A. :
FDT is undecidable for finitely presented monoids with solvable word problems.
In Chlebus, B. and Czaja, L., editors, Fundamentals of Computation Theory, Proceedings FCT'97 , Lecture Notes in Computer Science 1279, pages 388-399. Springer-Verlag 1997, Berlin.
Madlener, K. and Otto, F. :
Some undecidability results for finitely generated Thue congruences on a two-letter alphabet.
Fundamenta Informaticae, 1997, 30:31-44.
Otto, F. :
On the property of preserving regularity for string-rewriting systems.
In Comon, H., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 1232, pages 83-97. Springer-Verlag 1997, Berlin.
Otto, F., Katsura, M., and Kobayashi, Y. :
Cross-sections for finitely presented monoids with decidable word problems.
In Comon, H., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 1232, pages 53-67. Springer-Verlag 1997, Berlin.
Kobayashi, Y. and Otto, F. :
Properties of monoids that are presented by finite convergent string-rewriting systems - a survey.
In Du, D. and Ko, K., editors, Advances in Algorithms, Languages and Complexity, pages 226-266, Dordrecht. Kluwer Academic Publ. 1997
Cremanns, R. and Otto, F. :
For groups the property of having finite derivation type is equivalent to the homological finiteness condition FP3.
Journal of Symbolic Computation , 1996, 22:155-177.
Otto, F. :
Some decision problems related to the regularity of monoids.
In Almeida, J., Gomes, G., and Silva, P., editors, Semigroups, Automata and Languages, pages 211-224, Singapure. World Scientific. 1996
Squier, C., Otto, F., and Kobayashi, Y. :
A finiteness condition for rewriting systems.
Theoretical Computer Science, 1994, 131:271-294.
Madlener, K. and Otto, F. :
Some undecidability results for finitely generated Thue congruences on a two-letter alphabet.
In Schock, E., editor, Beiträge zur Angewandten Analysis und Informatik, Helmut Brakhage zu Ehren, pages 248-261, Aachen. Verlag Shaker 1994.
Cremanns, R. and Otto, F. :
Finite derivation type implies the homological finiteness condition FP3.
Journal of Symbolic Computation, 1994, 18:91-112.
Madlener, K., Sattler-Klein, A., and Otto, F. :
On the problem of generating small convergent systems.
Journal of Symbolic Computation, 1993, 16:167-187.
Cohen, D., Madlener, K., and Otto, F. :
Separating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups.
Mathematical Logic Quaterly, 1993, 39:143-157.
Madlener, K., Otto, F., and Sattler-Klein, A. :
Generating small convergent systems can be extremely hard.
In Ibaraki, T., Inagaki, Y., Iwama, K., Nishizeki, T., and Yamashita, M., editors, Proceedings ISAAC'92, Lecture Notes in Computer Science 650, pages 299-308. Springer-Verlag 1992, Berlin.
Otto, F. :
When is an extension of a specification consistent? Decidable and undecidable cases.
Journal of Symbolic Computation, 1991, 12:255-273.
Narendran, P., O'Dúnlaing, C., and Otto, F. :
It is undecidable whether a finite special string-rewriting system presents a group.
Discrete Mathematics, 1991, 98:153-159.
Madlener, K. and Otto, F. :
Decidable sentences for context-free groups.
In Choffrut, C. and Jantzen, M., editors, Proceedings STACS'91, Lecture Notes in Computer Science 480, pages 160-171. Springer-Verlag 1991, Berlin.
Narendran, P. and Otto, F. :
It is decidable in polynomial time whether a monoid presented by a finite weight-reducing and confluent Thue system is torsion-free.
In Huguet, L. and Poli, P., editors, Proceedings AAECC-5, Lecture Notes in Computer Science 356, pages 341-349. Springer-Verlag 1989, Berlin.
Narendran, P. and Otto, F. :
Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems.
Theoretical Computer Science, 1989, 68:319-332.
Madlener, K. and Otto, F. :
About the descriptive power of certain classes of finite string-rewriting systems.
Theoretical Computer Science, 1989, 67:143-172.
Otto, F. :
An example of a one-relator group that is not a one-relation monoid.
Discrete Mathematics, 1988, 69:101-103.
Narendran, P. and Otto, F. :
Elements of finite order for finite weight-reducing and confluent Thue systems.
Acta Informatica, 1988, 25:573-591.
Madlener, K. and Otto, F. :
On groups having finite monadic Church-Rosser presentations.
In Jürgensen, H., Lallement, G., and Weinert, H., editors, Semigroups, Theory and Applications, Lecture Notes in Mathematics 1320, pages 218-234. Springer-Verlag 1988, Berlin.
Madlener, K. and Otto, F. :
Commutativity in groups presented by finite Church-Rosser Thue systems.
RAIRO Informatique Théorique et Applications, 1988, 22:93-111.
Madlener, K. and Otto, F. :
Pseudo-natural algorithms for finitely generated presentations of monoids and groups.
Journal of Symbolic Computation, 1988, 5:339-358.
Squier, C. and Otto, F. :
The word problem for finitely presented monoids and finite canonical rewriting systems.
In Lescanne, P., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 256, pages 74-82. Springer-Verlag 1987, Berlin.
Otto, F. :
Deciding algebraic properties of finitely presented monoids.
In Benninghofen, B., Kemmerich, S., and Richter, M., editors, Systems of Reductions, Lecture Notes in Computer Science 277, pages 218-255. Springer-Verlag 1987, Berlin.
Madlener, K. and Otto, F. :
Groups presented by certain classes of finite length-reducing string-rewriting systems.
In Lescanne, P., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 256, pages 133-144. Springer-Verlag 1987, Berlin.
Madlener, K. and Otto, F. :
Using string-rewriting for solving the word problem for finitely presented groups.
Information Processing Letters, 1987, 24:281-284.
Otto, F. :
Church-Rosser Thue systems that present free monoids.
SIAM Journal on Computing, 1986, 15:786-792.
Otto, F. :
On two problems related to cancellativity.
Semigroup Forum, 1986, 33:331-356.
Otto, F. :
On deciding whether a monoid is a free monoid or is a group.
Acta Informatica, 1986, 23:99-110.
Narendran, P. and Otto, F. :
The problems of cyclic equality and conjugacy for finite complete rewriting systems.
Theoretical Computer Science, 1986, 47:27-38.
Avenhaus, J., Madlener, K., and Otto, F. :
Groups presented by finite two-monadic Church-Rosser Thue systems.
Transactions American Mathematical Society, 1986, 297:427-443.
Otto, F. and Wrathall, C. :
A note on Thue systems with a single defining relation.
Mathematical Systems Theory, 1985, 18:135-143.
Otto, F. :
Elements of finite order for finite monadic Church-Rosser Thue systems.
Transactions American Mathematical Society, 1985, 291:629-637.
Otto, F. :
Deciding algebraic properties of monoids presented by finite Church-Rosser Thue systems.
In Jouannaud, J., editor, Rewriting Techniques and Applications, Lecture Notes in Computer Science 202, pages 95-106. Springer-Verlag 1985, Berlin.
Narendran, P. and Otto, F. :
Complexity results on the conjugacy problem for monoids.
Theoretical Computer Science, 1985, 35:227-243.
Madlener, K. and Otto, F. :
Derivation-bounded groups.
Revista Colombiana de Mathematicas, 1985, 19:131-161.
Madlener, K. and Otto, F. :
Pseudo-natural algorithms for the word problem for finitely presented monoids and groups.
Journal of Symbolic Computation, 1985, 1:383-418.
Book, R. and Otto, F. :
Cancellation rules and extended word problems.
Information Processing Letters, 1985, 20:5-11.
Otto, F. :
Some undecidability results for non-monadic Church-Rosser Thue systems.
Theoretical Computer Science, 1984, 33:261-278.
Otto, F. :
Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group.
Theoretical Computer Science, 1984, 32:249-260.
Otto, F. :
Conjugacy in monoids with a special Church-Rosser presentation is decidable.
Semigroup Forum, 1984, 29:223-240.
Narendran, P., Otto, F., and Winklmann, K. :
The uniform conjugacy problem for finite Church-Rosser Thue systems is NP-complete.
Information Control, 1984, 63:58-66.
Bauer, G. and Otto, F. :
Finite complete rewriting systems and the complexity of the word problem.
Acta Informatica, 1984, 21:521-540.