Regular path expressions in feature logic

Abstract

We examine the existential fragment of a feature logic, which is extended by regular path expressions. A regular path expression is a subterm relation, where the allowed paths for the subterms are restricted to any given regular language. We will prove that satisfiability is decidable. This is achieved by setting up a quasi-terminating rule system.