The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

被引：16

作者：

Clemente, Lorenzo ^{[1
]}

Parys, Pawel ^{[1
]}

Salvati, Sylvain ^{[2
]}

Walukiewicz, Igor ^{[2
]}

机构：

[1] Univ Warsaw, Warsaw, Poland

[2] Univ Bordeaux, CNRS, INRIA, Bordeaux, France

来源：

PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016) | 2016年

关键词：

downward closure; separability problem; diagonal problem; higher-order recursion schemes; higher-order OI grammars;

D O I：

10.1145/2933575.2934527

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：96 / 105

页数：10

共 28 条

[1]

Abdulla PA, 2001, LECT NOTES COMPUT SC, V2076, P639

[2] INDEXED GRAMMARS - AN EXTENSION OF CONTEXT-FREE GRAMMARS [J].

AHO, AV .

JOURNAL OF THE ACM, 1968, 15 (04) :647-&

[3]

[Anonymous], 2008, Tree Automata Techniques and Applications

[4]

[Anonymous], 1996, INT J FOUND COMPUT S, DOI DOI 10.1142/S0129054196000191

[5]

Asada K., 2016, P ICALP 16 IN PRESS

[6]

Bachmeier Georg, 2015, Language and Automata Theory and Applications. 9th International Conference, LATA 2015. Proceedings: LNCS 8977, P473, DOI 10.1007/978-3-319-15579-1_37

[7] Recursion Schemes and Logical Reflection [J].

Broadbent, Christopher H. ;

Carayol, Arnaud ;

Ong, C-H. Luke ;

Serre, Olivier .

25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, :120-129

[8]

Clemente L, 2015, 35 IARCS ANN C FDN S, V45, P163, DOI [10.4230/LIPIcs.FSTTCS. 2015.163, DOI 10.4230/LIPICS.FSTTCS.2015.163]

[9]

Clemente L., 2016, DIAGONAL PROBLEM HIG

[10]

Courcelle B., 1991, B EATCS

← 1 2 3 →