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
- Shieber 1986, An Introduction to Unification-Based Approaches to Grammar formalized
- Carpenter 1992, The Logic of Typed Feature Structures: With Applications to Unification Grammars, Logic Programs and Constraint Resolution
- Plotkin 1970, A Note on Inductive Generalization
- Booij 2019, The role of schemas in Construction Morphology formalized
Declarations
- x.instDecidableIsMaxOfNonemptyOfDecidableEq = decidable_of_iff (x ≠ ⊥) ⋯
A pattern over the positions P gives each position its content and says which positions are
coindexed.
- content : P → α
The content at each position.
- coindex : Setoid P
The coindexation of positions.
Coindexed positions carry the same content.
- coindex_of_isMax ⦃p q : P⦄ : self.content p = self.content q → IsMax (self.content p) → self.coindex p q
Positions that carry the same maximal content are coindexed.
Used by ConstructionMorphology.Pattern.of, ConstructionMorphology.Pattern.ofItem, ConstructionMorphology.Pattern.ofSubscript, ConstructionMorphology.Pattern.comap, ConstructionMorphology.Pattern.ofTerms, ConstructionMorphology.Pattern.instPartialOrder, ConstructionMorphology.Pattern.le_def, ConstructionMorphology.Pattern.le_ofItem_iff, ConstructionMorphology.Pattern.setOf_le_ofItem_sumElim_ne_prod, ConstructionMorphology.Pattern.instSemilatticeInf, ConstructionMorphology.Pattern.instDecidableRelR, ConstructionMorphology.Pattern.instDecidableRelR_1, ConstructionMorphology.Pattern.instDecidableLeOfFintypeOfDecidableLEForallOfDecidableRelR
Used in Audring2019, Booij2010, Booij2019, Bybee1995, Haspelmath2025b and 1 more
Constructors
The pattern with content c whose coindexation is r together with the sameness of maximal
content.
- ConstructionMorphology.Pattern.of c r h = { content := c, coindex := { r := fun (p q : P) => r p q ∨ c p = c q ∧ IsMax (c p), iseqv := ⋯ }, content_eq := ⋯, coindex_of_isMax := ⋯ }
Built from
Used by ConstructionMorphology.Pattern.content_of, ConstructionMorphology.Pattern.coindex_of_iff, ConstructionMorphology.Pattern.ofItem, ConstructionMorphology.Pattern.ofSubscript, ConstructionMorphology.Pattern.instDecidableRelROfDecidableEqOfDecidableIsMax
An item as a pattern, coindexed only where it carries the same maximal content.
Built from ,
Used by ConstructionMorphology.Pattern.comap_ofItem, ConstructionMorphology.Pattern.ofItem_mono, ConstructionMorphology.Pattern.le_ofItem_iff, ConstructionMorphology.Pattern.setOf_le_ofItem_sumElim_ne_prod, ConstructionMorphology.Pattern.ofTerms_le_ofItem_iff, ConstructionMorphology.Pattern.ofTerms_sumElim_le_ofItem_iff, ConstructionMorphology.Pattern.instDecidableRelROfDecidableEqOfDecidableIsMax_1
Used in Audring2019, Booij2010, Booij2019, Bybee1995, Haspelmath2025b and 1 more
The pattern of a subscripting of positions by indices and the content of each index.
- ConstructionMorphology.Pattern.ofSubscript pos body = ConstructionMorphology.Pattern.of (body ∘ pos) (Setoid.ker pos) ⋯
Built from ,
Used by ConstructionMorphology.Pattern.ofTerms, ConstructionMorphology.Pattern.instDecidableRelROfDecidableEqOfDecidableIsMax_2
Used in Booij2010
The pattern read at the positions Q through f.
- ConstructionMorphology.Pattern.comap f s = { content := s.content ∘ f, coindex := Setoid.comap f s.coindex, content_eq := ⋯, coindex_of_isMax := ⋯ }
Built from
Used by ConstructionMorphology.Pattern.comap_ofItem, ConstructionMorphology.Pattern.comap_mono, ConstructionMorphology.Pattern.instDecidableRelR
Used in Audring2019
A pattern written as a row of constants and named variables, as $C_1aC_2C_2aaC_3$.
- ConstructionMorphology.Pattern.ofTerms t = ConstructionMorphology.Pattern.ofSubscript t (Sum.elim Flat.some fun (x : X) => ⊥)
Built from ,
Used by ConstructionMorphology.Pattern.ofTerms_le_ofItem_iff, ConstructionMorphology.Pattern.coindex_ofTerms_iff, ConstructionMorphology.Pattern.ofTerms_le_ofTerms_iff, ConstructionMorphology.Pattern.ofTerms_sumElim_le_ofItem_iff, ConstructionMorphology.Pattern.instDecidableRelROfNonemptyOfDecidableEq
Used in Audring2019, Booij2019, JackendoffAudring2020
Subsumption
Subsumption: s ≤ t when t has at least the content and at least the coindexation of
s.
- ConstructionMorphology.Pattern.instPartialOrder = PartialOrder.lift (fun (s : ConstructionMorphology.Pattern P α) => (s.content, s.coindex)) ⋯
Built from
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.
Built from ,
The meet of two patterns has the meet of their content and coindexes two positions exactly when both do.
The definition is too large to print here; read it in the source.
Built from
Rows of constants and variables
The words that a row of constants and variables subsumes are its substitution instances.
Built from ,
One row subsumes another exactly when the second is a substitution instance of the first.
Built from
Decidability
- ConstructionMorphology.Pattern.instDecidableRelROfDecidableEqOfDecidableIsMax c r h p q = { decide := decide (r p q) || decide (c p = c q ∧ IsMax (c p)), reflects_decide := ⋯ }
Built from
- ConstructionMorphology.Pattern.instDecidableRelROfDecidableEqOfDecidableIsMax_1 w p q = { decide := decide (p = q) || decide (w p = w q ∧ IsMax (w p)), reflects_decide := ⋯ }
Built from
The definition is too large to print here; read it in the source.
Built from
- ConstructionMorphology.Pattern.instDecidableRelR f s p q = ConstructionMorphology.Pattern.instDecidableRelR._aux_1 f s p q
Built from ,
- s.instDecidableLeOfFintypeOfDecidableLEForallOfDecidableRelR t = { decide := decide (s.content ≤ t.content) && decide (∀ ⦃p q : P⦄, s.coindex p q → t.coindex p q), reflects_decide := ⋯ }
Built from