Decidability of Context Logic
Authors
- Christiano Calcagno
- Thomas Dinsdale-Young
- Philippa Gardner
Abstract
We consider the problem of decidability for Context Logic for sequences, ranked trees and unranked trees. We show how to translate quantifier-free formulae into finite automata that accept just the sequences or trees which satisfy the formulae. Satisfiability is thereby reduced to the language emptiness problem for finite automata, which is simply a question of reachability. This reduction shows that Context Logic formulae define languages that are regular; indeed, we show that for sequences they are exactly the star-free regular languages. We also show that satisfiability is still decidable when quantification over context hole labels is added to the logic, by reducing the problem to the quantifier-free case.
Venue
Publication Date
2009
Keywords
Context Logic, decidability, trees, automata