The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

DOI10.1145/2933575.2934527zbMath1401.68158arXiv1605.00371MaRDI QIDQ4635865

Igor Walukiewicz, Sylvain Salvati, Paweł Parys, Lorenzo Clemente

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.00371

zbMATH Keywords

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

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

03B25: Decidability of theories and sets of sentences

68Q42: Grammars and rewriting systems