The Diagonal Problem for Higher-Order Recursion Schemes is Decidable*

机译：高阶递归方案的对角线问题是可确定的*

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We show decidability of the diagonal problem for schemes. This result has several interesting consequences. In particular, it gives an algorithm that computes the downward closure of languages of words recognized by schemes. In turn, this has immediate application to separability problems and reachability analysis of concurrent systems.

机译：非确定性递归方案可识别有限树的语言。这个非常有表现力的模型可以模拟具有崩溃的高阶下推自动机。我们显示了方案对角线问题的可判定性。这个结果有几个有趣的结果。特别地，它给出了一种算法，该算法计算方案识别的单词的语言的向下闭合。反过来，这可以立即应用于并发系统的可分离性问题和可达性分析。

著录项

来源
《Annual ACM/IEEE Symposium on Logic in Computer Science》|2016年|1-10|共10页
会议地点
作者
Lorenzo Clemente; Paweł Parys; Sylvain Salvati; Igor Walukiewicz;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类
关键词
Automata; Grammar; Computational modeling; Reachability analysis; Servers; Java;

机译：自动机;语法;计算建模;可达性分析;服务器; Java;

相似文献

外文文献
中文文献
专利

1. Types and Higher-Order Recursion Schemes for Verification of Higher-Order Programs [J] . Naoki Kobayashi ACM SIGPLAN Notices: A Monthly Publication of the Special Interest Group on Programming Languages . 2009,第1期

机译：验证高阶程序的类型和高阶递归方案
2. The Complexity of the Diagonal Problem for Recursion Schemes [J] . Pawel Parys LIPIcs : Leibniz International Proceedings in Informatics . 2018,第1期

机译：递归方案的对角线问题的复杂性
3. Streett Automata Model Checking of Higher-Order Recursion Schemes [J] . Ryota Suzuki, Koichi Fujima, Naoki Kobayashi, LIPIcs : Leibniz International Proceedings in Informatics . 2017,第1期

机译：高阶递归方案的Streett自动机模型检查
4. The Diagonal Problem for Higher-Order Recursion Schemes is Decidable* [C] . Lorenzo Clemente, Pawe? Parys, Sylvain Salvati, Annual ACM/IEEE Symposium on Logic in Computer Science . 2016

机译：高阶递归方案的对角线问题是可解除的*
5. Assessment of Equation-of-Motion Coupled-Cluster Methods with Approximate Treatments of Higher-Order Excitations and Development of Novel Schemes for Accurate Calculations of Diradical Electronic Spectra and Bond Breaking [D] . Ajala, Adeayo Olayinka 2017

机译：运动方程耦合簇方法的评估和高阶激励的近似处理，并开发了精确计算双基电子光谱和键断裂的新方案
6. Secondary and tertiary structural foldings in tRNA. A diagonal plot analysis using the blocked nucleotide scheme. [O] . R Malathi, N Yathindra 1982

机译：tRNA中的二级和三级结构折叠。使用封闭核苷酸方案的对角线图分析。
7. The Diagonal Problem for Higher-Order Recursion Schemes is Decidable [O] . Clemente, Lorenzo, Parys, Paweł, Salvati, Sylvain, 2016

机译：高阶递归方案的对角线问题是可以确定的

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable*

摘要

著录项

相似文献

相关主题

期刊订阅