The regular-expression m-semiring (ProvSQL's sr_regex) #
The semiring of languages over an alphabet of labels, with โ the union,
โ the concatenation, ๐ = โ
and ๐ = {ฮต}: Language ฮฑ of Mathlib,
whose Semiring instance is exactly this. ProvSQL's sr_regex
(src/semiring/Regex.h, since 1.13.0) computes in it, each value written
as a regular expression, a product gate concatenating its factors in the
order of the query. Concatenation does not commute, so this is an
entry of the catalog whose multiplication is not commutative:
not_commutative below exhibits a ยท b โ b ยท a.
What ProvSQL claims of it, verified here:
- it is an m-semiring: the natural order is inclusion, the monus is the
difference of languages (Mathlib's
OrderedSubinstance is preciselymonus_spec), andฮดis the indicator of being non-empty โ ProvSQL refuses to compute the monus (semiring-no-monus: it needs automata, and๐ โ L = ๐for a language without the empty word, which is right but registers no absence), but the monus exists, so the refusal is a gap of the implementation and not of the algebra; โis idempotent (idempotent_add) and the semiring is complemented (complemented_of), but neither absorptive nor exclusive (not_absorptive:๐ โ a โ ๐as soon asaholds a non-empty word;not_exclusive:{a} โ (๐ โ {a}) = {a} โ ๐, the monus of๐by a language without the empty word being๐itself);- every value has a Kleene star (Mathlib's
Language.kstar), with the identities ProvSQL's simplifier applies:(ฮต โช a)โ = aโ,(aโ)โ = aโ,โ โ = ฮตโ = ฮต, andaโ = ๐ โ a โ aโon either side (Language.one_add_self_mul_kstar_eq_kstar,Language.one_add_kstar_mul_self_eq_kstar).
The restriction to regular languages is a representation matter: ProvSQL writes its values as regular expressions and its operations keep them regular, so its values form a subsemiring of this one, closed under the star; the algebra is the same.
ProvSQL's Regex::delta: the indicator of being non-empty.
Instances For
Dependency graph
Dependency graph
Dependency graph
Every positive natural-number cast is ๐, union being idempotent.
Dependency graph
Languages form an m-semiring: inclusion for the order, the
difference for the monus, the indicator of non-emptiness for ฮด.
Equations
- One or more equations did not get rendered due to their size.