Local Divisors in Semigroups and Formal Languages

该项目致力于形式语言、有限半群、自动机和逻辑之间相互作用的各种活跃研究课题。我们专注于六个目标，在这些目标中，新发展的技术被用于推进理论。当第一个申请者在2004年左右开发了有限么半群的局部因子的数学工具时(从而改进了1972年Meyberg的一个构造)，这是为了证明Mazurkiewicz迹上局部LTL的表示完备性。在过去的几年里，我们意识到局部因子允许在各种其他环境中使用非常通用和强大的归纳方法，例如Krohn-Rhodes分解定理。这个新的证明方案将一个“大”的归纳步骤分成许多小的“小”步骤。去年，我们能够进一步改进我们的局部约数技术，并将这些发现应用于古典语言理论中的其他未决问题；我们立即成功了！例如，在CSR 2012和ICALP 2012的出版物中记录了这一点。自然，单纯的证明方案不能提供任何公开问题的解决方案。同样，并不是所有的问题都可以使用局部因子来解决。我们选择了六个目标，对这些目标来说，局部除数方法是非常有希望的。此外，该项目将受益于申请者的国际公认的专业知识，以及已经与该研究领域的世界领先专家进行的卓有成效的合作。

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.