ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Regex.h File Reference

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"
Include dependency graph for Regex.h:
This graph shows which files directly or indirectly include this file:

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

Detailed Description

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 merged
  • times() → "a · b"
  • star() → "(a)*"

Equality is syntactic: two expressions of the same language may compare unequal, which only leaves an alternative unmerged.

See also
https://provsql.org/lean-docs/Provenance/Semirings/Regex.html Lean 4 verified instance: 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.