Avraham Naumovich Trakhtman (auch Trahtman), (* 10. Februar 1944 in Kalinowo, Oblast Swerdlowsk) ist ein sowjetisch-israelischer Mathematiker.

Leben

Trahtman studierte an der Staatlichen Universität des Urals in Swerdlowsk mit dem Abschluss 1967. Er war danach an der Technischen Universität des Urals, wo er Dozent wurde und bis 1984 lehrte. 1973 wurde er bei Lew Schewrin an der Staatlichen Universität des Ural promoviert. Da er jüdisch war, war seine Karriere in der Sowjetunion in den 1970er Jahren behindert. Ende der 1980er Jahre war er auch in der russischen Demokratiebewegung aktiv. 1991 wurde er Assistenzprofessor an der Pädagogischen Hochschule in Swerdlowsk, verließ aber 1992 die Sowjetunion und ging nach Israel. Zunächst musste er sich dort mit Gelegenheitsarbeit durchschlagen, bevor er 1995 eine Stelle an der Bar-Ilan-Universität bekam.

1974 löste er ein Problem von T. Evans (1971) über Verbände von Halbgruppen-Varietäten.

1983 löste er das Problem der endlichen Basis für Halbgruppen von Alfred Tarski (1966).

2007 löste er das Straßenfärbungsproblem (Road coloring problem) von Roy Adler, L. W. Goodwyn und Benjamin Weiss (um 1970). Das Problem fragt nach der Existenz einer synchronisierten Färbung der Kanten in bestimmten gerichteten Graphen (aus jedem Knoten führen gleich viele Kanten heraus, die alle verschieden gefärbt werden). Die Färbung ermöglicht es einen Fahrplan (als Abfolge von Farben in einem Wort W) anzugeben, um von jedem beliebigen Knoten P des Graphen zu einem anderen Knoten Q des Graphen zu kommen, wobei W für alle P gleich ist. Das Problem hat seinen Ursprung in der Automatentheorie.

Er erzielte auch Fortschritte in einem weiteren offenen Problem der Theorie endlicher Automaten, dem Cerny-Problem (1964, Jan Cerny), einer oberen Grenze der Länge der kürzesten synchronisierenden Wörter.

Einzelnachweise

  1. ↑ Trahtman The road coloring problem, Israel J. Math., Band 172, 2009, S. 51–60.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.