资源介绍
该部分收录 24 篇研究论文，涵盖马科夫斯基贡献过的多个研究领域，展现相关领域的前沿进展，部分核心论文主题如下：ε 演算与证明复杂度：马蒂亚斯・鲍茨（Matthias Baaz）与阿内拉・洛利奇（Anela Lolić）的《ε 演算提供更短的无切割证明》（Epsilon Calculus Provides Shorter Cut-Free Proofs），证明在 ε 格式的矢列演算中，无切割推导相较于一阶语言中通常的矢列演算无切割证明具有非初等加速，且相较于具有宽松本征变量条件的演算也存在非初等加速。模型论与几何公理：约翰・T・鲍德温（John T. Baldwin）的《马科夫斯基主题的变体》（Variations on a Theme of Makowsky），区分几何证明的公理研究与基于数学一般公理的几何研究，梳理 20 世纪合成几何的多种方法，明确 “度量”“正交”“迷向”“双曲” 等术语的含义，探讨仿射几何公理与相关域的稳定性分类之间的联系。自动结构与良序：列夫・D・贝克列米舍夫（Lev D. Beklemishev）与费奥多尔・N・帕霍莫夫（Fedor N. Pakhomov）的《自动结构与自然良序问题》（Automatic Structures and the Problem of Natural Well-orderings），探索利用自动结构及类似结构表示来解决证明论序数记法的自然性这一概念问题，分析自动结构、树自动结构、布奇（Büchi）自动结构、拉宾（Rabin）自动结构以及考卡尔（Caucal）层次结构在该问题中的作用与局限。图多项式计数复杂度：马库斯・布莱泽（Markus Bläser）与尼科・曼森（Nico Mansion）的《简单图覆盖多项式的计数复杂度》（On the Counting Complexity of the Cover Polynomial for Simple Graphs），证实钟（Chung）与格雷厄姆（Graham）的猜想，即覆盖多项式在限制于简单图（不允许平行边或环）时仍具有 #P 难性质，同时探讨其在平面简单图中的复杂度，以及对相关的下降多项式（Drop Polynomial）和几何覆盖多项式（Geometric Cover Polynomial）的影响。有界树宽多项式阈值函数：卡琳・丘巴良（Karine Chubarian）、约翰尼・乔伊斯（Johnny Joyce）与捷尔吉・图兰（György Turán）的《有界树宽多项式阈值函数：可解释性与复杂度方面》（Polynomial Threshold Functions of Bounded Tree-width: Some Explainability and Complexity Aspects），将多元多项式的树宽定义为其项对应的超图的树宽，探讨布尔变量的多项式阈值函数（Polynomial Threshold Functions, PTF），分析有界树宽多项式阈值函数在贝叶斯网络分类器可解释人工智能（XAI）中的应用，并给出正多项式阈值函数与一般多项式阈值函数表示能力的分离结果。等价关系与默认逻辑：阿里埃勒・科恩（Ariel Cohen）的《有些相等比其他相等更相等》（Some Equalities are More Equal than Others），探讨 “默认相同” 概念，即有时假设两个个体相同除非证明其不同是有益的，将查尔尼亚克（Charniak）提出的非正式、程序性想法，在马科夫斯基指导与后续合作下，形式化为两个具有重要理论与应用意义的严格关系，并应用于自然语言处理中的指代消解问题。根毛毛虫图的二分多项式：布鲁诺・库赛勒（Bruno Courcelle）与伊雷娜・杜兰德（Irène Durand）的《根毛毛虫图的二分多项式》（On the Bipartition Polynomials for Rooted Caterpillars），研究多德（Dod）、科特克（Kotek）、普林（Preen）与蒂特曼（Tittmann）定义的图二分多项式\(B(G, u, v, w)\)，提出等价的对称多项式\(Q(G, u, v, w)\)，证明根毛毛虫图的弱形式猜想（即\(Q_1(T)\)能确定根毛毛虫图的同构类），并展示可通过有限自动机计算该多项式。三、文集特色与学术价值跨学科融合：文集打破模型论、计算机科学、图论等学科的界限，展现各领域间的深度关联。例如，模型论方法在图多项式研究中的应用、自动结构理论与证明论序数记法的结合等，为跨学科研究提供了范例。纪念性与学术性兼具：既通过个人评述部分呈现马科夫斯基的学术生涯与人格魅力，让读者了解学者背后的故事；又以高质量的学术论文展现相关领域的前沿成果，为研究者提供重要的学术参考。理论与应用并重：既有对 ε 演算、模型论公理、自动结构等纯理论问题的深入探讨，也包含图多项式在计数复杂度、多项式阈值函数在可解释 AI 中的应用等具有实际意义的研究，兼顾理论深度与应用价值。传承与创新：文集以马科夫斯基的研究成果为核心线索，汇集了其同事、学生与合作者的研究，既是对其学术贡献的总结与致敬，也推动了相关领域的进一步创新发展，为后续研究提供了方向与思路。总之，《模型论、计算机科学与图多项式》不仅是对约翰・A・马科夫斯基学术生涯的重要纪念，更是模型论、计算机科学与图论领域研究者不可或缺的学术资源，对于推动相关学科的发展具有重要意义。