Regular Path Expressions in Feature Logic

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. In the area of computational linguistics, this notion has been introduced as "functional uncertainty". We will prove that satisfiability is decidable by constructing a quasi-terminating rule system.