Documentation

Provenance.Semirings.Regex

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:

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.

noncomputable def Language.deltaInd {ฮฑ : Type} (l : Language ฮฑ) :
Language ฮฑ

ProvSQL's Regex::delta: the indicator of being non-empty.

Equations
Instances For
    Dependency graph
    Dependency graph
    theorem Language.one_ne_zero' {ฮฑ : Type} :

    {ฮต} is not โˆ….

    Dependency graph
    theorem Language.natCast_pos {ฮฑ : Type} {n : โ„•} (hn : 0 < n) :
    โ†‘n = 1

    Every positive natural-number cast is ๐Ÿ™, union being idempotent.

    Dependency graph
    @[instance_reducible]
    noncomputable instance Language.instSemiringWithMonus {ฮฑ : Type} :

    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.
    Dependency graph

    The star identities ProvSQL's simplifier applies #