General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond

DOI10.46298/lmcs-18(4:2)2022OpenAlexW4307260824MaRDI QIDQ5060187

Georg Zetzsche, Ramanathan S. Thinniyam, Rupak Majumdar

Publication date: 9 January 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

higher-order asynchronous programshigher-order recursion schemes and decidability

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items (1)

Existential Definability over the Subword Ordering

Uses Software

• OCaml

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The IO- and OI-hierarchies
• Effective constructions in well-partially-ordered free monoids
• Remarks on blind and partially blind one-way multicounter machines
• Undecidable problems in unreliable computations.
• Language and automata theory and applications. 9th international conference, LATA 2015, Nice, France, March 2--6, 2015. Proceedings
• Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
• Well-structured languages
• Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
• Unboundedness and downward closures of higher-order pushdown automata
• Interprocedural analysis of asynchronous programs
• An Approach to Computing Downward Closures
• Decidability Results for Well-Structured Transition Systems with Auxiliary Storage
• Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads
• An automata-theoretical characterization of the OI-hierarchy
• Higher-Order Model Checking: An Overview
• The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
• The Complexity of the Diagonal Problem for Recursion Schemes
• Types and higher-order recursion schemes for verification of higher-order programs
• Indexed Grammars—An Extension of Context-Free Grammars
• On free monoids partially ordered by embedding
• Model Checking Multithreaded Programs with Asynchronous Atomic Methods
• Regular Separability and Intersection Emptiness Are Independent Problems
• Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

This page was built for publication: General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond