Docs / Phonology / Subregular / MultitierDefinite

The equations of the multitier definite and reverse definite languages

import Linglib.Phonology.Subregular.MultitierDefinite

A monoid is multitier reverse definite when it is aperiodic and every idempotent e satisfies e x e = e x; in a finite monoid this is the equation x^ω y x = x^ω y, and it yields the equation x y₁ x y₂ ⋯ x yₙ x = x y₁ x y₂ ⋯ x yₙ for n the size of the monoid. Over a finite alphabet, a language is multitier reverse definite exactly when its syntactic monoid is. The monoid side is Pin's theorem as reported by Almeida: the monoids generated by the reverse definite semigroups are those satisfying the first equation, equivalently the second for some n.

A monoid is multitier definite when its opposite is multitier reverse definite, which in a finite monoid is the equation x y x^ω = y x^ω. Reversing a language exchanges the definite and reverse definite classes and turns its syntactic monoid into the opposite, so a language is multitier definite exactly when its syntactic monoid is.

Implementation notes

The equations of Lambert and Almeida use the omega power x^ω; isMultitierReverseDefinite_iff states the first through idempotent powers instead. Almeida states the reverse definite case, with the proof he gives for the finite and cofinite one, through a lemma on products in a monoid with n elements; the definite case is its dual. The proof here goes through words: once a letter has occurred n times, where n is the size of the syntactic monoid, further occurrences leave the syntactic class unchanged, so the class of a word is determined by its first n occurrences of each letter, and these are read off the tier projections up to length n times the size of the alphabet. Such a language is multitier reverse definite by Language.mem_multitierReverseDefinite_iff.

References

Declarations

L56–59
L85–103

In a finite multitier reverse definite monoid, a product of at least |M| factors x * yᵢ absorbs a further x. Two of its first |M| + 1 prefix products coincide, so a prefix a satisfies a * u = a for a segment u beginning with x, and the idempotent power of u absorbs x.

theorem Monoid.IsMultitierReverseDefinite.prod_map_mul_mul_eqL105–142
{M : Type u_1} [Monoid M] [Finite M] (h : IsMultitierReverseDefinite M) (x : M) {ys : List M} (hys : Nat.card M ≤ ys.length) :
(List.map (fun (x_1 : M) => x * x_1) ys).prod * x = (List.map (fun (x_1 : M) => x * x_1) ys).prod

Built from

A finite monoid is multitier reverse definite exactly when it satisfies Lambert's equation x^ω y x = x^ω y, stated through the idempotent powers of x.

theorem Monoid.isMultitierReverseDefinite_iffL146–156
{M : Type u_1} [Monoid M] [Finite M] :
IsMultitierReverseDefinite M ↔ ∀ (x y : M) (n : ℕ), n ≠ 0 → IsIdempotentElem (x ^ n) → x ^ n * y * x = x ^ n * y

Built from

Multitier definite monoids

L172–175
L211–212

A finite monoid is multitier definite exactly when it satisfies Lambert's equation x y x^ω = y x^ω, stated through the idempotent powers of x.

theorem Monoid.isMultitierDefinite_iffL216–227
{M : Type u_1} [Monoid M] [Finite M] :
IsMultitierDefinite M ↔ ∀ (x y : M) (n : ℕ), n ≠ 0 → IsIdempotentElem (x ^ n) → x * y * x ^ n = y * x ^ n

Built from

Multitier reverse definite languages satisfy the equation

Languages satisfying the equation are multitier reverse definite

Multitier definite languages, by reversal