Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeucht-Fraisse (EF) games in two ways: first, MS games are played on two sets of structures, while EF games are played on a pair of structures; second, in MS games, Duplicator can make any number of copies of structures. In the first part of this paper, we perform a finer analysis of MS games and develop a closer comparison of MS games with EF games. In particular, we point out that the use of sets of structures is of the essence and that when MS games are played on pairs of structures, they capture Boolean combinations of first-order sentences with a fixed number of quantifiers. After this, we focus on another important difference between MS games and EF games, namely, the necessity for Spoiler to play on top of a previous move in order to win some MS games. Via an analysis of the types realized during MS games, we delineate the expressive power of the variant of MS games in which Spoiler never plays on top of a previous move. In the second part we focus on simultaneously capturing number of quantifiers and number of variables in first-order logic. We show that natural variants of the MS game do not achieve this. We then introduce a new game, the quantifier-variable tree game, and show that it simultaneously captures the number of quantifiers and number of variables.


翻译:多结构游戏( MS) 是组合式游戏, 捕捉第一级句子的量化数。 在定义的表面上, MS 游戏与 Ehrenfeucht- Fraisse (EF) 游戏有两种不同方式: 首先, MS 游戏在两套结构上玩, 而 EF 游戏在一对结构上玩; 其次, 在 MS 游戏中, Duplicator 可以制作任何数量的架构副本。 在本文件的第一部分, 我们对 MS 游戏进行更精细的分析, 并对 MS 游戏与 EF 游戏进行更接近的比较。 特别是, 我们指出 MS 游戏的套游戏的使用是精髓的, 当 MS 游戏在两对结构的组合上玩的时候, 它们捕捉到一对一的组合, 而 EF 游戏是在两组结构上玩的组合; 之后, 我们集中关注 MS 游戏和 EF 游戏之间的另一个重要区别, 即 Spoilter 需要玩上之前的游戏, 来赢得一些 MS 游戏。 通过对在 MS MS 游戏中实现的种类的分析, 我们在前一个游戏的变式中, 在前一个变式中, 在前一个变式中, 显示前一个变式中, 我们在前一个变式中, 显示前的变式的变式中, 在前一个变式中, 我们的变式中, 在前一个变式中, 显示一个变式中, 我们的变式中, 我们的变式的变式的变式中, 显示一个变式中, 在前的变式中, 显示一个变式的变式中, 在前的变式中, 在前的变式中, 我们的变式中, 显示一个变式中, 在前一个变式中, 在前的变式中, 在前的变式中, 在前的变式中, 在前的变式中, 我们的变式的变式中, 我们的变式中, 我们的变式中, 我们的变式的变式中, 在前的变式中, 。

0
下载
关闭预览

相关内容

多媒体系统(MS)期刊详细介绍了多媒体计算,通信,存储和应用的各个方面的创新研究思想,新兴技术,最新方法和工具。它包含理论,实验和调查文章。多媒体系统的覆盖范围包括:在计算机系统中集成数字视频和音频功能;多媒体信息编码和数据交换格式;数字多媒体的操作系统机制;数字视频和音频网络与通信;存储模型和结构;用于支持多媒体应用程序的方法、范式、工具和软件体系结构;多媒体应用程序和应用程序接口,以及多媒体终端系统架构。 官网地址:http://dblp.uni-trier.de/db/journals/mms/
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
79+阅读 · 2022年7月16日
Arxiv
92+阅读 · 2021年5月17日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员