Venue

Publication Year

2009

Keywords

Context Logic, decidability, trees, automata

Authors

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.

Source Materials