![]() |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
The Viterbi (max-times) m-semiring over double.
More...
#include "Viterbi.h"


Public Member Functions | |
| virtual value_type | zero () const override |
| Return the additive identity \(\mathbb{0}\). | |
| virtual value_type | one () const override |
| Return the multiplicative identity \(\mathbb{1}\). | |
| virtual value_type | plus (const std::vector< value_type > &v) const override |
| Apply the additive operation to a list of values. | |
| virtual value_type | times (const std::vector< value_type > &v) const override |
| Apply the multiplicative operation to a list of values. | |
| virtual value_type | monus (value_type x, value_type y) const override |
| Apply the monus (m-semiring difference) operation. | |
| virtual value_type | delta (value_type x) const override |
| Apply the \(\delta\) operator. | |
| virtual bool | absorptive () const override |
Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)). | |
| virtual bool | selective () const override |
Return true if \(\oplus\) is selective (for all \(a, b\), \(a \oplus b \in \{a, b\}\)). | |
| virtual bool | mul_sub_left_distributive () const override |
\(\otimes\) distributes over \(\ominus\), so the HAVING MIN / MAX comparisons take the single-scan closed form. | |
| virtual bool | compatibleWithBooleanRewrite () const override |
No semiring homomorphism BoolFunc(Y) →+* Viterbi exists (real multiplication is not idempotent), so the safe-query Boolean rewrite is unsound under the Viterbi semiring. | |
| value_type | parse_leaf (const char *v) const |
| Public Member Functions inherited from semiring::Semiring< double > | |
| virtual value_type | plus_of (const std::vector< const value_type * > &v) const |
plus over the values v points to, read in place. | |
| virtual value_type | times_of (const std::vector< const value_type * > &v) const |
times over the values v points to, read in place (see plus_of). | |
| virtual value_type | cmp (value_type s1, ComparisonOperator op, value_type s2) const |
| Evaluate a comparison gate. | |
| virtual value_type | semimod (value_type x, value_type s) const |
| Apply a semimodule scalar multiplication. | |
| virtual value_type | agg (AggregationOperator op, const std::vector< value_type > &s) |
| Evaluate an aggregation gate. | |
| virtual value_type | value (const std::string &s) const |
| Interpret a literal string as a semiring value. | |
| virtual value_type | unmapped_input (const std::string &uuid) const |
Value of a variable leaf (gate_input / gate_mulinput) that the provenance mapping does not name. | |
| virtual value_type | rv (const std::string &spec, const std::vector< value_type > ¶ms) const |
Evaluate a continuous random-variable leaf (gate_rv). | |
| virtual value_type | arith (ArithmeticOperator op, const std::vector< value_type > &children, const std::string &extra) const |
Evaluate an arithmetic gate over scalar children (gate_arith). | |
| virtual value_type | mixture (value_type p, value_type x, value_type y) const |
Evaluate a Bernoulli mixture (gate_mixture, three wires). | |
| virtual value_type | categorical (value_type key, const std::vector< double > &probs, const std::vector< std::string > &outcomes) const |
Evaluate a categorical mixture (gate_mixture over gate_mulinput outcomes). | |
| virtual value_type | guarded_case (const std::vector< value_type > &children) const |
Evaluate a guarded selection (gate_case). | |
| virtual value_type | observe (value_type child, const std::string &datum) const |
Evaluate a latent-variable observation (gate_observe). | |
| virtual value_type | conditioned (const std::vector< value_type > &children) const |
Evaluate a conditioning marker (gate_conditioned). | |
| virtual | ~Semiring ()=default |
| virtual bool | idempotent () const |
Return true if this semiring is idempotent ( \(a \oplus a = a\) for all \(a\)). | |
| virtual bool | commutative () const |
Return true if \(\otimes\) is commutative ( \(a \otimes b = b \otimes a\) for all \(a, b\)). | |
| virtual bool | has_star () const |
Return true if star computes \(a^* = \mathbb{1} \oplus a \oplus a^2 \oplus \cdots\). | |
| virtual value_type | star (const value_type &a) const |
\(a^*\), the sum of the powers of a. | |
| virtual bool | symbolic () const |
Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown, define). | |
| virtual value_type | symbolic_unknown (std::size_t position) const |
| A fresh unknown, as a value. | |
| virtual void | define (const value_type &unknown, const value_type &rhs) const |
Record the equation unknown = rhs. | |
| virtual bool | equal (const value_type &a, const value_type &b) const |
| Equality of the semiring elements two values denote. | |
| virtual bool | exact_equality () const |
Return true if equal decides equality of semiring elements. | |
| virtual bool | exclusive () const |
Return true if the semiring is exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\). | |
| virtual bool | mul_idempotent () const |
Return true if \(\otimes\) is idempotent: \(a \otimes a = a\). | |
| bool | product_is_joint () const |
| Whether the product of the predicate provenances of two conditions over one family of occurrences is the provenance of their conjunction (and their sum that of their disjunction). | |
| virtual bool | certifying () const |
| Whether this semiring builds certified exclusive enumerations (see the three hooks below). | |
| virtual bool | independent_literal (const value_type &) const |
Whether v is an independent literal for certification purposes: a base Bernoulli variable (or a constant), so that distinct literals have disjoint supports and an AND over them is decomposable. | |
| virtual value_type | certified_world_term (const std::vector< value_type > &, const std::vector< value_type > &) const |
Build one complete world term: the conjunction of the present literals and the negations of the missing literals, certified decomposable. | |
| virtual value_type | certified_exclusive_plus (const std::vector< value_type > &) const |
Build the disjunction of pairwise-exclusive disjuncts, certified deterministic. | |
Additional Inherited Members | |
| Public Types inherited from semiring::Semiring< double > | |
| typedef double | value_type |
| The carrier type of this semiring. | |
The Viterbi (max-times) m-semiring over double.
Each gate evaluates to the probability of the most likely derivation of the corresponding sub-formula.
|
inlineoverridevirtual |
Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).
When true, the circuit evaluator and HAVING-semantics machinery may exploit the resulting idempotency ( \(a \oplus a = a\), implied by absorptivity) to deduplicate children of plus gates and to short-circuit over the multiplicative identity.
A semiring that does not commute (commutative()) is absorptive on both sides of a product: \(a \oplus a \otimes b = a \oplus b \otimes a
= a\), which the absorptive folds of the circuit rely on. Circuits built under an 'absorptive' assumption marker do not keep the order of the query, and require a commutative semiring as well.
false by default; override to return true. Reimplemented from semiring::Semiring< double >.
|
inlineoverridevirtual |
No semiring homomorphism BoolFunc(Y) →+* Viterbi exists (real multiplication is not idempotent), so the safe-query Boolean rewrite is unsound under the Viterbi semiring.
Inherits the false default from Semiring; this override exists for documentation.
Lean: Provenance.Semirings.Viterbi.no_hom_from_BoolFunc (provenance-lean/Provenance/Semirings/Viterbi.lean).
Reimplemented from semiring::Semiring< double >.
|
inlineoverridevirtual |
Apply the \(\delta\) operator.
| x | Input value. |
Implements semiring::Semiring< double >.
Definition at line 69 of file Viterbi.h.

|
inlineoverridevirtual |
Apply the monus (m-semiring difference) operation.
| x | Minuend. |
| y | Subtrahend. |
Implements semiring::Semiring< double >.
Definition at line 65 of file Viterbi.h.

|
inlineoverridevirtual |
\(\otimes\) distributes over \(\ominus\), so the HAVING MIN / MAX comparisons take the single-scan closed form.
Lean: Provenance.Semirings.Viterbi.mul_sub_left_distributive.
Reimplemented from semiring::Semiring< double >.
|
inlineoverridevirtual |
Return the multiplicative identity \(\mathbb{1}\).
Implements semiring::Semiring< double >.
Definition at line 55 of file Viterbi.h.

|
inline |
|
inlineoverridevirtual |
Apply the additive operation to a list of values.
| v | Ordered list of operands (empty list should return zero()). |
Implements semiring::Semiring< double >.
Definition at line 58 of file Viterbi.h.

|
inlineoverridevirtual |
Return true if \(\oplus\) is selective (for all \(a, b\), \(a \oplus b \in \{a, b\}\)).
In an idempotent semiring this is the same as a total natural order; in general it is stronger (the counting semiring has a total natural order, but \(a + b\) is neither \(a\) nor \(b\)). In a selective absorptive semiring (a selective dioid, in Gondran & Minoux's terms), the least solution of a cyclic equation system (a recursive query, see GenericCircuit::solveFixSystem) is found by Dijkstra's algorithm, generalised to semirings (Ramusat, Maniu & Senellart, EDBT 2021): absorption makes extending a derivation never improve it, and selectivity lets the best unsettled value be final.
false by default; override to return true. Reimplemented from semiring::Semiring< double >.
|
inlineoverridevirtual |
Apply the multiplicative operation to a list of values.
| v | Ordered list of operands (empty list should return one()). |
Implements semiring::Semiring< double >.
|
inlineoverridevirtual |
Return the additive identity \(\mathbb{0}\).
Implements semiring::Semiring< double >.
Definition at line 52 of file Viterbi.h.
