From Automatic Structures to Borel Structures
From Automatic Structures to Borel Structures
复制标题
从自动结构到 Borel 结构
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Nies
中科院分区：
文献类型：
--
作者：
G. Hjorth;B. Khoussainov;A. Montalbán;A. Nies
我们研究 Buchi 和 Rabin 自动结构类。对于 Buchi（Rabin）自动结构，它们的域由无限字符串（树）组成，并且基本关系（包括等式关系）和运算图由 Buchi（Rabin）自动机识别。如果不同的无限串（树）表示结构的不同元素，则 Buchi（Rabin）自动结构是单射的。本文的第一部分致力于理解模型理论中著名的 Lowenheim-Skolem 定理的自动机理论内容。我们为 Rabin 和 Buchi 自动结构提供 Lowenheim-Skolem 定理的自动机理论版本。在第二部分中，我们解决自动结构理论中的以下两个著名的开放问题：是否每个Buchi自动结构都有一个单射Buchi表示？每个拉宾自动结构都有一个单射拉宾表示吗？我们提供了 Buchi 结构的示例，但没有单射 Buchi 和 Rabin 演示。为了回答这些问题，我们引入 Borel 结构并使用 Borel 集和同构的一些基本属性。最后，在论文的最后一部分我们研究了Buchi自动结构的同构问题。
We study the classes of Buchi and Rabin automatic structures. For Buchi (Rabin) automatic structures their domains consist of infinite strings (trees), and the basic relations, including the equality relation, and graphs of operations are recognized by Buchi (Rabin) automata. A Buchi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata- theoretic content of the well-known Lowenheim-Skolem theorem in model theory. We provide automata-theoretic versions of Lowenheim-Skolem theorem for Rabin and Buchi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every Buchi automatic structure have an injective Buchi presentation? Does every Rabin automatic structure have an injective Rabin presentation? We provide examples of Buchi structures without injective Buchi and Rabin presentations. To answer these questions we introduce Borel structures and use some of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for Buchi automatic structures.