Strukturkonstruktionen und modelltheoretische Spiele in speziellen Strukturklassen

特殊结构类别中的结构构造和模型理论博弈

• 批准号: 39236596
• 负责人: Professor Dr. Martin Otto
• 金额: --
• 依托单位: Fachbereich Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2007
• 资助国家: 德国
• 起止时间: 2006-12-31 至 2010-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/39236596?language=en
• 关键词: Strukturkonstruktionen; und; modelltheoretische; Spiele; speziellen

Dieses Forschungsvorhaben zur algorithmischen Modelltheorie zielt auf die Entwicklung von Methoden zur Analyse und Modellkonstruktion im Zusammenhang mit semantischen Invarianzbedingungen über speziellen, anwendungsrelevanten Strukturklassen. Im Vordergrund stehen algorithmische Probleme und Fragestellung der theoretischen Informatik, die mit modelltheoretisch-logischen Methoden bearbeitet werden. Modelltheoretische Spiele (Bisimulationsspiele, Ehrenfeucht-Fraissé-Spiele) gehören zum wichtigsten Instrumentarium für die Analyse von Struktureigenschaften und ihrer Definierbarkeit. Über geeigneten speziellen Strukturklassen sollen entsprechende Methoden anhand von Modularitäts- und Lokalitätskriterien verfeinert werden, mit dem Ziel, komplexere Strukturen anhand hierarchischer Zerlegungs- und Transformationsprozesse zu analysieren, sowie bestimmte algorithmische und modelltheoretische Fragestellungen über geeigneten Strukturklassen anhand entsprechend skalierbarer Kriterien für die Komplexität von Strukturen zu behandeln.

该研究的算法模型理论有助于分析和建模方法的发展，使其具有语义不变性和结构相关性。在解决理论信息学的算法问题和碎片问题时，采用模型理论逻辑方法可以得到韦尔登。Modelltheoretische Spiele（Bisimulationsspiele，Escherfeucht-Fraissé-Spiele）gehören zum wichtigsten Instrumentarium für die Analyse von Struktureigenschaften und ihrer Scherbarkeit.通过对结构的分析，我们可以使用模块化和局部化的方法，复杂的结构和层次化的Zerlegungs-和变换过程，从而可以通过算法和模型理论来分析结构，并为结构的复杂性提供一个标准。

项目成果

Decidability Results for the Boundedness Problem

有界问题的可判定性结果

• DOI: 10.2168/lmcs-10(3:2)2014
• 发表时间: 2011
• 期刊: Log. Methods Comput. Sci.
• 作者: Achim Blumensath;Martin Otto;Mark Weyer
• 通讯作者: Mark Weyer

Simple monadic theories and partition width

简单的一元理论和分区宽度

• DOI: 10.1002/malq.201010019
• 发表时间: 2011
• 期刊: Mathematical Logic Quarterly
• 影响因子: 0.3
• 作者: Achim Blumensath

On the Monadic Second-Order Transduction Hierarchy

关于一元二阶传导层次

• DOI: 10.2168/lmcs-6(2:2)2010
• 发表时间: 2010
• 期刊: Log. Methods Comput. Sci.
• 作者: A. Blumensath;B. Courcelle
• 通讯作者: B. Courcelle

Simple monadic theories and indiscernibles

简单的一元理论和难以辨别的

• DOI: 10.1002/malq.200910121
• 发表时间: 2011
• 期刊: Mathematical Logic Quarterly
• 影响因子: 0.3
• 作者: Achim Blumensath

Modal characterisation theorems over special classes of frames

特殊类别框架的模态表征定理

• DOI: 10.1016/j.apal.2009.04.002
• 发表时间: 2009
• 期刊: 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)
• 作者: A. Dawar;M. Otto
• 通讯作者: M. Otto