Lokale Divisoren in Halbgruppen und Formalen Sprachen
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)
- Star-free languages and local divisors. In DCFS 2014, Proceedings, volume 8614 of Lecture Notes in Computer Science, pages 23–28. Springer, 2014
M. Kufleitner
(Siehe online unter https://doi.org/10.1007/978-3-319-09704-6_3) - A survey on the local divisor technique. Theoretical Computer Science, 610:13–23, 2015
V. Diekert und M. Kufleitner
(Siehe online unter https://doi.org/10.1016/j.tcs.2015.07.008) - Regular languages are Church-Rosser congruential. J. ACM, 62:39:1–39:20, Nov. 2015
V. Diekert, M. Kufleitner, K. Reinhardt, and T. Walter
(Siehe online unter https://doi.org/10.1145/2808227) - Abschnitte 7.5 und 7.6 in Discrete Algebraic Methods. Arithmetic, Cryptography, Automata and Groups. Walter de Gruyter, 2016
V. Diekert, M. Kufleitner, G. Rosenberger, und U. Hertrampf
(Siehe online unter https://doi.org/10.1515/9783110413335-008) - Characterizing classes of regular languages using prefix codes of bounded synchronization delay. In I. Chatzigiannakis et al., editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), pages 129:1–129:13, 2016
V. Diekert und T. Walter
(Siehe online unter https://doi.org/10.1142/S021819671750028X) - Characterizing classes of regular languages using prefix codes of bounded synchronization delay. International Journal of Algebra and Computation, 27:561–590, 2017
V. Diekert und T. Walter
(Siehe online unter https://doi.org/10.1142/S021819671750028X) - Church-Rosser systems, codes with bounded synchronization delay and local Rees extensions. In WORDS 2017, Proceedings, volume 10432 of LNCS, pages 6–16. Springer, 2017
V. Diekert und L. Fleischer
(Siehe online unter https://doi.org/10.1007/978-3-319-66396-8_2) - Green’s relations in finite transformation semigroups. In CSR 2017, Proceedings, volume 10304 of LNCS, pages 112–125. Springer, 2017
L. Fleischer and M. Kufleitner
(Siehe online unter https://doi.org/10.1007/978-3-319-58747-9_12) - Parikh-reducing Church–Rosser representations for some classes of regular languages. Theoretical Computer Science, 702:34 – 47, 2017
T. Walter
(Siehe online unter https://doi.org/10.1016/j.tcs.2017.08.009)
