Local Divisors in Semigroups and Formal Languages

• Applicants: Professor Dr. Volker Diekert; Dr. Manfred Kufleitner
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 233994807

The project aims at a variety of active research topics in theinterplay between formal languages, finite semigroups, automata, andlogic. We concentrate on six objectives, where newly developedtechniques are used to advance the theory. The motivation for thespecific project grew over the past two years.When the first applicant developed the mathematical tool of localdivisors for finite monoids around 2004 (thereby refining aconstruction of Meyberg from 1972), this was done for proving theexpressive completeness of local LTL over Mazurkiewicz traces. Overthe last few years, we realized that local divisors allow very generaland powerful induction methods in various other settings such as theKrohn-Rhodes decomposition theorem. This new proof scheme splits one``big'' induction step into many tiny ``baby'' steps. Last year, wereable to further refine our techniques for local divisors and apply thefindings to other open problems in classical language theory; and wewere immediately successful! This is documented e.g. in publicationsat CSR 2012 and ICALP 2012.Naturally, a mere proof scheme cannot provide solutions to any openproblems. In the same way, not every problem can be solved using localdivisors. We have chosen six objectives for which the local divisorapproach is highly promising. In addition, the project will benefit from theinternationally recognized expertise of the applicants, and thealready existing fruitful collaboration with world leading experts inthe research area.

• DFG Programme: Research Grants
• International Connection: Canada, France
• Participating Persons: Professor Dr. Markus Lohrey; Dr. Klaus Reinhardt; Professor Dr. Benjamin Steinberg; Professor Dr. Pascal Weil