Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Lokale Divisoren in Halbgruppen und Formalen Sprachen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2013 bis 2017
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 233994807
 
Erstellungsjahr 2017

Zusammenfassung der Projektergebnisse

A local divisor in the theory of finite monoids combines two concepts: local algebras were introduced by Karl Meyberg in the mid 1970s in associative algebra and, in semigroup theory, divisors generalize the notion of a sub-semigroup. Given a monoid M and an element c, the local divisor at c is the set of elements x which can be written as both x= cy and x=zc. This subset of M can be equipped with the operation * such that xc*cy = xcy. Indeed, it is a divisor of M and its neutral element is c. If c is idempotent, then the local divisor is a sub-semigroup called the local monoid which, by definition, is cMc. Local monoids appear in classical semigroup theory. However, the crucial observation is that the construction of a local divisor goes far beyond the classical approach. It works for every c in M. The local divisor is always a monoid and smaller than M if c is not a unit and M is finite. This makes the construction useful for inductive proofs. The aim of the project was to show that the local divisor technique is able to simplify various difficult proofs in finite semigroup theory and, more importantly, leads to new results. The outcome of the project outmatched our expectations by far. For this short summary we content ourselves to highlight three specific achievements. 1. In the textbook "Discrete Algebraic Methods" we included a chapter on local divisors. We showed that difficult standard theorems in formal language theory can be made much more transparent and simpler when using an induction based on local divisors. The examples include Schützenberger’s famous theorem that aperiodic languages are star-free, the Krohn-Rhodes decomposition theorem as well as a fundamental result about Green's relation. Thus, local divisors can be successfully incorporated in undergraduate education. 2. In a conference abstract we showed that every regular language is recognized by a finite Church-Rosser semi-Thue system. This contribution got the best paper award in Track B. It solved a problem which was open for more than 25 years. The work on this long and technical paper was done within the project. 3. In 2017 we were able to complete an unfinished research program lanced by Schützenberger more than 40 years ago. In 1975, Schützenberger found another but less prominent characterization for the class of star-free languages: it is also the class of languages which can be defined inductively by finite languages and closure under finite union, concatenation, and the Kleene-star restricted to prefix codes of bounded synchronization delay. Follow-up publications showed that he aimed at a much more general result. The statement he had in mind was clear, but he could show only one direction of it. His attempts were based on the work of Krohn and Rhodes. Using local divisors, we were able to show the missing “other direction” of his result. The results underline that a simple change in the proof methodology (here: from Krohn-Rhodes decompositions to local divisors) may lead to far reaching results.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung