![]() |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
Regular-expression semiring: the derivations of a tuple as a language over the labels of its input tuples. More...
#include <cstddef>#include <functional>#include <memory>#include <string>#include <vector>#include "Semiring.h"#include "../Circuit.h"

Go to the source code of this file.
Classes | |
| struct | semiring::regex_t |
| A regular expression: an immutable tree, shared between the expressions built from it. More... | |
| struct | semiring::regex_node |
A node of a regex_t. More... | |
| struct | semiring::regex_ops |
Operations on regular expressions, shared by Regex and TropicalPaths. More... | |
| class | semiring::Regex |
The regular-expression semiring over regex_t. More... | |
Namespaces | |
| namespace | semiring |
Regular-expression semiring: the derivations of a tuple as a language over the labels of its input tuples.
The semiring of regular languages over an alphabet of labels, with \(\oplus\) union, \(\otimes\) concatenation, \(\mathbb{0} =
\emptyset\) and \(\mathbb{1} = \{\varepsilon\}\), each language written as a regular expression. Concatenation does not commute: a product gate concatenates its factors in the order of the query, that of the FROM clause for a join, so that a path query reads its paths in the order it extends them.
Every value has a star, the Kleene star, which makes the regular expression of a recursion on cyclic data its exact least solution: the equations are solved by Gaussian elimination (state elimination, in automata terms), provided the recursive relation is on the same side of every coefficient (see GenericCircuit::solveFixSystem).
Operations:
zero() → \(\emptyset\)one() → \(\varepsilon\)plus() → "a | b", alternatives that render alike mergedtimes() → "a · b" star() → "(a)*" Equality is syntactic: two expressions of the same language may compare unequal, which only leaves an alternative unmerged.
Language.instSemiringWithMonus, whose monus, the difference of languages, this implementation does not compute; with proofs of Language.not_commutative, Language.not_absorptive, Language.not_exclusive, Language.complemented_of and of the star identities (Language.kstar_one_add, Language.kstar_kstar). Definition in file Regex.h.