Abstract
Functional uncertainty (FU) is a critical component in unification grammars like Lexical Functional Grammar (LFG), allowing for the description of long-distance dependencies via regular path expressions. However, the decidability of FU in the presence of cyclic feature structures remained an open problem for years. This paper presents a two-phase algorithm that utilizes path variables and non-deterministic rewrite rules to prove that FU is indeed decidable even with cycles.
Introduction
In computational linguistics, feature logic is used to describe abstract objects through feature structures. A powerful extension of this logic is functional uncertainty (FU), which allows for constraints based on regular expressions over paths. For example, instead of specifying a fixed path from variable $x$ to $y$, FU allows one to state that there exists some path described by a regular language $L$ connecting them. This is essential for modeling linguistic phenomena like long-distance dependencies.
Historically, algorithms for FU (notably those by Kaplan and Maxwell) were only guaranteed to terminate on acyclic feature structures. When faced with cycles, these methods often fell into infinite loops by continuously generating new variables. This paper addresses the long-standing question of whether FU remains decidable when cycles are permitted.
Methods: A Two-Phase Algorithm
Rolf Backofen proposes a novel two-phase algorithm that shifts the focus from node-based reasoning to path-based reasoning. The syntax of the constraints handled by this logic is shown in the figure above, including sort restrictions, agreements, and path restrictions ($p \dot{\in} L$).
Phase 1: Normalization via Path Variables
The core innovation is the introduction of path variables ($\alpha, \beta, \dots$). By treating paths as first-class citizens, the algorithm can reason about relationships like prefixing or equality without immediately resolving the specific nodes involved. The algorithm uses a set of non-deterministic rewrite rules to transform a clause into a "pre-solved" form.
As seen in the rewrite rules above, the system handles equality (Eq), prefixes (Pre), and divergences (Div) by manipulating the set of constraints $\psi$. The "secret sauce" of this approach is quasi-termination. Although the rules could theoretically cycle, Backofen proves that they only produce a finite number of unique clauses. By tracking these states, the algorithm detects when the search space is exhausted and terminates.
Phase 2: Consistency Checking
Once the constraints are in pre-solved form, the algorithm performs a final consistency check. It verifies if the constraints on path variables—such as divergence (where two paths branch off) or path equality—are mutually satisfiable. By delaying the resolution of divergence, the method avoids the infinite variable creation that plagued previous approaches.
Key Insights and Results
- Decoupling Nodes and Paths: By reasoning about path relationships independently of node identities, the algorithm avoids premature commitment to specific graph structures that might lead to infinite loops in cyclic cases.
- Regular Language Decomposition: The algorithm leverages the property that regular languages can be decomposed into finite sets of simpler languages, allowing complex FU constraints to be broken down into manageable pieces.
- Proof of Decidability: The primary contribution is the formal proof that consistency for feature descriptions with functional uncertainty (without negation) is decidable, even in the presence of cycles.
- Completeness: The author provides a sound and complete algorithm, ensuring that a solution will be found if one exists, and a failure will be reported otherwise.
Limitations and Future Work
While this work solves the decidability of positive FU constraints, the author notes that adding negation to the logic renders it undecidable. Furthermore, while the problem is proven to be decidable, the computational complexity of the non-deterministic rewrite system remains a topic for further analysis. Future work may focus on optimizing these rewrite rules for practical implementation in large-scale linguistic parsers.
Summary updated