Docs / Studies / Studies.Lambert2023

Relativized adjacency

Lambert, D. (2023). Journal of Logic, Language and Information, 32, 707–731

Lambert characterizes the tier-based strictly local languages by two closure conditions on a tier: the symbols off it are freely insertable and deletable, and suffixes cross over middles with one projection. A refutation finds symbols that are not freely insertable and words over them that violate the crossover, so the constraint against a … b … a is not tier-based strictly local though it is strictly piecewise. On a canonical automaton the freely insertable symbols are those that loop on every state, in Figure 3 only d. The figure's stringset is tier-based strictly local but not strictly local, and its salient symbols are its least tier.

Implementation notes

Figure 3 draws the canonical automaton, which leaves out the nonaccepting sink; fig3DFA restores it so that its transition function is total. The figure's stringset is shown tier-based strictly local through the closure conditions rather than by a grammar, the route Lambert describes for reading a tier off an automaton.

References

Declarations

A precedence constraint

A precedence constraint that is not tier-based strictly local (p. 715). Since b is not freely insertable it lies on every tier, so suffix substitution across a middle of bs carries a b⋯b b and b b⋯b a to a b⋯b a. Lambert's middle has k - 1 symbols; it has k + 1 here so that the argument covers every width.

theorem abaFree_not_isTierStrictlyLocalL65–81

Built from

Salience on an automaton

Figure 3's stringset is tier-based strictly 2-local (§4.1), by Lambert's characterization: off the tier {a, b, c} only d remains, which is freely insertable, and the state after a middle with a tier symbol depends only on its last one, so suffixes cross over such middles.

theorem fig3_isTierStrictlyLocalL170–177

Built from

The salient symbols are the least tier (§4.1). Figure 3's stringset is generated at width 2 on the tier {a, b, c}, and every grammar that generates it, at any width, has a, b and c on its tier.

theorem fig3_least_tierL179–188
:
(∃ (G : TierStrictlyLocalGrammar Sym), TierStrictlyLocalGrammar.language 2 G = fig3 ∧ ∀ (x : Sym), G.tier x ↔ x ≠ Sym.d) ∧ ∀ (k : ℕ) (G : TierStrictlyLocalGrammar Sym), TierStrictlyLocalGrammar.language k G = fig3 → ∀ (x : Sym), x ≠ Sym.d → G.tier x

Built from ,

Figure 3's stringset is not strictly local (Figure 4). A run of ds of any length separates a from b, so suffix substitution carries a d⋯d a and b d⋯d b to a d⋯d b; Lambert reads the same fact off a cycle of the powerset graph.

theorem fig3_not_isStrictlyLocalL190–204
(k : ℕ) :

Built from