English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Dynamic programming (DP) is an algorithmic design paradigm for the efficient,exact solution of otherwise intractable, combinatorial problems. However, DPalgorithm design is often presented in an ad-hoc manner. It is sometimesdifficult to justify algorithm correctness. To address this issue, this paperpresents a rigorous algebraic formalism for systematically deriving DPalgorithms, based on semiring polymorphism. We start with a specification,construct an algorithm to compute the required solution which is self-evidentlycorrect because it exhaustively generates and evaluates all possible solutionsmeeting the specification. We then derive, through the use of shortcut fusion,an implementation of this algorithm which is both efficient and correct. Wealso demonstrate how, with the use of semiring lifting, the specification canbe augmented with combinatorial constraints, showing how these constraints canbe fused with the algorithm. We furthermore demonstrate how existing DPalgorithms for a given combinatorial problem can be abstracted from theiroriginal context and re-purposed.  This approach can be applied to the full scope of combinatorial problemsexpressible in terms of semirings. This includes, for example: optimalprobability and Viterbi decoding, probabilistic marginalization, logicalinference, fuzzy sets, differentiable softmax, relational and provenancequeries. The approach, building on ideas from the existing literature onconstructive algorithmics, exploits generic properties of polymorphicfunctions, tupling and formal sums and algebraic simplifications arising fromconstraint algebras. We demonstrate the effectiveness of this formalism forsome example applications arising in signal processing, bioinformatics andreliability engineering. Python software implementing these algorithms can bedownloaded from: http://www.maxlittle.net/software/dppolyalg.zip.

Dynamic programming by polymorphic semiring algebraic shortcut fusion