We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The subclasses of rational relations that we consider are formed by the deterministic rational relations, synchronous (also called automatic or regular) relations, and recognizable relations. For almost all versions of the membership problem, determining the precise complexity or even decidability has remained an open problem for almost two decades. In this paper, we provide improved complexity and new decidability results. (i) Testing whether a synchronous relation over infinite words is recognizable is NL-complete (PSPACE-complete) if the relation is given by a deterministic (nondeterministic) omega-automaton. This fully settles the complexity of this recognizability problem, matching the complexity of the same problem over finite words. (ii) Testing whether a deterministic rational binary relation is recognizable is decidable in polynomial time, which improves a previously known double exponential time upper bound. For relations of higher arity, we present a randomized exponential time algorithm. (iii) We provide the first algorithm to decide whether a deterministic rational relation is synchronous. For binary relations the algorithm even runs in polynomial time.


翻译:我们重新审视有限和无限字上的有理关系子类的成员问题:给定类别C_2中的一个关系R,R是否属于较小的类别C_1?我们考虑的有理关系子类是由确定有限自动机,同步(也称为自动或常规)关系和可识别关系形成的。对于几乎所有成员问题的版本,几乎已经有近二十年时间,确定复杂性甚至可决定性仍然是一个悬而未决的问题。在本文中,我们提供了改进的复杂度和新的可决定性结果。 (i) 对于用确定的(非确定的)无限自动机给出的同步关系,测试它是否可识别是NL完全的(PSPACE完全的)。这个收敛性问题的复杂度已经得到充分解决,与相同问题的有限字版本的复杂度相匹配。 (ii) 测试确定的有理二元关系是否可识别是可在多项式时间内决定的,这正在改善先前已知的双重指数时间上限。对于更高阶的关系,我们提供了一个随机指数时间算法。 (iii) 我们提供了第一个算法来决定一个确定的有理关系是否同步。对于二元关系,该算法甚至可以在多项式时间内运行。

0
下载
关闭预览

相关内容

【ICML2022】通过能量最小化学习迭代推理
专知会员服务
25+阅读 · 2022年7月3日
20年单类别(One-Class)分类全面综述论文,从2001到2020
专知会员服务
21+阅读 · 2021年1月12日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
读书报告 | Deep Learning for Extreme Multi-label Text Classification
科技创新与创业
48+阅读 · 2018年1月10日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年6月7日
Arxiv
0+阅读 · 2023年6月6日
VIP会员
相关VIP内容
【ICML2022】通过能量最小化学习迭代推理
专知会员服务
25+阅读 · 2022年7月3日
20年单类别(One-Class)分类全面综述论文,从2001到2020
专知会员服务
21+阅读 · 2021年1月12日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
读书报告 | Deep Learning for Extreme Multi-label Text Classification
科技创新与创业
48+阅读 · 2018年1月10日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员