一句话：回顾自动结构概念的起源与早期发展，追溯逻辑理论的自动机判定程序思想。
本文回顾自动结构（automatic structures）的历史渊源与发展。自动结构于二十年前的 LICS 2000 出现，但其思想可追溯至 1960 年代早期自动机理论中基于自动机的逻辑理论判定程序，尤其是 Büchi、Elgot、Trakhtenbrot 与 Rabin 的工作。自动结构这一显式概念最早由 Hodgson 在 1976 年的博士论文中提出，但当时未受到广泛关注；后来由 Khoussainov 与 Nerode 在 1995 年重新提出。文章梳理这些早期贡献与概念演变，说明自动结构如何从自动机方法应用于逻辑理论判定问题中逐步形成，并指出其正式登场与后续发展之间的历史联系。本文属于历史性综述，未提出新的技术定理或实验评估。
Automatic structures made their appearance at LICS twenty years ago, at LICS 2000. However, their roots are much older. The idea of automata based decision procedures for logical theories can be traced back to the early days of automata theory and to the work of Büchi, Elgot, Trakhtenbrot and Rabin in the 1960s. The explicit notion of automatic structures has first been proposed in 1976 in the (unfortunately largely unnoticed) PhD thesis of Hodgson, and later been reinvented by Khoussainov and Nerode in 1995.
DOI 原文 ·
@inproceedings{paperbot5481,
title = {Automatic Structures},
author = {Erich Grädel},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394734}
}