REGULAR PATH EXPRESSIONS IN FEATURE LOGIC

We examine the existential fragment of a feature logic, which is exten ded by regular path expressions. A regular path expression is a subter m relation, where the allowed paths for the subterms are restricted to any given regular language. In the ama of computational linguistics, this notion has been introduced as ''functional uncertainty''. We will prove that satisfiability is decidable by constructing a quasi-termin ating rule system.