Docs / Phonology / Subregular / StringModel

String models

import Linglib.Phonology.Subregular.StringModel · namespace Subregular

This file defines the string models of Chandlee and Jardine, the first-order structures over which quantifier-free formulas state local conditions on strings. The string model of a word has its positions as domain, a unary relation $P_a$ for each symbol $a$, and the successor and predecessor functions $s$ and $p$, the first position being its own predecessor and the last its own successor, so that $\mathrm{first}(x)$ is $p(x) ≈ x$ and $\mathrm{last}(x)$ is $s(x) ≈ x$. Since $s$ and $p$ are functions, a quantifier-free formula in the position variable $x$ reads a bounded window around the position, the syntactic source of strict locality: a formula whose terms step at most l back and r forward cannot tell apart positions whose windows agree. These formulas are the guards of logical transductions.

Main definitions

Main results

Implementation notes

The word models of Subregular.WordModel order positions by a binary relation, over which a quantifier-free formula cannot leave its variables; the window is reached here through the function symbols. HoldsAt evaluates at a natural-number position, false off the word, as the docking processes and transductions scan positions by index. The terms of boolean monadic recursive schemes, Subregular.Walk, instead step off the word into nothing.

References

Declarations

The signature of string models over the alphabet α.

def stringLanguageL69–70
(α : Type u) :
FirstOrder.Language

Built from ,

Used by StringModel.instStructureStringLanguage, StringModel.instDecidableRelMapOfDecidableEq, StringTerm, StringTerm.pdepth, StringTerm.sdepth, StringTerm.pdepth_relabel, StringTerm.sdepth_relabel, StringTerm.realize_offset, StringFormula, StringFormula.Bounded, StringFormula.instDecidableBounded

The string model of a word

The string model of w, whose elements are the positions of w.

def StringModelL76–77
{α : Type u} (w : List α) :

Used by StringModel.instDecidableEq, StringModel.instFintype, StringModel.mk, StringModel.val, StringModel.val_lt, StringModel.ext, StringModel.symbol, StringModel.getElem?_val, StringModel.symbol_eq_iff, StringModel.succ, StringModel.pred, StringModel.val_succ, StringModel.val_pred, StringModel.instStructureStringLanguage, StringModel.instDecidableRelMapOfDecidableEq, StringTerm.realize_succ, StringTerm.realize_pred, StringTerm.val_realize_back, StringTerm.realize_offset, StringFormula.realize_label, StringFormula.realize_first, StringFormula.realize_last, StringFormula.realize_readBack

L93
L95
L97
L102–103
L105–106
L115–117
L119

Terms

L137–138
L157–158
L160–161
L163–166
L168–172
L174–178
L180–184
L186–190
L197–199
L201–203
L205–240

Formulas

Formulas in the position variable.

@[reducible, inline] abbrev StringFormulaL246–247
(α : Type u) :

Built from

Used by StringFormula.label, StringFormula.first, StringFormula.last, StringFormula.HoldsAt, StringFormula.instDecidableHoldsAtOfDecidableEq, StringFormula.HoldsAt.lt_length, StringFormula.holdsAt_not, StringFormula.holdsAt_inf, StringFormula.holdsAt_sup, StringFormula.bounded_not, StringFormula.bounded_inf, StringFormula.bounded_sup, StringFormula.Bounded.holdsAt_congr, StringFormula.readBack, StringFormula.window

Used in Phonology/Subregular/Transduction, Dolatian2020, Lionnet2025

L265–266
L268–272
L274–280

φ.HoldsAt w n: n is a position of w, and φ holds there.

def StringFormula.HoldsAtL282–284
{α : Type u} (φ : StringFormula α) (w : List α) (n : ℕ) :
  • φ.HoldsAt w n = ∃ (h : n < w.length), FirstOrder.Language.Formula.Realize φ fun (x : Fin 1) => StringModel.mk n h

Built from ,

Used by StringFormula.instDecidableHoldsAtOfDecidableEq, StringFormula.HoldsAt.lt_length, StringFormula.holdsAt_top, StringFormula.holdsAt_not, StringFormula.holdsAt_inf, StringFormula.holdsAt_sup, StringFormula.holdsAt_label_var, StringFormula.Bounded.holdsAt_congr, StringFormula.holdsAt_window

Used in Phonology/Subregular/Transduction, Lionnet2025

L286–287
L291
L293–294
L296–298
L307–313

Bounded formulas read only a window

A formula is bounded by l back and r forward if it is quantifier-free and each of its terms takes at most l predecessor and r successor steps, so that it reads only the window from l before its position to r after.

def StringFormula.BoundedL317–325
{α : Type u} (l r : ℕ) {n : ℕ} :
(stringLanguage α).BoundedFormula (Fin 1) n → Prop

The definition is too large to print here; read it in the source.

Built from , ,

Used by StringFormula.instDecidableBounded, StringFormula.bounded_top, StringFormula.bounded_not, StringFormula.bounded_inf, StringFormula.bounded_sup, StringFormula.bounded_label, StringFormula.bounded_first, StringFormula.bounded_last, StringFormula.Bounded.holdsAt_congr, StringFormula.bounded_readBack, StringFormula.bounded_window

Used in Phonology/Subregular/Transduction, Lionnet2025

L327–333
L337
L339

A formula bounded by l back and r forward has the same truth value at n in w and at n' in w' when the windows agree: the positions are equally far from the left edge up to l, and the offsets up to l back and r forward carry the same symbols or none.

theorem StringFormula.Bounded.holdsAt_congrL416–432
{α : Type u} {w : List α} {φ : StringFormula α} {n l r : ℕ} (hφ : Bounded l r φ) {w' : List α} {n' : ℕ} (hedge : min n l = min n' l) (hleft : ∀ j ≤ l, w[n - j]? = w'[n' - j]?) (hright : ∀ j ≤ r, w[n + j]? = w'[n' + j]?) :
φ.HoldsAt w n ↔ φ.HoldsAt w' n'

Built from , ,

Window tests

window r u holds at a position when the last r symbols before it, or all of them if there are fewer than r, spell u.

def StringFormula.windowL442–445
{α : Type u} (r : ℕ) (u : List α) :

Built from , , ,

Used by StringFormula.holdsAt_window, StringFormula.bounded_window

L447–466
L468–474

At a position of the word, window r u holds exactly when the last r symbols before the position spell u.

theorem StringFormula.holdsAt_windowL476–491
{α : Type u} {w : List α} {n r : ℕ} {u : List α} (hn : n < w.length) (hu : u.length ≤ r) :
(window r u).HoldsAt w n ↔ (List.take n w).rtake r = u

Built from ,

L493–499