Paper: On The Decidability Of Functional Uncertainty

ACL ID P93-1027
Title On The Decidability Of Functional Uncertainty
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1993
  • Rolf Backofen (German Research Center for Artificial Intelligence, Saarbrucken Germany)

We show that feature logic extended by functional uncertainty is decidable, even if one admits cyclic descriptions. We present an algorithm, which solves feature descriptions containing functional un- certainty in two phases, both phases using a set of de- terministic and non-deterministic rewrite rules. We then compare our algorithm with the one of Kaplan and Maxwell, that does not cover cyclic feature de- scriptions.