On the expressivity of feature logics with negation, functional uncertainty, and sort equations

Abstract

. Feature logics are the logical basis for so-called unification grammars studied in computational linguistics. We investigate the expressivity of feature terms with negation and the functional uncertainty construct needed for the description of long-distance dependencies and obtain the following results: satisfiability of feature terms is undecidable, sort equations can be internalized, consistency of sort equations is decidable if there is at least one atom, and consistency of sort equations is undecidable if there is no atom. Key words: Feature Logic, Functional Uncertainty, Sort Equations, Undecidability 1 Introduction Feature constraint grammars, also known as unification grammars, have become the predominant family of declarative grammar formalisms in Computational Linguistics (Kay, 1979; Kaplan and Bresnan, 1982; Shieber et al., 1983; Shieber, 1986; Pollard and Sag, 1987). The common assumption of these formalisms is that linguistic objects can be described by means of their f...

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 69 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.