Docs / Morphology / ConstructionMorphology / Pattern

Patterns and subsumption

import Linglib.Morphology.ConstructionMorphology.Pattern

A pattern over a type of positions gives each position its content and says which positions are coindexed. A slot below a maximal element is a variable, and coindexed variables are filled alike, as the second root consonant of the Damascus Arabic template $C_1aC_2C_2aaC_3$ is. Patterns are ordered by subsumption: s ≤ t when t has at least the content and at least the coindexation of s. This is the subsumption of Shieber 1986 and Carpenter 1992 for feature structures of depth one, with coindexation as reentrancy.

A word is a pattern whose slots are all maximal, and a pattern written as a row of constants and named variables subsumes exactly its substitution instances, among rows as among words. The meet of two patterns is their least general generalization in the sense of Plotkin 1970: it coindexes two positions exactly when both do. A schema that relates two words is a pattern over the disjoint union of their positions, and once it coindexes a position of each, the pairs it subsumes are not a product of conditions on the words separately.

Implementation notes

Positions that carry the same maximal content are always coindexed. Without this condition a constant written twice could be coindexed or not, giving two patterns with the same instances. The index type of a schema's notation is not part of a pattern: Pattern.ofSubscript and Pattern.ofTerms keep only which positions share an index.

References

Declarations

L53–55
L66–77

Constructors

L86–102
L104
L106–108
L110–111
L113–115
L117–122
L124–126
L130–132

Subsumption

L147–148
L150–153
L155–160

The pairs of items that a pattern over two sets of positions subsumes are not the product of a set of first items and a set of second items, once the pattern coindexes a position of each and two pairs fill those positions differently.

theorem ConstructionMorphology.Pattern.setOf_le_ofItem_sumElim_ne_prodL162–174
{P₁ : Type u_3} {P₂ : Type u_4} {α : Type u_6} [PartialOrder α] {s : Pattern (P₁ ⊕ P₂) α} {w₁ w₁' : P₁ → α} {w₂ w₂' : P₂ → α} (h : s ≤ ofItem (Sum.elim w₁ w₂)) (h' : s ≤ ofItem (Sum.elim w₁' w₂')) {a : P₁} {b : P₂} (hab : s.coindex (Sum.inl a) (Sum.inr b)) (hne : w₁ a ≠ w₂' b) (A : Set (P₁ → α)) (B : Set (P₂ → α)) :
{(x, y) : (P₁ → α) × (P₂ → α) | s ≤ ofItem (Sum.elim x y)} ≠ A ×ˢ B

Built from ,

L178–196

Rows of constants and variables

L232–242
L269–276

Decidability

L280–282
L284–286
L288–291
L293–295
L301–303
L305–307