Nondeterministic Phase Semantics and the Undecidability of Boolean BI

DOI10.1145/2422085.2422091zbMath1343.03022OpenAlexW2017959340MaRDI QIDQ2946690

Dominique Larchey-Wendling, Didier Galmiche

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422085.2422091

zbMATH Keywords

decidabilitylinear logicBoolean BIMinsky machines encoding

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items

Expressive Completeness of Separation Logic with Two Variables and No Separating Conjunction, A Unified Display Proof Theory for Bunched Logic, An Alternative Direct Simulation of Minsky Machines into Classical Bunched Logics via Group Semantics, Completeness for a First-Order Abstract Separation Logic, Undecidability of Propositional Separation Logic and Its Neighbours, Separation logic with one quantified variable, Exponential-Size Model Property for PDL with Separating Parallel Composition, Nonelementary Complexities for Branching VASS, MELL, and Extensions, Separation logics and modalities: a survey, Proof tactics for assertions in separation logic, Two-Variable Separation Logic and Its Inner Circle, An epistemic separation logic with action models, On the almighty wand, An algebraic glimpse at bunched implications and separation logic, Unnamed Item, Complexity Optimal Decision Procedure for a Propositional Dynamic Logic with Parallel Composition, Unnamed Item