The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

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

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

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 problemhigher-order recursion schemesdownward closurediagonal problemhigher-order OI grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond, Recursion Schemes and the WMSO+U Logic, Cost Automata, Safe Schemes, and Downward Closures, Unboundedness problems for machines with reversal-bounded counters, Existential Definability over the Subword Ordering, Unnamed Item, Unnamed Item, General decidability results for asynchronous shared-memory programs: higher-order and beyond, Unnamed Item, The Complexity of the Diagonal Problem for Recursion Schemes