Automatische Strukturen und Ersetzungssysteme - Forschungsinformationssystem | Universität Kassel

ohne Drittmittelfinanzierung

Automatische Strukturen und Ersetzungssysteme

Details zum Projekt

Projektlaufzeit: 01/1999–12/2009

Webseite: http://www.theory.informatik.uni-kassel.de/projekte

Zusammenfassung

The concepts of an automatic structure and of a convergent rewriting system have a
common source in the attempts to identify and study algebraic objects in which the
algebraic operations are easy to compute. The objectives of this project are the
following:
- to investigate the relationships between various types of automatic structures and
various classes of rewriting systems,
- to develop theoretical and practical methods for constructing convergent rewriting
systems from various types of automatic structures,
- to develop theoretical and practical methods for computing automatic structures from certain types of rewriting systems,
- to investigate various decision problems for monoids given by an automatic structure of a certain form.

Publikationen

2001	Otto, F., Ruskuc, N., 2001. Confluent monadic string-rewriting systems and automatic structures. Journal of Automata, Languages and Combinatorics 6, 375–388.
2000	Otto, F., 2000. On Dehn functions of finitely presented monoids. Journal of Automata, Languages and Combinatorics 5, 405–419.
1999	Otto, F., 1999. On s-regular prefix-rewriting systems and automatic structures, in: T. Asano, H.I. (Hrsg.), Computing and Combinatorics, Proceedings of COCOON’99. Springer, Berlin, S. 422–431.