# SubAdditiveCurve

Used to represent curves that are known to be sub-additive with $f(0) = 0$ (see IsRegularSubAdditive), and exploit these properties to optimize computations.

$f(0) = 0$ is required for the curve to be IsRegularSubAdditive and provides optimized algorithms for convolution as described in [ZS23], but is not required for sub-additivity to be stable on addition and convolution. To keep the type system simple for the common cases of DNC, we opted not to support non-regular sub-additive functions with their own type.

`public class SubAdditiveCurve : Unipi.Nancy.MinPlusAlgebra.Curve, Unipi.Nancy.MinPlusAlgebra.IToCodeString, Unipi.Nancy.Utility.IStableHashCode`

Inheritance Object → Curve → SubAdditiveCurve

Implements IToCodeString, IStableHashCode

## Properties

**IsSubAdditive**

True if the curve is sub-additive.

For a SubAdditiveCurve this will always return true, without performing any checks.

`public bool IsSubAdditive { get; }`

#### Property Value

**PseudoPeriodStart**

Point in time after which the curve has a pseudo-periodic behavior.

Referred to as $T$ or Rank in [BT08] Section 4.1

`public Rational PseudoPeriodStart { get; set; }`

#### Property Value

**PseudoPeriodLength**

Time length of each pseudo-period.

Referred to as $d$ in [BT08] Section 4.1

`public Rational PseudoPeriodLength { get; set; }`

#### Property Value

**PseudoPeriodHeight**

Static value gain applied after each pseudo-period. If it's 0, the curve is truly periodic.

Referred to as $c$ in [BT08] Section 4.1

`public Rational PseudoPeriodHeight { get; set; }`

#### Property Value

**PseudoPeriodSlope**

Average slope of curve in pseudo-periodic behavior. If it's 0, the curve is truly periodic.

`public Rational PseudoPeriodSlope { get; }`

#### Property Value

**FirstPseudoPeriodEnd**

End time of the first pseudo period.

`public Rational FirstPseudoPeriodEnd { get; }`

#### Property Value

**SecondPseudoPeriodEnd**

End time of the second pseudo period.

`public Rational SecondPseudoPeriodEnd { get; }`

#### Property Value

**BaseSequence**

Sequence describing behavior of the curve in $[0, T + d[$. Combined with the UPP property, this is also allows to derive $f(t)$ for any $t \ge T + d$.

Referred to as $[t_1, ..., t_k]$ in [BT08] Section 4.1

`public Sequence BaseSequence { get; set; }`

#### Property Value

**IsFinite**

True if the curve has finite value for any $t$.

`public bool IsFinite { get; }`

#### Property Value

**FirstFiniteTime**

The first instant around which the curve is not infinite. Does not specify whether it's inclusive or not, i.e. if $f(t)$ is finite.

`public Rational FirstFiniteTime { get; }`

#### Property Value

**FirstFiniteTimeExceptOrigin**

The first instant around which the curve is not infinite, excluding the origin point. Does not specify whether it's inclusive or not, i.e. if $f(t)$ is finite.

`public Rational FirstFiniteTimeExceptOrigin { get; }`

#### Property Value

**FirstNonZeroTime**

The first instant around which the curve is not 0. Does not specify whether it's inclusive or not, i.e. if $f(\overline{t}) = 0$.

`public Rational FirstNonZeroTime { get; }`

#### Property Value

**PseudoPeriodStartInfimum**

Returns the minimum $T_L$ such that $f(t + d) = f(t) + c$ for all $t > T_L$. It is the infimum of all valid PseudoPeriodStart, i.e. $T_L = \inf\{ T | f(t + d) = f(t) + c \forall t \ge T \}$.

`public Rational PseudoPeriodStartInfimum { get; }`

#### Property Value

**IsZero**

True if the curve is 0 for all $t$.

`public bool IsZero { get; }`

#### Property Value

**IsPlusInfinite**

True if the curve has $+\infty$ value for any $t$.

`public bool IsPlusInfinite { get; }`

#### Property Value

**IsMinusInfinite**

True if the curve has $-\infty$ value for any $t$.

`public bool IsMinusInfinite { get; }`

#### Property Value

**IsContinuous**

True if there is no infinite value or discontinuity within the curve.

`public bool IsContinuous { get; }`

#### Property Value

**IsContinuousExceptOrigin**

True if there is no discontinuity within the curve, except at most in origin.

`public bool IsContinuousExceptOrigin { get; }`

#### Property Value

**IsLeftContinuous**

True if there is no left-discontinuity within the curve.

`public bool IsLeftContinuous { get; }`

#### Property Value

**IsRightContinuous**

True if there is no right-discontinuity within the curve.

`public bool IsRightContinuous { get; }`

#### Property Value

**IsNonNegative**

True if the curve is non-negative, i.e. $f(t) \ge 0$ for any $t$.

`public bool IsNonNegative { get; }`

#### Property Value

**FirstNonNegativeTime**

The first instant around which the curve is non-negative. Does not specify whether it's inclusive or not, i.e. if $f(\overline{t}) >= 0$.

`public Rational FirstNonNegativeTime { get; }`

#### Property Value

**IsNonDecreasing**

True if for any $t > s$, $f(t) \ge f(s)$.

`public bool IsNonDecreasing { get; }`

#### Property Value

**IsUltimatelyFinite**

True if for all $t \ge$ PseudoPeriodStart the curve is finite.

This property does not check if $f(t), t <$ PseudoPeriodStart is either infinite, finite or both.

`public bool IsUltimatelyFinite { get; }`

#### Property Value

**IsUltimatelyInfinite**

True if, for $b \in \{-\infty, +\infty\}$ and some $T$, $f(t) = b$ for all $t \ge T$.

`public bool IsUltimatelyInfinite { get; }`

#### Property Value

**IsUltimatelyPlain**

True if for all $t >$ PseudoPeriodStart the curve is either always finite or always infinite.

Defined in [BT08], Definition 1.

`public bool IsUltimatelyPlain { get; }`

#### Property Value

**IsPlain**

True if $f$ is plain, i.e., it is either a) always finite, b) always plus or minus infinite (without changing sign), or c) finite up to a $T$, then always plus or minus infinite (without changing sign)

Formally defined in [BT08], Definition 1.

`public bool IsPlain { get; }`

#### Property Value

**IsUltimatelyAffine**

True if for all $t \ge$ PseudoPeriodStart the curve is affine.

`public bool IsUltimatelyAffine { get; }`

#### Property Value

**IsUltimatelyConstant**

True if for $t \ge$ PseudoPeriodStart the curve is constant.

`public bool IsUltimatelyConstant { get; }`

#### Property Value

**IsRegularSubAdditive**

True if the curve is sub-additive with $f(0) = 0$.

`public bool IsRegularSubAdditive { get; }`

#### Property Value

**IsSuperAdditive**

True if the curve is super-additive, i.e. $f(t+s) \ge f(t) + f(s)$.

Based on [Zippo23] Lemma 9.4: $f$ is super-additive $\iff f^\circ = f^\circ \overline{\otimes} f^\circ$, where $f^\circ$ is defined in WithZeroOrigin(). Can be computationally expensive the first time it is invoked, the result is cached afterwards.

`public bool IsSuperAdditive { get; }`

#### Property Value

**IsRegularSuperAdditive**

True if the curve is super-additive with $f(0) = 0$.

`public bool IsRegularSuperAdditive { get; }`

#### Property Value

**IsConcave**

Tests if the curve is concave, i.e. for any two points $(t, f(t))$ the straight line joining them is below $f$.

The property is checked via the following property: $f$ is concave $\iff$ a) $f$ is continuous, or it is continuous for $t > 0$ and $f(0) \le f(0^+)$, and b) $f$ is composed of segments with decreasing slopes.

`public bool IsConcave { get; }`

#### Property Value

**IsRegularConcave**

Tests if the curve is concave with $f(0) = 0$.

`public bool IsRegularConcave { get; }`

#### Property Value

**IsConvex**

Tests if the curve is convex, i.e. for any two points $(t, f(t))$ the straight line joining them is above $f$.

The property is checked via the following property: $f$ is convex $\iff$ a) $f$ is continuous, or it is continuous for $t > 0$ and $f(0) \ge f(0^+)$, and b) $f$ is composed of segments with increasing slopes.

`public bool IsConvex { get; }`

#### Property Value

**IsRegularConvex**

Tests if the curve is convex with $f(0) = 0$.

`public bool IsRegularConvex { get; }`

#### Property Value

**HasTransient**

True if pseudo-periodic behavior starts at $T > 0$.

`public bool HasTransient { get; }`

#### Property Value

**TransientSequence**

Sequence describing the curve in $[0, T[$, before pseudo-periodic behavior.

`public Sequence TransientSequence { get; }`

#### Property Value

**TransientElements**

Elements describing the curve from $[0, T[$, before pseudo-periodic behavior.

Referred to as $[t_1, ..., t_{i_0 - 1}]$ in [BT08] Section 4.1

`public IEnumerable<Element> TransientElements { get; }`

#### Property Value

**PseudoPeriodicSequence**

Sequence describing the pseudo-periodic behavior of the curve in $[T, T + d[$.

`public Sequence PseudoPeriodicSequence { get; }`

#### Property Value

**PseudoPeriodicElements**

Elements describing the pseudo-periodic behavior of the curve in $[T, T + d[$.

Referred to as $[t_{i_0}, ..., t_k]$ in [BT08] Section 4.1

`public IEnumerable<Element> PseudoPeriodicElements { get; }`

#### Property Value

## Constructors

**SubAdditiveCurve(Sequence, Rational, Rational, Rational, Boolean)**

Constructor

`public SubAdditiveCurve(Sequence baseSequence, Rational pseudoPeriodStart, Rational pseudoPeriodLength, Rational pseudoPeriodHeight, bool doTest)`

#### Parameters

`baseSequence`

Sequence

Describes the curve from 0 to PseudoPeriodStart + PseudoPeriodLength.

`pseudoPeriodStart`

Rational

Instant after which the curve is pseudo-periodic.

`pseudoPeriodLength`

Rational

Length of each pseudo-period.

`pseudoPeriodHeight`

Rational

Step gained after each pseudo-period.

`doTest`

Boolean

If true, the sub-additive property is tested. This test can be computationally expensive.

#### Exceptions

` If is true and the sub-additive property was not successfully verified.`

**SubAdditiveCurve(Curve, Boolean)**

Copy constructor

`public SubAdditiveCurve(Curve other, bool doTest)`

#### Parameters

`other`

Curve

The Curve object to copy from.

`doTest`

Boolean

If true, the sub-additive property is tested. This test can be computationally expensive.

#### Exceptions

` If is true and the sub-additive property was not successfully verified.`

## Methods

**IsSubAdditiveCheck()**

Forced check for sub-additive property.

Can be computationally expensive the first time it is invoked, the result is cached afterwards.

`public bool IsSubAdditiveCheck()`

#### Returns

**IsRegularSubAdditiveCheck()**

Forced check for sub-additive property with f(0) = 0.

Can be computationally expensive the first time it is invoked, the result is cached afterwards.

`public bool IsRegularSubAdditiveCheck()`

#### Returns

**SubAdditiveClosure(ComputationSettings)**

`public SubAdditiveCurve SubAdditiveClosure(ComputationSettings settings)`

#### Parameters

`settings`

ComputationSettings

#### Returns

**Convolution(Curve, ComputationSettings)**

Computes the convolution of the two curves.

Attempts to optimize the computations using theorems in [ZS23].

`public Curve Convolution(Curve curve, ComputationSettings settings)`

#### Parameters

`curve`

Curve

`settings`

ComputationSettings

#### Returns

**Convolution(SubAdditiveCurve, ComputationSettings)**

Computes the convolution of the two curves.

Attempts to optimize the computations using theorems in [ZS23].

`public SubAdditiveCurve Convolution(SubAdditiveCurve curve, ComputationSettings settings)`

#### Parameters

`curve`

SubAdditiveCurve

`settings`

ComputationSettings

#### Returns

**Convolution(IEnumerable<SubAdditiveCurve>, ComputationSettings)**

Computes the convolution of a set of sub-additive curves. Order of operations is optimized to exploit theorems in [ZS23]

`public static SubAdditiveCurve Convolution(IEnumerable<SubAdditiveCurve> curves, ComputationSettings settings)`

#### Parameters

`curves`

IEnumerable<SubAdditiveCurve>

The set of sub-additive curves to be convolved.

`settings`

ComputationSettings

#### Returns

SubAdditiveCurve

The curve resulting from the overall convolution.

**EstimateConvolution(Curve, Boolean, ComputationSettings)**

`public long EstimateConvolution(Curve curve, bool countElements, ComputationSettings settings)`

#### Parameters

`curve`

Curve

`countElements`

Boolean

`settings`

ComputationSettings

#### Returns

**EstimateConvolution(SubAdditiveCurve, Boolean, ComputationSettings)**

Computes the number of elementary convolutions involved in computing the convolution of the two curves, avoiding allocations as much as possible.

Attempts to optimize the computations using theorems in [ZS23]

`public long EstimateConvolution(SubAdditiveCurve curve, bool countElements, ComputationSettings settings)`

#### Parameters

`curve`

SubAdditiveCurve

`countElements`

Boolean

If true, instead of counting only how many convolutions are done, it counts how many convolution elements are produced.

`settings`

ComputationSettings

#### Returns

Int64

The number of elementary convolutions involved in computing the result of the convolution, or the number of elements resulting from these convolutions if is true