The function symbols of string models, successor and predecessor.
Used by stringLanguage
Docs / Phonology / Subregular / StringModel
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.
Subregular.stringLanguage: the signature $\{s, p, P_a\}$.Subregular.StringModel: the string model of a word.Subregular.StringFormula: formulas in the position variable, with StringFormula.HoldsAt.StringFormula.Bounded l r: quantifier-free, with terms at most l back and r forward.StringFormula.window r u: the last r symbols before the position spell u.StringFormula.Bounded.holdsAt_congr: a bounded formula cannot distinguish positions whose
windows agree.StringFormula.holdsAt_window: window r u holds where the last r symbols spell u.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.
The function symbols of string models, successor and predecessor.
Used by stringLanguage
The relation symbols of string models, a unary label for each symbol.
Used by stringLanguage
The signature of string models over the alphabet α.
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 w, whose elements are the positions of w.
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
Built from
Built from
Position n of w.
Built from
Used by StringModel.val_mk, StringModel.succ, StringModel.pred, StringFormula.HoldsAt
The index of a position.
Built from
Used by StringModel.val_lt, StringModel.val_mk, StringModel.ext, StringModel.getElem?_val, StringModel.symbol_eq_iff, StringModel.succ, StringModel.pred, StringModel.val_succ, StringModel.val_pred, StringTerm.val_realize_back, StringTerm.realize_offset, StringFormula.realize_first, StringFormula.realize_last, StringFormula.realize_readBack
Built from ,
Built from ,
The symbol at a position.
Built from
Used by StringModel.getElem?_val, StringModel.symbol_eq_iff, StringModel.instDecidableRelMapOfDecidableEq, StringFormula.realize_label
Built from , ,
Built from , ,
The successor of a position, the last position being its own.
Built from , ,
The predecessor of a position, the first position being its own.
Built from , ,
Built from , ,
The definition is too large to print here; read it in the source.
Built from ,
Built from , ,
Terms in the position variable.
Built from
Used by StringTerm.succ, StringTerm.pred, StringTerm.back, StringTerm.realize_succ, StringTerm.realize_pred, StringTerm.pdepth_succ, StringTerm.pdepth_pred, StringTerm.sdepth_succ, StringTerm.sdepth_pred, StringFormula.label, StringFormula.first, StringFormula.last, StringFormula.realize_label, StringFormula.realize_first, StringFormula.realize_last, StringFormula.bounded_label, StringFormula.bounded_first, StringFormula.bounded_last
Used in Dolatian2020, Lionnet2025
The successor $s(t)$ of a term.
Built from
Used by StringTerm.realize_succ, StringTerm.pdepth_succ, StringTerm.sdepth_succ, StringFormula.last
Used in Lionnet2025
The predecessor $p(t)$ of a term.
Built from
Used by StringTerm.back, StringTerm.realize_pred, StringTerm.pdepth_pred, StringTerm.sdepth_pred, StringFormula.first
Used in Lionnet2025
The term j predecessor steps back from the position variable.
Built from ,
Used by StringTerm.val_realize_back, StringTerm.pdepth_back, StringTerm.sdepth_back, StringFormula.window
Built from , , ,
Built from , , ,
Built from , ,
The number of predecessor steps of a term, which bounds how far back it reaches.
Built from
Used by StringTerm.pdepth_relabel, StringTerm.pdepth_succ, StringTerm.pdepth_pred, StringTerm.pdepth_back, StringTerm.realize_offset, StringFormula.Bounded, StringFormula.bounded_label, StringFormula.bounded_first, StringFormula.bounded_last
The number of successor steps of a term, which bounds how far forward it reaches.
Built from
Used by StringTerm.sdepth_relabel, StringTerm.sdepth_succ, StringTerm.sdepth_pred, StringTerm.sdepth_back, StringTerm.realize_offset, StringFormula.Bounded, StringFormula.bounded_label, StringFormula.bounded_first, StringFormula.bounded_last
Built from , ,
Built from , ,
Built from , ,
Built from , ,
A term evaluated where every variable denotes position i lands within its depths of i, and
at the same offset from i in w as from i' in w' when the two positions are equally far
from the left edge up to l and the same offsets up to r forward are positions.
Built from , , , ,
Formulas in the position variable.
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
$P_a(t)$: term t reads symbol a.
Built from ,
Used by StringFormula.realize_label, StringFormula.holdsAt_label_var, StringFormula.bounded_label
Used in Lionnet2025
$\mathrm{first}(t)$, that is $p(t) ≈ t$: term t reads the first position.
Built from , ,
Used by StringFormula.realize_first, StringFormula.bounded_first, StringFormula.window
$\mathrm{last}(t)$, that is $s(t) ≈ t$: term t reads the last position.
Built from , ,
Used by StringFormula.realize_last, StringFormula.bounded_last
Built from , , ,
Built from , , ,
Built from , , ,
φ.HoldsAt w n: n is a position of w, and φ holds there.
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
The definition is too large to print here; read it in the source.
Built from ,
Built from ,
Built from ,
Built from ,
Built from ,
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.
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
The definition is too large to print here; read it in the source.
Built from ,
Built from ,
Built from ,
Built from ,
Built from , , , ,
Built from , , , ,
Built from , , , ,
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.
Built from , ,
readBack v j holds at a position when the positions j + 1, j + 2, … back exist and carry
v, nearest first.
The definition is too large to print here; read it in the source.
Built from
Used by StringFormula.window, StringFormula.realize_readBack, StringFormula.bounded_readBack
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.
Built from , , ,
Used by StringFormula.holdsAt_window, StringFormula.bounded_window
Built from , ,
At a position of the word, window r u holds exactly when the last r symbols before the
position spell u.
Built from ,